Name
Abstract | ||
|---|---|---|
Genome indexing is the basis for many bioinformatics applications. Read mapping(sequence alignment) is one such application where the goal is to align millions of short reads against reference genome. Several tools are available for read mapping which rely on different indexing techniques to expedite the alignment process. However, many of these contemporary alignment programs are sequential, memory intensive and cannot be easily scaled for larger genomes. Suffix tree is one of the most widely used data structures for indexing strings (genomes). Building a scalable suffix-tree based tool is particularly challenging due to the difficulties involved in parallel construction of the suffix tree. Several suffix tree construction techniques have been proposed till date with focus on space-time tradeoff. Most of these existing works address the construction issue for uniprocessor and cannot be easily extended to utilize modern multi-processor systems. In this paper we investigate and propose a MapReduce based parallel construction of suffix tree. We demonstrate the performance of the algorithm over commodity cluster using up to 32 nodes each having 8GB of primary memory. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/PADSW.2014.7097867 | Parallel and Distributed Systems |
Keywords | Field | DocType |
bioinformatics,data structures,genomics,indexing,parallel processing,trees (mathematics),MapReduce based parallel suffix tree construction,bioinformatics application,commodity cluster,data structure,genome indexing technique,human genome,multiprocessor system,read mapping application,sequence alignment application,space-time tradeoff,uniprocessor system,genome,indexing,map-reduce,parallel,suffix tree | Genome,Data structure,Uniprocessor system,Computer science,Parallel computing,Search engine indexing,Theoretical computer science,Suffix tree,Compressed suffix array,Reference genome,Scalability | Conference |
ISSN | Citations | PageRank |
1521-9097 | 1 | 0.36 |
References | Authors | |
11 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Umesh Chandra Satish | 1 | 1 | 0.36 |
| Praveenkumar Kondikoppa | 2 | 12 | 2.83 |
| Seung-Jong Park | 3 | 319 | 31.12 |
| Manish Patil | 4 | 71 | 7.46 |
| Rahul Shah | 5 | 1059 | 61.31 |