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

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

Contig Model for Variable-Order de Bruijn Graphs Díaz-Domínguez, Diego Martinello, Pierfrancesco Onodera, Taku Puglisi, Simon J. Salmela, Leena genome assembly de Bruijn Graph long reads Choosing an order for constructing a de Bruijn graph (DBG) is a crucial step in de novo assembly, as no single value allows complete genome reconstruction. The variable-order de Bruijn graph (voDBG) addresses this limitation by combining DBGs of multiple orders in a single structure connected by contextual relationships. This representation enables new connections to be identified or ambiguities to be resolved during assembly. However, voDBGs currently lack a formal definition of contigs. In this paper, we give the first formal definition of contigs for voDBGs. We show that, for a frequency range [𝓁,h] with 𝓁 > h/2, nodes whose labels occur with frequency f ∈ [𝓁, h] in the reads spell sequences of the genome with high probability under uniform sampling assumptions. We call these sequences (𝓁,h)-tigs. We also present an efficient algorithm to enumerate (𝓁,h)-tigs from a voDBG that accounts for homopolymer errors. Experiments on PacBio HiFi data show that our method significantly improves contiguity compared to unitigs in fixed-order DBGs while remaining considerably lighter than full genome assemblers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Díaz-Domínguez and Pierfrancesco Martinello and Taku Onodera and Simon J. Puglisi and Leena Salmela 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.4 urn:nbn:de:0030-drops-275080 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode