Cargando…

An efficient error correction algorithm using FM-index

BACKGROUND: High-throughput sequencing offers higher throughput and lower cost for sequencing a genome. However, sequencing errors, including mismatches and indels, may be produced during sequencing. Because, errors may reduce the accuracy of subsequent de novo assembly, error correction is necessar...

Descripción completa

Detalles Bibliográficos
Autores principales: Huang, Yao-Ting, Huang, Yu-Wen
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2017
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5704532/
https://www.ncbi.nlm.nih.gov/pubmed/29179672
http://dx.doi.org/10.1186/s12859-017-1940-1
_version_ 1783281916292628480
author Huang, Yao-Ting
Huang, Yu-Wen
author_facet Huang, Yao-Ting
Huang, Yu-Wen
author_sort Huang, Yao-Ting
collection PubMed
description BACKGROUND: High-throughput sequencing offers higher throughput and lower cost for sequencing a genome. However, sequencing errors, including mismatches and indels, may be produced during sequencing. Because, errors may reduce the accuracy of subsequent de novo assembly, error correction is necessary prior to assembly. However, existing correction methods still face trade-offs among correction power, accuracy, and speed. RESULTS: We develop a novel overlap-based error correction algorithm using FM-index (called FMOE). FMOE first identifies overlapping reads by aligning a query read simultaneously against multiple reads compressed by FM-index. Subsequently, sequencing errors are corrected by k-mer voting from overlapping reads only. The experimental results indicate that FMOE has highest correction power with comparable accuracy and speed. Our algorithm performs better in long-read than short-read datasets when compared with others. The assembly results indicated different algorithms has its own strength and weakness, whereas FMOE is good for long or good-quality reads. CONCLUSIONS: FMOE is freely available at https://github.com/ythuang0522/FMOC. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1186/s12859-017-1940-1) contains supplementary material, which is available to authorized users.
format Online
Article
Text
id pubmed-5704532
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-57045322017-12-05 An efficient error correction algorithm using FM-index Huang, Yao-Ting Huang, Yu-Wen BMC Bioinformatics Methodology Article BACKGROUND: High-throughput sequencing offers higher throughput and lower cost for sequencing a genome. However, sequencing errors, including mismatches and indels, may be produced during sequencing. Because, errors may reduce the accuracy of subsequent de novo assembly, error correction is necessary prior to assembly. However, existing correction methods still face trade-offs among correction power, accuracy, and speed. RESULTS: We develop a novel overlap-based error correction algorithm using FM-index (called FMOE). FMOE first identifies overlapping reads by aligning a query read simultaneously against multiple reads compressed by FM-index. Subsequently, sequencing errors are corrected by k-mer voting from overlapping reads only. The experimental results indicate that FMOE has highest correction power with comparable accuracy and speed. Our algorithm performs better in long-read than short-read datasets when compared with others. The assembly results indicated different algorithms has its own strength and weakness, whereas FMOE is good for long or good-quality reads. CONCLUSIONS: FMOE is freely available at https://github.com/ythuang0522/FMOC. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1186/s12859-017-1940-1) contains supplementary material, which is available to authorized users. BioMed Central 2017-11-28 /pmc/articles/PMC5704532/ /pubmed/29179672 http://dx.doi.org/10.1186/s12859-017-1940-1 Text en © The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Methodology Article
Huang, Yao-Ting
Huang, Yu-Wen
An efficient error correction algorithm using FM-index
title An efficient error correction algorithm using FM-index
title_full An efficient error correction algorithm using FM-index
title_fullStr An efficient error correction algorithm using FM-index
title_full_unstemmed An efficient error correction algorithm using FM-index
title_short An efficient error correction algorithm using FM-index
title_sort efficient error correction algorithm using fm-index
topic Methodology Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5704532/
https://www.ncbi.nlm.nih.gov/pubmed/29179672
http://dx.doi.org/10.1186/s12859-017-1940-1
work_keys_str_mv AT huangyaoting anefficienterrorcorrectionalgorithmusingfmindex
AT huangyuwen anefficienterrorcorrectionalgorithmusingfmindex
AT huangyaoting efficienterrorcorrectionalgorithmusingfmindex
AT huangyuwen efficienterrorcorrectionalgorithmusingfmindex