Title: Optimised fine and coarse parallelism for sequence homology search

Authors: Xiandong Meng, Vipin Chaudhary

Addresses: Electrical and Computer Engineering, Wayne State University, Detroit, MI 48202, USA. ' Institute for Scientific Computing, Wayne State University, Detroit, MI 48202, USA

Abstract: 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.

Keywords: sequence homology search; FASTA; Smith-Waterman algorithm; SSE2; fine grain parallelism; coarse grain parallelism; cluster computing; DNA sequences; RNA sequences; genome sequences; protein sequences; sequence alignment; scheduling; parallel computing; bioinformatics research; bioinformatics applications; high performance computing.

DOI: 10.1504/IJBRA.2006.011041

International Journal of Bioinformatics Research and Applications, 2006 Vol.2 No.4, pp.430 - 441

Published online: 05 Oct 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article