TY  - JOUR
A1  - Chandra, Ghanshyam
A1  - Hossen, Md Helal
A1  - Scholz, Stephan
A1  - Dilthey, Alexander T
A1  - Gibney, Daniel
A1  - Jain, Chirag
T1  - Pangenome-based genome inference using integer programming
Y1  - 2025/08/21 
JF  - Genome Research 
JO  - Genome Research 
DO  - 10.1101/gr.280567.125 
SP  - gr.280567.125 
UR  - http://genome.cshlp.org/content/early/2025/08/21/gr.280567.125.abstract 
N2  - Affordable genotyping methods are essential in genomics. Commonly used genotyping methods primarily support single nucleotide variants and short indels but neglect structural variants. Additionally, accuracy of read alignments to a reference genome is unreliable in highly polymorphic and repetitive regions, further impacting genotyping performance. Recent works highlight the advantage of haplotype-resolved pangenome graphs in addressing these challenges. Building on these developments, we propose a rigorous alignment-free genotyping method. Our optimization framework identifies a path through the pangenome graph that maximizes the matches between the path and substrings of sequencing reads (e.g., k-mers) while minimizing recombination events (haplotype switches) along the path. We prove that this problem is NP-Hard and develop efficient integer-programming solutions. We benchmarked the algorithm using downsampled short-read datasets from homozygous human cell lines with coverage ranging from 0.1× to 10×. Our algorithm accurately estimates complete major histocompatibility complex (MHC) haplotype sequences with small edit distances from the ground-truth sequences, providing a significant advantage over existing methods on low-coverage inputs. While this algorithm is designed for haploid genomes, we discuss directions for extending it to diploid genotyping. 
ER  -