BLESS: bloom filter-based error correction solution for high-throughput sequencing reads.
BACKGROUND
Rapid advances in next-generation sequencing (NGS) technology have led to exponential increase in the amount of genomic information. However, NGS reads contain far more errors than data from traditional sequencing methods, and downstream genomic analysis results can be improved by correcting the errors. Unfortunately, all the previous error correction methods required a large amount of memory, making it unsuitable to process reads from large genomes with commodity computers.


RESULTS
We present a novel algorithm that produces accurate correction results with much less memory compared with previous solutions. The algorithm, named BLoom-filter-based Error correction Solution for high-throughput Sequencing reads (BLESS), uses a single minimum-sized Bloom filter, and is also able to tolerate a higher false-positive rate, thus allowing us to correct errors with a 40× memory usage reduction on average compared with previous methods. Meanwhile, BLESS can extend reads like DNA assemblers to correct errors at the end of reads. Evaluations using real and simulated reads showed that BLESS could generate more accurate results than existing solutions. After errors were corrected using BLESS, 69% of initially unaligned reads could be aligned correctly. Additionally, de novo assembly results became 50% longer with 66% fewer assembly errors.


METHODS
Freely available at http://sourceforge.net/p/bless-ec


BACKGROUND
dchen@illinois.edu


BACKGROUND
Supplementary data are available at Bioinformatics online.
Department of Electrical and Computer Engineering, Department of Bioengineering and Institute for Genomic Biology, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.
Yun
Y
Heo
Xiao-Long
XL
Wu
Deming
D
Chen
Jian
J
Ma
Wen-Mei
WM
Hwu
D000465:Algorithms; D057205:Automation, Laboratory; D005189:False Positive Reactions; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods