Denys Andrukhovskyi, Martin Madzin, Luca Denti, Tomás Vinar, Brona Brejová. Efficient Algorithms for Pangenome Personalization. In Nadia El-Mabrouk, Fabio Vandin, ed., 26th International Conference on Algorithms for Bioinformatics (WABI), 393 volume of LIPIcs, pp. 8:1-8:17, 2026. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Download preprint: not available
Download from publisher: https://doi.org/10.4230/LIPIcs.WABI.2026.8
Related web page: not available
Bibliography entry: BibTeX
Abstract:
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.
Last modified: 28.09.2026
Contact: Tomáš Vinař, KAI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Broňa Brejová, KI FMFI UK, Mlynská Dolina, 84248 Bratislava, Slovakia
Office: M-163 Phone: +421(2)60295207
E-mail: 