EUVIMEDEUVIMED entdecken
Open Access

Pangenome-based genome inference using integer programming

Ghanshyam Chandra, Md Helal Hossen, Stephan Scholz, Alexander T Dilthey, Daniel Gibney, Chirag Jain

Genome Research · 2025

DOI: 10.1101/gr.280567.125 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Genome Research, 2025. Verfasst von Ghanshyam Chandra und 5 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computational and Data Sciences, Indian Institute of Science, Bangalore, Karnataka 560012, India. Hauptthemen laut MEDLINE: Genomics, Genome, Human, Genotyping Techniques. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 40 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: DBT-Wellcome Trust India Alliance, DBT/Wellcome Trust India Alliance Fellowship, Intel India Research Fellowship.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 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 benchmark the algorithm using downsampled short-read data sets 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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

GenomicsGenome, HumanGenotyping TechniquesHumansAlgorithmsHaplotypesMajor Histocompatibility ComplexPolymorphism, Single NucleotideSoftwareSequence Analysis, DNA

Autor:innen und Institutionen

  • Department of Computational and Data Sciences, Indian Institute of Science, Bangalore, Karnataka 560012, India.
  • Department of Computer Science, The University of Texas at Dallas, Dallas, Texas 75080, USA.
  • Institute of Medical Microbiology and Hospital Hygiene, Heinrich Heine University Düsseldorf, 40225 Düsseldorf, Germany.
  • Center for Digital Medicine, Heinrich Heine University Düsseldorf, 40225 Düsseldorf, Germany.
  • Department of Computational and Data Sciences, Indian Institute of Science, Bangalore, Karnataka 560012, India; chirag@iisc.ac.in.

Förderung

  • DBT-Wellcome Trust India Alliance
  • DBT/Wellcome Trust India Alliance Fellowship
  • Intel India Research Fellowship
  • National Institutes of Health
  • NIH-NIAID
  • Jürgen Manchot Foundation

Zitieren

APA

Chandra, G., Hossen, M. H., Scholz, S., Dilthey, A. T., Gibney, D., & Jain, C. (2025). Pangenome-based genome inference using integer programming. Genome Research. https://doi.org/10.1101/gr.280567.125

Vancouver

Chandra G, Hossen MH, Scholz S, Dilthey AT, Gibney D, Jain C. Pangenome-based genome inference using integer programming. Genome Research. 2025. doi:10.1101/gr.280567.125

BibTeX
@article{Chandra2025,
  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},
  journal = {Genome Research},
  year = {2025},
  doi = {10.1101/gr.280567.125}
}
Kostenlos starten →