• DocumentCode
    110782
  • Title

    An bm{O(m, \\log , m)} -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
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=110782