Search Results

Documents authored by Brejová, Broňa

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}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.WABI.2025
LIPIcs, Volume 344, WABI 2025, Complete Volume

Authors: Broňa Brejová and Rob Patro

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
LIPIcs, Volume 344, WABI 2025, Complete Volume
Cite as

25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 1-430, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Proceedings{brejova_et_al:LIPIcs.WABI.2025,
  title =	{{LIPIcs, Volume 344, WABI 2025, Complete Volume}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{1--430},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025},
  URN =		{urn:nbn:de:0030-drops-243498},
  doi =		{10.4230/LIPIcs.WABI.2025},
  annote =	{Keywords: LIPIcs, Volume 344, WABI 2025, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.WABI.2025.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Broňa Brejová and Rob Patro

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brejova_et_al:LIPIcs.WABI.2025.0,
  author =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.0},
  URN =		{urn:nbn:de:0030-drops-243477},
  doi =		{10.4230/LIPIcs.WABI.2025.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact