We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs.
- Authors
Kundeti, Vamsi K; Rajasekaran, Sanguthevar; Dinh, Hieu; Vaughn, Matthew; Thapar, Vishal
- Abstract
Assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. Algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. The first class uses an overlap/string graph and the second type uses a de Bruijn graph. However with the recent advances in short read sequencing technology, de Bruijn graph based algorithms seem to play a vital role in practice. Efficient algorithms for building these massive de Bruijn graphs are very essential in large sequencing projects based on short reads. In an earlier work, an O(n/p) time parallel algorithm has been given for this problem. Here n is the size of the input and p is the number of processors. This algorithm enumerates all possible bi-directed edges which can overlap with a node and ends up generating Θ(nΣ) messages (Σ being the size of the alphabet).
- Publication
BMC bioinformatics, 2010, Vol 11, p560
- ISSN
1471-2105
- Publication type
Journal Article
- DOI
10.1186/1471-2105-11-560