06104415

a

06104415 Chapuis, Guillaume Chikhi, Rayan Lavenier, Dominique Parallel and memory-efficient reads indexing for genome assembly. Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 9th international conference, PPAM 2011, Torun, Poland, September 11--14, 2011. Revised selected papers, Part II. Berlin: Springer (ISBN 978-3-642-31499-5/pbk). Lecture Notes in Computer Science 7204, 272-280 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-31500-8_28

Summary: As genomes, transcriptomes and meta-genomes are being sequenced at a faster pace than ever, there is a pressing need for efficient genome assembly methods. Two practical issues in assembly are heavy memory usage and long execution time during the read indexing phase. In this article, a parallel and memory-efficient method is proposed for reads indexing prior to assembly. Specifically, a hash-based structure that stores a reduced amount of read information is designed. Erroneous entries are filtered on the fly during index construction. A prototype implementation has been designed and applied to actual Illumina short reads. Benchmark evaluation shows that this indexing method requires significantly less memory than those from popular assemblers.