2026-07-22T14:20:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7661 2024-03-06T10:41:24Z ddc:004 open_access

Disentangled Long-Read De Bruijn Graphs via Optical Maps Alipanahi, Bahar Salmela, Leena Puglisi, Simon J. Muggli, Martin Boucher, Christina Positional de Bruijn graph Genome Assembly Long Read Data Optical maps While long reads produced by third-generation sequencing technology from, e.g, Pacific Biosciences have been shown to increase the quality of draft genomes in repetitive regions, fundamental computational challenges remain in overcoming their high error rate and assembling them efficiently. In this paper we show that the de Bruijn graph built on the long reads can be efficiently and substantially disentangled using optical mapping data as auxiliary information. Fundamental to our approach is the use of the positional de Bruijn graph and a succinct data structure for constructing and traversing this graph. Our experimental results show that over 97.7% of directed cycles have been removed from the resulting positional de Bruijn graph as compared to its non-positional counterpart. Our results thus indicate that disentangling the de Bruijn graph using positional information is a promising direction for developing a simple and efficient assembly algorithm for long reads. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bahar Alipanahi and Leena Salmela and Simon J. Puglisi and Martin Muggli and Christina Boucher 2017 Is Part Of LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2017.1 urn:nbn:de:0030-drops-76614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.1 eng https://creativecommons.org/licenses/by/3.0/legalcode