Linear-time superbubble identification algorithm for genome assembly

DOI10.1016/J.TCS.2015.10.021zbMATH Open1331.92091arXiv1505.04019OpenAlexW1750841778WikidataQ112664257 ScholiaQ112664257MaRDI QIDQ897907FDOQ897907

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)

Abstract: DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilize de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble. In this paper, we propose an O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n nodes and m (directed) edges, improving the best-known O(m log m)-time algorithm by Sung et al.

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

zbMATH Keywords

de Bruijn graphsgenome assemblysuperbubble

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms
• A simple linear-space data structure for constant-time range minimum query
• Title not available (Why is that?)
• Edge-disjoint spanning trees and depth-first search
• Fast Algorithms for Finding Nearest Common Ancestors
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• An Eulerian path approach to DNA fragment assembly

Cited In (7)

• 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
• Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis
• On bubble generators in directed graphs
• Economic genome assembly from low coverage illumina and nanopore data
• Direct superbubble detection

Uses Software

• ALLPATHS
• Velvet

This page was built for publication: Linear-time superbubble identification algorithm for genome assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897907)