Paper Info
Title
Parallel biological sequence alignments on the Cell Broadband Engine
Abstract
Sequence alignment and its many variants are a fundamental tool in computational biology. There is considerable recent interest in using the Cell Broadband Engine, a heterogenous multi-core chip that provides high performance, for biological applications. However, work so far has been limited to computing optimal alignment scores using quadratic space under the basic global/local alignment algorithm. In this paper we present a comprehensive study of developing sequence alignment algorithms on the Cell exploiting its thread and data level parallelism features. First, we develop a Cell implementation that computes optimal alignments and adopts Hirschberg's linear space technique. The former is essential as merely computing optimal alignment scores is not useful while the latter is needed to permit alignments of longer sequences. We then present Cell implementations of two advanced alignment techniques - spliced alignments and syntenic alignments. In a spliced alignment, consecutive non-overlapping portions of a sequence align with ordered non-overlapping, but non-consecutive portions of another sequence. Spliced alignments are useful in aligning mRNA sequences with corresponding genomic sequences to uncover gene structure. Syntenic alignments are used to discover conserved exons and other sequences between long genomic sequences from different organisms. We present experimental results for these three types of alignments on the Cell BE and report speedups of about 4 on six SPUs on the Playstation 3, when compared to the respective best serial algorithms on the Cell BE and the Pentium 4 processor.
Year
DOI
Venue
2008
10.1109/IPDPS.2008.4536328
IPDPS
Keywords
Field
DocType
biology computing,parallel processing,cell broadband engine,computational biology,heterogenous multi-core chip,parallel biological sequence alignments,sequence alignment
Sequence alignment,Alignment-free sequence analysis,Computer science,Parallel computing,Linear space,Algorithm,Genomics,Theoretical computer science,Data parallelism,Pentium,Smith–Waterman algorithm,Multiple sequence alignment
Conference
Citations 
PageRank 
References 
7
0.63
8
Authors
2
Name
Order
Citations
PageRank
Abhinav Sarje1355.71
Aluru, Srinivas21166122.83