Read mapping on de Bruijn graphs.

Area of Science:

• Genomics
• Bioinformatics

Background:

• Next Generation Sequencing (NGS) generates vast amounts of genomic data, but genome assembly often results in fragmented contigs, losing valuable sequence information.
• Current methods for analyzing assembled genomes primarily use contigs, which may not capture the complete information present in the original assembly graph.

Purpose of the Study:

• To develop a practical and efficient method for mapping sequencing reads directly onto de Bruijn graphs, thereby recovering potentially lost sequence information.
• To assess the informativeness of mapping reads on assembly graphs compared to mapping on contigs.

Main Methods:

• Formalized the problem of mapping reads on de Bruijn graphs, identifying it as NP-complete.
• Developed the GGMAP (Greedy Graph MAPping) pipeline, featuring the BGREAT (de Bruijn Graph REAd mapping Tool) heuristic algorithm for mapping reads on branching paths.
• Optimized BGREAT by representing read sequences as successions of unitig sequences for efficiency.

Main Results:

• The GGMAP pipeline demonstrates high efficiency, capable of mapping millions of reads per CPU hour on large human genomic datasets.
• Mapping reads on the de Bruijn graph identified up to 22% more mappable reads compared to mapping solely on the set of contigs.
• The proposed method successfully handles complex eukaryotic data.

Conclusions:

• Despite the inherent complexity of mapping reads on de Bruijn graphs, a practical and efficient solution has been developed.
• The GGMAP pipeline offers improved read mapping capacity over traditional contig-based methods, leading to more comprehensive genome analysis.