@article{Chandra21082025,
author = {Chandra, Ghanshyam and Hossen, Md Helal and Scholz, Stephan and Dilthey, Alexander T and Gibney, Daniel and Jain, Chirag}, 
title = {Pangenome-based genome inference using integer programming},
year = {2025}, 
doi = {10.1101/gr.280567.125}, 
elocation-id = {gr.280567.125}, 
abstract ={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.}, 
URL = {http://genome.cshlp.org/content/early/2025/08/21/gr.280567.125.abstract}, 
eprint = {http://genome.cshlp.org/content/early/2025/08/21/gr.280567.125.full.pdf+html}, 
journal = {Genome Research} 
}