title: An O(m log m)-Time Algorithm for Detecting Superbubbles.
abstract: In genome assembly graphs, motifs such as tips, bubbles, and cross links are studied in order to find sequencing errors and to understand the nature of the genome. Superbubble, a complex generalization of bubbles, was recently proposed as an important subgraph class for analyzing assembly graphs. At present, a quadratic time algorithm is known. This paper gives an O(m log m)-time algorithm to solve this problem for a graph with m edges.
authors.forename: Wing-Kin
authors.initials: WK
authors.lastname: Sung
authors.forename: Kunihiko
authors.initials: K
authors.lastname: Sadakane
authors.forename: Tetsuo
authors.initials: T
authors.lastname: Shibuya
authors.forename: Abha
authors.initials: A
authors.lastname: Belorkar
authors.forename: Iana
authors.initials: I
authors.lastname: Pyrogova
mesh_terms: D000465:Algorithms; D023281:Genomics / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*