Rxivist logo

DREAM-Yara: An exact read mapper for very large databases with short update time

By Temesgen Hailemariam Dadi, Enrico Siragusa, Vitor C. Piro, Andreas Andrusch, Enrico Seiler, Bernhard Y. Renard, Knut Reinert

Posted 30 Jan 2018
bioRxiv DOI: 10.1101/256354 (published DOI: 10.1093/bioinformatics/bty567)

Motivation: Mapping-based approaches have become limited in their application to very large sets of references since computing an FM-index for very large databases (e.g. > 10 GB) has become a bottleneck. This affects many analyses that need such index as an essential step for approximate matching of the NGS reads to reference databases. For instance, in typical metagenomics analysis, the size of the reference sequences has become prohibitive to compute a single full- text index on standard machines. Even on large memory machines, computing such index takes about one day of computing time. As a result, updates of indices are rarely performed. Hence, it is desirable to create an alternative way of indexing while preserving fast search times. Results: To solve the index construction and update problem we propose the DREAM (Dynamic seaRchablE pArallel coMpressed index) framework and provide an implementation. The main contributions are the introduction of an approximate search distributor directories via a novel use of Bloom filters. We combine several Bloom filters to form an interleaved Bloom filter and use this new data structure to quickly exclude reads for parts of the databases where they cannot match. This allows us to keep the databases in several indices which can be easily rebuilt if parts are updated while maintaining a fast search time. The second main contribution is an implementation of DREAM-Yara a distributed version of a fully sensitive read mapper under the DREAM framework.

Download data

  • Downloaded 775 times
  • Download rankings, all-time:
    • Site-wide: 20,630 out of 103,764
    • In bioinformatics: 2,987 out of 9,474
  • Year to date:
    • Site-wide: 53,409 out of 103,764
  • Since beginning of last month:
    • Site-wide: 49,864 out of 103,764

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)