Name
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 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)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlogm)-time algorithm by Sung et al. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.10.021 | Theoretical Computer Science |
Keywords | Field | DocType |
Genome assembly,de Bruijn graphs,Superbubble | Genome,Discrete mathematics,Combinatorics,Vertex (geometry),Algorithm,Directed acyclic graph,Superbubble,DNA sequencing,De Bruijn sequence,Time complexity,Sequence assembly,Mathematics | Journal |
Volume | Issue | ISSN |
609 | P2 | 0304-3975 |
Citations | PageRank | References |
5 | 0.67 | 6 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ljiljana Brankovic | 1 | 333 | 58.74 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Ritu Kundu | 3 | 17 | 3.76 |
| Manal Mohamed | 4 | 102 | 12.62 |
| Solon P. Pissis | 5 | 281 | 57.09 |
| Fatima Vayani | 6 | 25 | 3.85 |