Using 2k + 2 bubble searches to find single nucleotide polymorphisms in k-mer graphs.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Single nucleotide polymorphism (SNP) discovery is crucial for understanding genetic variation.
• Current alignment-based methods face challenges in complex genomic regions and high-coverage data.
• De Bruijn graphs offer an alternative approach for handling large sequencing datasets.

Purpose of the Study:

• To develop and evaluate a novel algorithm for SNP discovery using De Bruijn graphs.
• To assess the accuracy and comprehensiveness of the new method compared to alignment-based approaches.
• To improve SNP calling in complex genomic regions and high-coverage scenarios.

Main Methods:

• Developed an algorithm that calls SNPs by enumerating 2k+2 cycles in converted De Bruijn graphs.
• Evaluated SNP calling accuracy against established alignment-based methods.
• Utilized sequence-based graph attributes to train a decision tree for enhanced accuracy.

Main Results:

• The algorithm demonstrated high accuracy in SNP calling across diverse genomic features in Arabidopsis thaliana.
• SNP calling performance was consistent across the genome, including complex and high-coverage regions.
• Integrating a decision tree further improved the accuracy of SNP predictions.

Conclusions:

• The developed algorithm accurately identifies SNPs using De Bruijn graphs, offering a robust alternative to alignment-based methods.
• This approach effectively handles complex genomic structures and high-coverage data, enabling more comprehensive SNP discovery.
• The method shows promise for accurate and extensive SNP detection from whole-genome sequencing data.