## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 264-272 |

Number of pages | 9 |

Journal | Journal of Parallel and Distributed Computing |

Volume | 63 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1 2003 |

## Keywords

- Computational biology
- Parallel algorithms
- Parallel prefix
- Sequence alignments
- Space-efficient

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence