Parallel biological sequence comparison using prefix computations

✍ Scribed by Srinivas Aluru; Natsuhiko Futamura; Kishan Mehrotra

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 217 KB
• Volume: 63
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1016/s0743-7315(03)00010-8

✦ Synopsis

We present practical parallel algorithms using prefix computations for various problems that arise in pairwise comparison of biological sequences. We consider both constant and affine gap penalty functions, full-sequence and subsequence matching, and space-saving algorithms. Commonly used sequential algorithms solve the sequence comparison problems in OðmnÞ time and Oðm þ nÞ space, where m and n are the lengths of the sequences being compared. All the algorithms presented in this paper are time optimal with respect to the sequential algorithms and can use Oð n log n Þ processors where n is the length of the larger sequence. While optimal parallel algorithms for many of these problems are known, we use a simple framework and demonstrate how these problems can be solved systematically using repeated parallel prefix operations. We also present a space-saving algorithm that uses Oðm þ n p Þ space and runs in optimal time where p is the number of the processors used. We implemented the parallel space-saving algorithm and provide experimental results on an IBM SP-2 and a Pentium cluster.