Superbubbles as an empirical characteristic of directed networks
Authors:
- Fabian GärtnerFGFabian Gärtner
- Felix KühnlFKFelix Kühnl
- Carsten R. SeemannCSCarsten R. Seemann
- The Students Of The Graphs And Networks Computer Lab 2018/19T2The Students Of The Graphs And Networks Computer Lab 2018/19
- Christian Höner Zu SiederdissenCSChristian Höner Zu Siederdissen
- Peter F. StadlerPeter F. Stadler
- 1 September 2020
- journal article
- research article
- Published by Cambridge University Press (CUP) in Network Science
- Vol. 9 (1) , 49-58
Abstract
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.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Network sciencePhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013
- GenomeRing: alignment visualization based on SuperGenome coordinatesBioinformatics, 2012
- Edge direction and the structure of networksProceedings of the National Academy of Sciences, 2010
- Complete Alternative Splicing Events Are Bubbles in Splicing GraphsJournal of Computational Biology, 2009
- Towards a Theory of Scale-Free Graphs: Definition, Properties, and ImplicationsInternet Mathematics, 2005
- Mixing patterns in networksPhysical Review E, 2003
- Realizing degree imbalances in directed graphsDiscrete Mathematics, 2001
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Eccentricity and centrality in networksSocial Networks, 1995
- Eigenvalues of the Laplacian of a graph∗Linear and Multilinear Algebra, 1985