Optimised fine and coarse parallelism for sequence homology search.
New biological experimental techniques are continuing to generate large amounts of data using DNA, RNA, human genome and protein sequences. The quantity and quality of data from these experiments makes analyses of their results very time-consuming, expensive and impractical. Searching on DNA and protein databases using sequence comparison algorithms has become one of the most powerful techniques to better understand the functionality of particular DNA, RNA, genome, or protein sequence. This paper presents a technique to effectively combine fine and coarse grain parallelism using general-purpose processors for sequence homology database searches. The results show that the classic Smith-Waterman sequence alignment algorithm achieves super linear performance with proper scheduling and multi-level parallel computing at no additional cost.
Electrical and Computer Engineering, Wayne State University, Detroit, MI 48202, USA. meng@ece.eng.wayne.edu
Xiandong
X
Meng
Vipin
V
Chaudhary
D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D003201:Computers; D003205:Computing Methodologies; D004247:DNA / Q000737:chemistry; D030541:Databases, Genetic; D030562:Databases, Protein; D016678:Genome; D006801:Humans; D016247:Information Storage and Retrieval; D012313:RNA / Q000737:chemistry; D015203:Reproducibility of Results; D016415:Sequence Alignment; D017385:Sequence Homology; D012984:Software
D012313:RNA; D004247:DNA