Integer programming framework for pangenome-based genome inference.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Current genotyping methods struggle with structural variants and repetitive genomic regions.
• Reference genome alignments are unreliable in polymorphic and repetitive areas, limiting genotyping accuracy.
• Haplotype-resolved pangenome graphs offer a promising approach to overcome these limitations.

Purpose of the Study:

• To develop a novel, alignment-free genotyping framework utilizing pangenome graphs.
• To address the challenge of accurately genotyping structural variants and complex genomic regions.
• To improve genotyping performance, especially in low-coverage sequencing scenarios.

Main Methods:

• Proposed an alignment-free genotyping framework based on pangenome graphs.
• Formulated the problem as finding an optimal path in the pangenome graph maximizing k-mer matches and minimizing haplotype switches.
• Developed efficient integer-programming solutions for the NP-Hard problem.
• Benchmarked the algorithm using downsampled short-read data from homozygous human cell lines (0.1× to 10× coverage).

Main Results:

• The algorithm accurately estimates complete major histocompatibility complex (MHC) haplotype sequences.
• Achieved small edit distances between estimated and ground-truth MHC haplotypes.
• Demonstrated significant advantages over existing methods, particularly for low-coverage sequencing data.
• Successfully handled challenges posed by polymorphic and repetitive genomic regions.

Conclusions:

• The developed alignment-free framework provides accurate genotyping, especially for structural variants and MHC haplotypes.
• The method shows superior performance in low-coverage sequencing settings compared to traditional approaches.
• Future extensions are planned to accommodate diploid samples, broadening the applicability of the framework.