DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.8

Efficient Algorithms for Pangenome Personalization

Authors: Denys Andrukhovskyi, Martin Madzin, Luca Denti, Tomáš Vinař, and Broňa Brejová

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

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.

Cite as

Denys Andrukhovskyi, Martin Madzin, Luca Denti, Tomáš Vinař, and Broňa Brejová. Efficient Algorithms for Pangenome Personalization. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andrukhovskyi_et_al:LIPIcs.WABI.2026.8,
  author =	{Andrukhovskyi, Denys and Madzin, Martin and Denti, Luca and Vina\v{r}, Tom\'{a}\v{s} and Brejov\'{a}, Bro\v{n}a},
  title =	{{Efficient Algorithms for Pangenome Personalization}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.8},
  URN =		{urn:nbn:de:0030-drops-275125},
  doi =		{10.4230/LIPIcs.WABI.2026.8},
  annote =	{Keywords: pangenome graph, approximation algorithm, network flow}
}

Search Results

Documents authored by Andrukhovskyi, Denys

Efficient Algorithms for Pangenome Personalization

Abstract

Cite as

Thanks for your feedback!

Could not send message