Fast randomized approximate string matching with succinct hash data structures. Issue 9 (December 2015)

• Record Type: Journal Article
• Authors: Policriti, Alberto; Prezza, Nicola
• Is Part Of: BMC bioinformatics. Volume 16:Issue 9(2015)
• Page Start: 1
• Page End: 8
• Publication Date: 2015-12
• Subjects: Hashing -- succinct indexing -- BWT -- de Bruijn property -- complexity analysis; Bioinformatics -- Periodicals; Computational biology -- Periodicals; 570.285
• DOI: 10.1186/1471-2105-16-S9-S4
• Languages: English
• ISSNs: 1471-2105

Abstract

Abstract Background The high throughput of modern NGS sequencers coupled with the huge sizes of genomes currently analysed, poses always higher algorithmic challenges to align short reads quickly and accurately against a reference sequence. A crucial, additional, requirement is that the data structures used should belight . The available modern solutions usually are a compromise between the mentioned constraints: in particular, indexes based on the Burrows-Wheeler transform offer reduced memory requirements at the price of lower sensitivity, while hash-based text indexes guarantee high sensitivity at the price of significant memory consumption. Methods In this work we describe a technique that permits to attain the advantages granted by both classes of indexes. This is achieved using Hamming-aware hash functions--hash functions designed to search the entire Hamming sphere in reduced time--which are also homomorphisms on de Bruijn graphs. We show that, using this particular class of hash functions, the corresponding hash index can be represented in linear space introducing only a logarithmic slowdown (in the query length) for the lookup operation. We point out that our data structure reaches its goalswithout compressing its input: another positive feature, as in biological applications data is often very close to be un-compressible. Results The new data structure introduced in this work is calleddB-hash and we show how its implementation--BW-ERNE--maintains the high sensitivity and speed of its (hash-based) predecessor ERNE, while drastically reducing space consumption. Extensive comparison experiments conducted with several popular alignment tools on both simulated and real NGS data, show, finally, that BW-ERNE is able to attain both the positive features of succinct data structures (that is, small space) and hash indexes (that is, sensitivity). Conclusions In applications where space and speed are both a concern, standard methods often sacrifice accuracy to obtain competitive throughputs and memory footprints. In this work we show that, combining hashing and succinct indexing techniques, we can attain good performances and accuracy with a memory footprint comparable to that of the most popular compressed indexes.