2026-08-27T21:20:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27512 2026-08-27T06:04:07Z ddc:004 open_access

Efficient Algorithms for Pangenome Personalization Andrukhovskyi, Denys Madzin, Martin Denti, Luca Vinař, Tomáš Brejová, Broňa pangenome graph approximation algorithm network flow A pangenome graph is a representation of the genomes of multiple individuals of the same species. Using a pangenome graph reference instead of a single linear reference genome can increase accuracy of read mapping and downstream tasks, e.g., variant calling, but can also lead to increasing computational demands and false positives. In 2024, Sirén et al. proposed to select only parts of the pangenome mostly likely to match a studied individual, introducing the so-called personalized pangenome reference. Their algorithm is based on greedily selecting sections of paths representing individual haplotypes comprising the pangenome. In this article, we formulate the problem of pangenome personalization purely in terms of pangenome vertices and edges, as finding two paths using vertices supported by sequencing data. We provide several algorithms for solving the problem, ranging from a simple linear-time greedy algorithm with approximation ratio analysis, through dynamic programming and application of minimum-cost flow. Our implementation misses only a small percentage of vertices belonging to the studied individual and improves the sensitivity of read mapping compared to the linear reference. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Denys Andrukhovskyi and Martin Madzin and Luca Denti and Tomáš Vinař and Broňa Brejová 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.8 urn:nbn:de:0030-drops-275125 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode