## 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. The best known sequential algorithms solve these problems in O(mn) time and O(m+n) space, where m and n are the lengths of the two sequences. All the algorithms presented in this paper are time optimal with respect to the best known 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.

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

Title of host publication | Proceedings of the International Parallel Processing Symposium, IPPS |

Publisher | IEEE Computer Society |

Pages | 653-659 |

Number of pages | 7 |

State | Published - 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing - San Juan Duration: Apr 12 1999 → Apr 16 1999 |

### Other

Other | Proceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing |
---|---|

City | San Juan |

Period | 4/12/99 → 4/16/99 |

## ASJC Scopus subject areas

- Hardware and Architecture