2026-08-27T21:19:52Z https://drops.dagstuhl.de/oai

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

Reconciling and Comparing Variation Graphs Using Homology Relations Lisiecka, Anna Cicherski, Adam Dojer, Norbert Pangenome Variation Graph Genome Homology 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Lisiecka and Adam Cicherski and Norbert Dojer 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.29 urn:nbn:de:0030-drops-275332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.29 eng https://creativecommons.org/licenses/by/4.0/legalcode