Paper Info
Title
Parallel Genomic Alignments on the Cell Broadband Engine
Abstract
Genomic alignments, as a means to uncover evolutionary relationships among organisms, are a fundamental tool in computational biology. There is considerable recent interest in using the Cell Broadband Engine, a heterogeneous multicore chip that provides high performance, for biological applications. However, work in genomic alignments so far has been limited to computing optimal alignment scores using quadratic space for the basic global/local alignment problem. In this paper, we present a comprehensive study of developing alignment algorithms on the Cell, exploiting its thread and data level parallelism features. First, we develop a parallel implementation on the Cell 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. Spliced alignments are useful in aligning mRNA sequences with corresponding genomic sequences to uncover the 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 16 Synergistic Processing Elements of the IBM QS20 dual-Cell blade system.
Year
DOI
Venue
2009
10.1109/TPDS.2008.254
IEEE Trans. Parallel Distrib. Syst.
Keywords
Field
DocType
cell broadband engine,present cell implementation,syntenic alignment,local alignment problem,optimal alignment score,spliced alignment,computes optimal alignment,advanced alignment technique,parallel genomic alignments,alignment algorithm,genomic alignment,organisms,chip,data level parallelism,parallel algorithms,engines,sequences,local alignment,genomics,linear space,parallel algorithm,multicore processing,genetics,pattern matching,computational biology,genome sequence,gene structure,quadratic programming,bioinformatics
Computer science,Parallel algorithm,Linear space,Theoretical computer science,Genomics,Data parallelism,Smith–Waterman algorithm,Quadratic programming,Pattern matching,Multi-core processor,Distributed computing
Journal
Volume
Issue
ISSN
20
11
1045-9219
Citations 
PageRank 
References 
4
0.42
15
Authors
2
Name
Order
Citations
PageRank
Abhinav Sarje1355.71
Aluru, Srinivas21166122.83