StLiter: A Novel Algorithm to Iteratively Build the Compacted de Bruijn Graph From Many Complete Genomes.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Compacted de Bruijn graphs (cDBGs) are valuable for read mapping due to their ability to handle genomic repetitions.
• Current methods for constructing cDBGs lack flexibility for varying k-mer lengths.
• Building cDBGs for longer k-mers directly can be computationally intensive.

Purpose of the Study:

• To introduce StLiter, a novel algorithm for constructing compacted de Bruijn graphs.
• To enable efficient cDBG construction either directly from genome sequences or indirectly from existing shorter k-mer graphs.
• To address the limitations of current cDBG construction methods regarding flexibility and computational cost.

Main Methods:

• StLiter algorithm for constructing cDBGs directly from genome sequences.
• StLiter algorithm for constructing longer k-mer cDBGs based on pre-existing shorter k-mer cDBGs.
• Performance evaluation against TwoPaCo on simulated and real genomic datasets.

Main Results:

• StLiter constructs cDBGs for k-mer lengths 15-18 in 2.5-5.9 hours with ~70GB memory on simulated human genomes.
• StLiter is 5-9 times faster than TwoPaCo for k-mer lengths 15-18, using less memory.
• StLiter demonstrates improved efficiency for k-mer lengths >18 when building from shorter k-mer graphs.

Conclusions:

• StLiter offers a more efficient and flexible approach to constructing compacted de Bruijn graphs.
• The indirect construction method of StLiter significantly outperforms direct construction for longer k-mers.
• StLiter provides a valuable tool for genomic sequence analysis, particularly for read mapping applications.