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...
Autores principales: | , |
---|---|
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 |