Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T13:18:02.561Z Has data issue: false hasContentIssue false

Superbubbles as an empirical characteristic of directed networks

Published online by Cambridge University Press:  01 September 2020

Fabian Gärtner
Affiliation:
Competence Center for Scalable Data Services and Solutions Dresden/Leipzig (scaDS), Universität Leipzig, Augustusplatz 12, D-04107 Leipzig, Germany (e-mail: fabian@bioinf.uni-leipzig.de)Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)
Felix Kühnl
Affiliation:
Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany
Carsten R. Seemann
Affiliation:
Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, GermanyMax Planck Institute for Mathematics in the Sciences, Inselstraße 22, D-04103 Leipzig, Germany
Christian Höner Zu Siederdissen
Affiliation:
Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany
Peter F. Stadler*
Affiliation:
Competence Center for Scalable Data Services and Solutions Dresden/Leipzig (scaDS), Universität Leipzig, Augustusplatz 12, D-04107 Leipzig, Germany (e-mail: fabian@bioinf.uni-leipzig.de)Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, GermanyMax Planck Institute for Mathematics in the Sciences, Inselstraße 22, D-04103 Leipzig, GermanyGerman Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, GermanyLeipzig Research Center for Civilization Diseases, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, GermanyInstitute for Theoretical Chemistry, University of Vienna, Währingerstraße17, A-1090 Wien, AustriaFacultad de Ciencias, Universidad National de Colombia, Sede Bogotá, ColombiaSanta Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA
The Students of the Graphs and Networks Computer Lab 2018/19
Affiliation:
Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany (e-mails: carsten@bioinf.uni-leipzig.de, felix@bioinf.uni-leipzig.de, choener@bioinf.uni-leipzig.de)
*
*Corresponding author. Email: studla@bioinf.uni-leipzig.de
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.

Information

Type
Research Article
Copyright
© The Author(s), 2020. Published by Cambridge University Press
Supplementary material: PDF

Gärtner et al. Supplementary Materials

Gärtner et al. Supplementary Materials

Download Gärtner et al. Supplementary Materials(PDF)
PDF 142.3 KB