DREAM-Yara: an exact read mapper for very large databases with short update time
Authors:
- 1 September 2018
- journal article
- conference paper
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 34 (17) , i766-i772
Abstract
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 1 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 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. Availability and implementation: https://gitlab.com/pirovc/dream_yara/Keywords
All Related Versions
Funding Information
- Coordenação de Aperfei-çoamento de Pessoal de Nível Superior
- CAPES
- Ciência sem Fronteiras (BEX 13472/13-5)
- InfectControl 2020 Project
- BMG
- Metagenome Analysis Tool (2515NIK043)
- IMPRS for Scientific Computing and Computational Biology
This publication has 21 references indexed in Scilit:
- The GEM mapper: fast, accurate and versatile alignment by filtrationNature Methods, 2012
- RazerS 3: Faster, fully sensitive read mappingBioinformatics, 2012
- Fast gapped-read alignment with Bowtie 2Nature Methods, 2012
- The NCBI Taxonomy databaseNucleic Acids Research, 2011
- A novel and well-defined benchmarking method for second generation read mappingBMC Bioinformatics, 2011
- Fast and accurate long-read alignment with Burrows–Wheeler transformBioinformatics, 2010
- Simultaneous alignment of short reads against multiple genomesGenome Biology, 2009
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- Approximation algorithms for a hierarchically structured bin packing problemInformation Processing Letters, 2004
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970