Direct superbubble detection
type: Item
instance of: scholarly article
title: Direct superbubble detection
zbMATH Open document ID: 1461.68152
author: Fabian Gärtner
author: Peter F. Stadler
published in: Algorithms
publication date: 2019-07-08T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7077456
zbMATH Keywords: superbubble
zbMATH Keywords: depth-first search
zbMATH Keywords: cycles
zbMATH Keywords: linear-time algorithm
describes a project that uses: NetworkX
describes a project that uses: SciPy
describes a project that uses: SNAP
describes a project that uses: GitHub
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12040081
OpenAlex ID: W2937634726
cites work: Superbubbles, ultrabubbles and cacti
cites work: Linear-time superbubble identification algorithm for genome assembly
cites work: Depth-First Search and Linear Graph Algorithms
cites work: On bubble generators in directed graphs
Wikidata QID: Q128038794
DOI: 10.3390/A12040081
Recommended article: SUPER-screening
Recommended article: Super-resolution radar
Recommended article: Detection of supernova explosions with IceCube
Recommended article: Coherent and incoherent neutral current scattering for supernova detection
Recommended article: Q4531734
description: scientific article; zbMATH DE number 7077456