A space-efficient algorithm for local similarities

Xiaoqiu Huang, Ross C. Hardison, Webb Miller

Research output: Contribution to journalArticlepeer-review

169 Scopus citations


Existing dynamic-programming algorithms for identifying similar regions of two sequences require time and space proportional to the product of the sequence lengths. Often this space requirement is more limiting than the time requirement. We describe a dynamic-programming local-similarity algorithm that needs only space proportional to the sum of the sequence lengths. The method can also find repeats within a single long sequence. To illustrate the algorithm's potential, we discuss comparison of a 73 360 nucleotide sequence containing the human β-like globin gene cluster and a corresponding 44 594 nucleotide sequence for rabbit, a problem well beyond the capabilities of other dynamic-programming software.

Original languageEnglish (US)
Pages (from-to)373-381
Number of pages9
Issue number4
StatePublished - Oct 1990

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 'A space-efficient algorithm for local similarities'. Together they form a unique fingerprint.

Cite this