DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.4

Contig Model for Variable-Order de Bruijn Graphs

Authors: Diego Díaz-Domínguez, Pierfrancesco Martinello, Taku Onodera, Simon J. Puglisi, and Leena Salmela

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

Abstract

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.

Cite as

Diego Díaz-Domínguez, Pierfrancesco Martinello, Taku Onodera, Simon J. Puglisi, and Leena Salmela. Contig Model for Variable-Order de Bruijn Graphs. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{diazdominguez_et_al:LIPIcs.WABI.2026.4,
  author =	{D{\'\i}az-Dom{\'\i}nguez, Diego and Martinello, Pierfrancesco and Onodera, Taku and Puglisi, Simon J. and Salmela, Leena},
  title =	{{Contig Model for Variable-Order de Bruijn Graphs}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{4:1--4:19},
  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.4},
  URN =		{urn:nbn:de:0030-drops-275080},
  doi =		{10.4230/LIPIcs.WABI.2026.4},
  annote =	{Keywords: genome assembly, de Bruijn Graph, long reads}
}

Search Results

Documents authored by Martinello, Pierfrancesco

Contig Model for Variable-Order de Bruijn Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message