DiGi: An Integer Programming Formulation for Diploid Genome Inference Using a Pangenome Reference

Compared with genotyping against a single linear reference genome, pangenome-based genotyping enables more comprehensive detection of genetic variation, including structural variants. Existing genotyping methods employ a range of combinatorial, probabilistic, and statistical techniques. One class of methods formulates genotyping as a combinatorial path-finding problem in a pangenome graph, allowing bounded recombinations between reference haplotypes. By restricting solutions to mosaics of reference haplotypes, this formulation implicitly exploits linkage disequilibrium. However, extending this formulation to diploid genomes requires jointly identifying two mosaic paths, leading to an exponential increase in the search space. To address this challenge, we first represent the pangenome as a haplotype trellis graph, which maintains reference haplotypes as separate sequences and permits switching between them only at a predefined set of positions. Second, we formulate a combinatorial optimization problem that uses sequencing reads from a target genome to jointly infer a pair of haplotype paths in the graph. We then develop a probabilistic model that automatically sets the optimization parameters based on the read length and coverage of the input data, and an integer programming formulation to solve the resulting problem exactly. Our implementation, DiGi, successfully reconstructs both paternal and maternal copies of 90% of key HLA genes in target genomes absent from the pangenome reference, achieving sequence identity above 99.9%. On the HG002 Genome in a Bottle benchmark, DiGi achieves favorable F1 scores for genotyping SNVs, indels, and structural variants in the highly polymorphic major histocompatibility complex (MHC) region. DiGi remains accurate across a wide range of sequencing coverages, which makes it well suited to population-scale studies with variable coverage across samples.

Authors

Institutions

Publication Details

Journal
bioRxiv (Cold Spring Harbor Laboratory)
Published
2026-11-17
DOI
https://doi.org/10.64898/2026.11.15.766871
Primary Topic
Genomics and Phylogenetic Studies
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

DiGi: An Integer Programming Formulation for Diploid Genome Inference Using a Pangenome Reference

Anandita Mishra, Alexander Dilthey, Chirag Jain
1 links
bioRxiv (Cold Spring Harbor Laboratory)
Genomics and Phylogenetic Studies
preprint

DiGi: An Integer Programming Formulation for Diploid Genome Inference Using a Pangenome Reference

Anandita Mishra, Alexander Dilthey, Chirag Jain
preprint en

Abstract

Compared with genotyping against a single linear reference genome, pangenome-based genotyping enables more comprehensive detection of genetic variation, including structural variants. Existing genotyping methods employ a range of combinatorial, probabilistic, and statistical techniques. One class of methods formulates genotyping as a combinatorial path-finding problem in a pangenome graph, allowing bounded recombinations between reference haplotypes. By restricting solutions to mosaics of reference haplotypes, this formulation implicitly exploits linkage disequilibrium. However, extending this formulation to diploid genomes requires jointly identifying two mosaic paths, leading to an exponential increase in the search space. To address this challenge, we first represent the pangenome as a haplotype trellis graph, which maintains reference haplotypes as separate sequences and permits switching between them only at a predefined set of positions. Second, we formulate a combinatorial optimization problem that uses sequencing reads from a target genome to jointly infer a pair of haplotype paths in the graph. We then develop a probabilistic model that automatically sets the optimization parameters based on the read length and coverage of the input data, and an integer programming formulation to solve the resulting problem exactly. Our implementation, DiGi, successfully reconstructs both paternal and maternal copies of 90% of key HLA genes in target genomes absent from the pangenome reference, achieving sequence identity above 99.9%. On the HG002 Genome in a Bottle benchmark, DiGi achieves favorable F1 scores for genotyping SNVs, indels, and structural variants in the highly polymorphic major histocompatibility complex (MHC) region. DiGi remains accurate across a wide range of sequencing coverages, which makes it well suited to population-scale studies with variable coverage across samples.

bioRxiv (Cold Spring Harbor Laboratory)
Heinrich Heine University Düsseldorf (DE), Indian Institute of Science Bangalore (IN)
Genomics and Phylogenetic Studies
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon