Paper Info
Title
Efficient parallel construction of suffix trees for genomes larger than main memory
Abstract
The construction of suffix tree for very long sequences is essential for many applications, and it plays a central role in the bioinformatic domain. With the advent of modern sequencing technologies, biological sequence databases have grown dramatically. Also the methodologies required to analyze these data have become everyday more complex, requiring fast queries to multiple genomes. In this paper we presented Parallel Continuous Flow PCF, a parallel suffix tree construction method that is suitable for very long strings. We tested our method on the construction of suffix tree of the entire human genome, about 3GB. We showed that PCF can scale gracefully as the size of the input string grows. Our method can work with an efficiency of 90% with 36 processors and 55% with 172 processors. We can index the Human genome in 7 minutes using 172 nodes.
Year
DOI
Venue
2013
10.1145/2488551.2488579
EuroMPI
Keywords
DocType
Citations 
parallel suffix tree construction,bioinformatic domain,parallel continuous flow pcf,long string,central role,biological sequence databases,entire human genome,suffix tree,efficient parallel construction,long sequence,human genome,main memory,parallel algorithms
Conference
4
PageRank 
References 
Authors
0.40
22
2
Name
Order
Citations
PageRank
Matteo Comin119120.94
Montse Farreras216312.94