DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.29

Reconciling and Comparing Variation Graphs Using Homology Relations

Authors: Anna Lisiecka, Adam Cicherski, and Norbert Dojer

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

Abstract

In variation graphs genomic sequences are represented as paths sharing their nodes in homologous regions. Shared nodes must represent identical sequence fragments, but the definition does not impose strict criteria on when the paths should be merged and when not. Consequently, most variation graph building tools heuristically infer the graph structure from pairwise genome alignments or the results of seeding procedures of alignment algorithms. In the current paper we introduce the concept of homology relation induced by a variation graph on the nucleotides of represented genomic sequences. This notion can be used to specify in a mathematically rigorous way the criteria the structure of a variation graph should meet. We investigate the relationships between the structures of variation graphs and their homology relations, as well as between operations on relations and on graphs. In particular, we show how to use the result of combining relations induced by different graphs to combine these graphs. Then, we propose homology-based methods of reconciling and comparing variation graphs representing the same genome collection. Moreover, we provide an implementation of homology-based tools for variation graph analysis.

Cite as

Anna Lisiecka, Adam Cicherski, and Norbert Dojer. Reconciling and Comparing Variation Graphs Using Homology Relations. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lisiecka_et_al:LIPIcs.WABI.2026.29,
  author =	{Lisiecka, Anna and Cicherski, Adam and Dojer, Norbert},
  title =	{{Reconciling and Comparing Variation Graphs Using Homology Relations}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{29:1--29:15},
  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.29},
  URN =		{urn:nbn:de:0030-drops-275332},
  doi =		{10.4230/LIPIcs.WABI.2026.29},
  annote =	{Keywords: Pangenome, Variation Graph, Genome Homology}
}

Document

DOI: 10.4230/LIPIcs.WABI.2024.23

AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction

Authors: Adam Cicherski, Anna Lisiecka, and Norbert Dojer

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract

The success of pangenome-based approaches to genomics analysis depends largely on the existence of efficient methods for constructing pangenome graphs that are applicable to large genome collections. In the current paper we present AlfaPang, a new pangenome graph building algorithm. AlfaPang is based on a novel alignment-free approach that allows to construct pangenome graphs using significantly less computational resources than state-of-the-art tools. The code of AlfaPang is freely available at https://github.com/AdamCicherski/AlfaPang.

Cite as

Adam Cicherski, Anna Lisiecka, and Norbert Dojer. AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cicherski_et_al:LIPIcs.WABI.2024.23,
  author =	{Cicherski, Adam and Lisiecka, Anna and Dojer, Norbert},
  title =	{{AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.23},
  URN =		{urn:nbn:de:0030-drops-206673},
  doi =		{10.4230/LIPIcs.WABI.2024.23},
  annote =	{Keywords: pangenome, variation graph, genome alignment, population genomics}
}

Search Results

Documents authored by Lisiecka, Anna

Reconciling and Comparing Variation Graphs Using Homology Relations

Abstract

Cite as

AlfaPang: Alignment Free Algorithm for Pangenome Graph Construction

Abstract

Cite as

Thanks for your feedback!

Could not send message