King's College London

Research portal

Linear-time superbubble identification algorithm for genome assembly

Research output: Contribution to journalArticle

Original languageUndefined/Unknown
Pages (from-to)374-383
Number of pages10
JournalTheoretical Computer Science
Volume609, Part 2
Early online date23 Oct 2015
Publication statusPublished - 4 Jan 2016


King's Authors


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 utilise 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)O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlog⁡m)O(mlog⁡m)-time algorithm by Sung et al.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454