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

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Mapping-based approaches using FM-indexes are computationally intensive for large reference databases (>10 GB).
• Index construction for massive datasets, crucial for next-generation sequencing (NGS) read analysis, can take over a day on high-memory machines.
• The difficulty in updating FM-indexes hinders the incorporation of new genomic data and analysis of dynamic biological systems.

Purpose of the Study:

• To develop an alternative indexing strategy that overcomes the limitations of FM-indexes for large-scale biological data.
• To enable faster and more efficient approximate matching of NGS reads to extensive reference databases.
• To facilitate easier index updates and maintain rapid search performance.

Main Methods:

• Introduction of the DREAM (Dynamic seaRchablE pArallel coMpressed index) framework.
• Development of an approximate search distributor utilizing a novel interleaved Bloom filter data structure.
• Implementation of DREAM-Yara, a distributed, fully sensitive read mapper within the DREAM framework.

Main Results:

• The interleaved Bloom filter effectively excludes reads from irrelevant database portions, significantly speeding up search times.
• The DREAM framework allows for parallel processing and dynamic index rebuilding, addressing the bottleneck of large index construction.
• DREAM-Yara demonstrates efficient and sensitive read mapping capabilities within the proposed framework.

Conclusions:

• The DREAM framework provides a scalable and efficient solution for indexing and searching large biological sequence databases.
• The novel Bloom filter application enhances the speed and manageability of NGS read analysis.
• DREAM-Yara offers a robust tool for metagenomics and other applications requiring rapid and accurate read mapping.