Parallel biological sequence comparison using prefix computations

Srinivas Aluru, Natsuhiko Futamura, Kishan Mehrotra

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the International Parallel Processing Symposium, IPPS
PublisherIEEE Computer Society
Pages653-659
Number of pages7
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing - San Juan
Duration: Apr 12 1999Apr 16 1999

Other

OtherProceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing
CitySan Juan
Period4/12/994/16/99

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Parallel biological sequence comparison using prefix computations'. Together they form a unique fingerprint.

  • Cite this

    Aluru, S., Futamura, N., & Mehrotra, K. (1999). Parallel biological sequence comparison using prefix computations. In Proceedings of the International Parallel Processing Symposium, IPPS (pp. 653-659). IEEE Computer Society.