A variant selection framework for genome graphs.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Variation graphs are emerging as a powerful alternative to single genome references for capturing population diversity and mitigating reference bias in genomics.
• Existing large variant catalogs necessitate methods to identify essential variants for efficient and accurate read mapping.

Purpose of the Study:

• To develop a novel mathematical framework for selecting critical genetic variants to minimize variation graph size.
• To address variant selection problems by minimizing graph size while preserving sequence paths of a specific length and difference threshold.

Main Methods:

• Formulated variant selection as a mathematical optimization problem: minimizing variation graph size under constraints of path preservation (length α, δ differences).
• Investigated problems based on variant types (SNPs, indels, SVs) and minimization goals (number of variant positions vs. total variants).
• Analyzed computational complexity and developed efficient algorithms with software implementation (VF).

Main Results:

• Empirically evaluated graph reduction on human chromosome variation graphs using varying parameters (α, δ) for short and long-read sequencing.
• Demonstrated significant size reduction: 99.99% SNPs and 73% SVs excluded from human chromosome 1 variation graph with long-read parameters (α=10 kbp, δ=1000).

Conclusions:

• The proposed framework and algorithms effectively reduce variation graph size, enhancing efficiency for downstream analyses.
• Significant reduction in genetic variants is achievable without compromising critical information for read mapping, benefiting pan-genome studies.