Parallelization of a local similarity algorithm

Xiaoqiu Huang, Webb Miller, Scott Schwartz, Ross C. Hardison

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


The local similarity problem is to determine the similar regions within two given sequences. We recently developed a dynamic programming algorithm for the local similarity problem that requires only space proportional to the sum of the two sequence lengths, whereas earlier methods use space proportional to the product of the lengths. In this paper, we describe how to parallelize the new algorithm and present results of experimental studies on an Intel hypercube. The parallel method provides rapid, high-resolution alignments for users of our software toolkit for pairwise sequence comparison, as illustrated here by a comparison of the chloroplast genomes of tobacco and liverwort.

Original languageEnglish (US)
Pages (from-to)155-165
Number of pages11
Issue number2
StatePublished - Apr 1992

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Parallelization of a local similarity algorithm'. Together they form a unique fingerprint.

Cite this