DocumentCode :
110782
Title :
An 
-Time Algorithm for Detecting Superbubbles
Author :
Wing-Kin Sung ; Sadakane, Kunihiko ; Shibuya, Tetsuo ; Belorkar, Abha ; Pyrogova, Iana
Author_Institution :
Dept. of Comput. Sci., Nat. Univ. of Singapore, Singapore, Singapore
Volume :
12
Issue :
4
fYear :
2015
fDate :
July-Aug. 1 2015
Firstpage :
770
Lastpage :
777
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.
Keywords :
bubbles; genomics; sequences; O(m log m)-time algorithm; assembly graphs; complex generalization; genome assembly graphs; quadratic time algorithm; sequencing errors; subgraph class; superbubble detection; Assembly; Bioinformatics; Computational biology; Genomics; IEEE transactions; Merging; Sequential analysis; Genome assembly; Next generation sequencing; Superbubble; genome assembly; next generation sequencing;
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2014.2385696
Filename :
6998850
Link To Document :
