Linear-time superbubble identification algorithm for genome assembly

DOI10.1016/j.tcs.2015.10.021zbMath1331.92091arXiv1505.04019OpenAlexW1750841778WikidataQ112664257 ScholiaQ112664257MaRDI QIDQ897907

Solon P. Pissis, Ritu Kundu, Manal Mohamed, Ljiljana Brankovic, Fatima Vayani, Costas S. Iliopoulos

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.04019

zbMATH Keywords

de Bruijn graphsgenome assemblysuperbubble

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10)

Related Items

Describing the local structure of sequence graphs, A Family of Tree-Based Generators for Bubbles in Directed Graphs, A family of tree-based generators for bubbles in directed graphs, Direct superbubble detection, On bubble generators in directed graphs, Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis

Uses Software

• ALLPATHS
• Velvet

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-disjoint spanning trees and depth-first search
• A simple linear-space data structure for constant-time range minimum query
• Fast Algorithms for Finding Nearest Common Ancestors
• An Eulerian path approach to DNA fragment assembly
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE