Genome assembly with variable order de Bruijn graphs

Genome assembly with variable-order de Bruijn graphs⋆ | bioRxiv Skip to main content Home About Submit ALERTS / RSS Search for this keyword Advanced Search New Results Genome assembly with variable-order de Bruijn graphs ⋆ View ORCID Profile Diego Díaz-Domínguez , Pierfrancesco Martinello , Taku Onodera , Simon J. Puglisi , View ORCID Profile Leena Salmela doi: https://doi.org/10.1101/2022.09.06.506758 Diego Díaz-Domínguez 1 Department of Computer Science, University of Helsinki , Finland Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Diego Díaz-Domínguez Pierfrancesco Martinello 1 Department of Computer Science, University of Helsinki , Finland Find this author on Google Scholar Find this author on PubMed Search for this author on this site For correspondence: pierfrancesco.martinello{at}helsinki.fi Taku Onodera 1 Department of Computer Science, University of Helsinki , Finland Find this author on Google Scholar Find this author on PubMed Search for this author on this site Simon J. Puglisi 1 Department of Computer Science, University of Helsinki , Finland Find this author on Google Scholar Find this author on PubMed Search for this author on this site Leena Salmela 1 Department of Computer Science, University of Helsinki , Finland Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Leena Salmela Abstract Full Text Info/History Metrics Preview PDF 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 fixed-order DBGs while remaining considerably lighter than full genome assemblers. Competing Interest Statement The authors have declared no competing interest. Footnotes diego.diaz{at}helsinki.fi , pierfrancesco.martinello{at}helsinki.fi , simon.puglisi{at}helsinki.fi , leena.salmela{at}helsinki.fi ⋆ This work was funded by Academy of Finland via grants 323233 and 370538 (to LS). This version is a complete rewrite of the manuscript, with new material, figures, and experiments. The source code associated with the maniscript was also substantially modified. Funder Information Declared Academy of Finland via grants 323233 and 370538 (to LS). Copyright The copyright holder for this preprint is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made available under a CC-BY-NC-ND 4.0 International license . Back to top Previous Next Posted March 16, 2026. Download PDF Email Thank you for your interest in spreading the word about bioRxiv. NOTE: Your email address is requested solely to identify you as the sender of this article. Your Email * Your Name * Send To * Enter multiple addresses on separate lines or separate them with commas. You are going to email the following Genome assembly with variable-order de Bruijn graphs⋆ Message Subject (Your Name) has forwarded a page to you from bioRxiv Message Body (Your Name) thought you would like to see this page from the bioRxiv website. Your Personal Message CAPTCHA This question is for testing whether or not you are a human visitor and to prevent automated spam submissions. Share Genome assembly with variable-order de Bruijn graphs ⋆ Diego Díaz-Domínguez , Pierfrancesco Martinello , Taku Onodera , Simon J. Puglisi , Leena Salmela bioRxiv 2022.09.06.506758; doi: https://doi.org/10.1101/2022.09.06.506758 Share This Article: Copy Citation Tools Genome assembly with variable-order de Bruijn graphs ⋆ Diego Díaz-Domínguez , Pierfrancesco Martinello , Taku Onodera , Simon J. Puglisi , Leena Salmela bioRxiv 2022.09.06.506758; doi: https://doi.org/10.1101/2022.09.06.506758 Citation Manager Formats BibTeX Bookends EasyBib EndNote (tagged) EndNote 8 (xml) Medlars Mendeley Papers RefWorks Tagged Ref Manager RIS Zotero Tweet Widget Facebook Like Google Plus One Subject Area Bioinformatics Subject Areas All Articles Animal Behavior and Cognition (7996) Biochemistry (18704) Bioengineering (14817) Bioinformatics (44313) Biophysics (22543) Cancer Biology (19661) Cell Biology (26829) Clinical Trials (138) Developmental Biology (13922) Ecology (20950) Epidemiology (2067) Evolutionary Biology (25404) Genetics (16137) Genomics (23455) Immunology (18657) Microbiology (42370) Molecular Biology (18015) Neuroscience (93236) Paleontology (696) Pathology (2975) Pharmacology and Toxicology (5079) Physiology (8092) Plant Biology (15963) Scientific Communication and Education (2094) Synthetic Biology (4546) Systems Biology (10212) Zoology (2381)

Related documents

• Pan1c : a pipeline to easily build chromosome-level pangenome graphs#290738
• Structural basis for Retriever-SNX17 assembly and endosomal sorting#334308
• Evolution of whole genomes through inversions : models and algorithms for duplicates, ancestors, and edit scenarios#1100184
• A computational framework for designing micron-scale crisscross DNA megastructures / Matthew Aquilina, Florian Katzmeier, Minke A. D. Nijenhuis, Siyuan Stella Wang, Corey Becker, Yichen Zhao, Su Hyun Seok, Julie Finkel, Huangchen Cui, Jaewon Lee, Seungwoo Lee, William M. Shih#623867
• Strand algebras for DNA computing#490049