{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T04:05:08Z","timestamp":1783483508951,"version":"3.55.0"},"reference-count":12,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T00:00:00Z","timestamp":1555459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007148","name":"Bundesministerium f\u00fcr Wissenschaft und Forschung","doi-asserted-by":"publisher","award":["BMBF 01IS14014B"],"award-info":[{"award-number":["BMBF 01IS14014B"]}],"id":[{"id":"10.13039\/501100007148","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. Linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github.<\/jats:p>","DOI":"10.3390\/a12040081","type":"journal-article","created":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T11:07:11Z","timestamp":1555499231000},"page":"81","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Direct Superbubble Detection"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1128-3408","authenticated-orcid":false,"given":"Fabian","family":"G\u00e4rtner","sequence":"first","affiliation":[{"name":"Competence Center for Scalable Data Services and Solutions Dresden\/Leipzig, Universit\u00e4t Leipzig, Augustusplatz 12, D-04107 Leipzig, Germany"},{"name":"Bioinformatics Group, Department of Computer Science, Universit\u00e4t Leipzig, H\u00e4rtelstra\u00dfe 16\u201318, D-04107 Leipzig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[{"name":"Competence Center for Scalable Data Services and Solutions Dresden\/Leipzig, Universit\u00e4t Leipzig, Augustusplatz 12, D-04107 Leipzig, Germany"},{"name":"Bioinformatics Group, Department of Computer Science, Universit\u00e4t Leipzig, H\u00e4rtelstra\u00dfe 16\u201318, D-04107 Leipzig, Germany"},{"name":"Interdisciplinary Center for Bioinformatics, German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, and Leipzig Research Center for Civilization Diseases, University Leipzig, D-04107 Leipzig, Germany"},{"name":"Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, Germany"},{"name":"Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstra\u00dfe 17, A-1090 Wien, Austria"},{"name":"Facultad de Ciencias, Universidad National de Colombia, Sede Bogot\u00e1, Colombia"},{"name":"Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1089\/cmb.2017.0251","article-title":"Superbubbles, Ultrabubbles, and Cacti","volume":"25","author":"Paten","year":"2018","journal-title":"J. Comput. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/978-3-642-40453-5_26","article-title":"Detecting superbubbles in assembly graphs","volume":"Volume 8126","author":"Darling","year":"2013","journal-title":"Proceedings of the International Workshop on Algorithms in Bioinformatics"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1146\/annurev-genom-090314-050032","article-title":"The Theory and Practice of Genome Sequence Assembly","volume":"16","author":"Simpson","year":"2015","journal-title":"Annu. Rev. Genomics Hum. Genet."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.biosystems.2017.03.003","article-title":"Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment","volume":"156\u2013157","author":"Baichoo","year":"2017","journal-title":"Biosystems"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1109\/TCBB.2014.2385696","article-title":"An O(mlogm)-time algorithm for detecting superbubbles","volume":"12","author":"Sung","year":"2015","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.tcs.2015.10.021","article-title":"Linear-time superbubble identification algorithm for genome assembly","volume":"609","author":"Brankovic","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1186\/s13015-018-0134-3","article-title":"Superbubbles revisited","volume":"13","author":"Stadler","year":"2018","journal-title":"Algorithms Mol. Biol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-First Search and Linear Graph Algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/978-3-319-68705-6_2","article-title":"On Bubble Generators in Directed Graphs","volume":"Volume 10520","author":"Bodlaender","year":"2017","journal-title":"Graph-Theoretic Concepts in Computer Science"},{"key":"ref_10","unstructured":"Hagberg, A., Schult, D.A., and Swart, P. (2008, January 19\u201324). Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy 2008), Pasadena, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/s13015-018-0133-4","article-title":"Coordinate Systems for Supergenomes","volume":"13","author":"Stadler","year":"2018","journal-title":"Algorithms Mol. Biol."},{"key":"ref_12","unstructured":"Leskovec, J., and Krevl, A. (2018, November 26). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/81\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:46:10Z","timestamp":1760186770000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,17]]},"references-count":12,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["a12040081"],"URL":"https:\/\/doi.org\/10.3390\/a12040081","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,17]]}}}