A space-efficient algorithm for local similarities

Xiaoqiu Huang; Ross C. Hardison; Webb Miller

doi:10.1093/bioinformatics/6.4.373

A space-efficient algorithm for local similarities

Xiaoqiu Huang, Ross C. Hardison, Webb Miller

Research output: Contribution to journal › Article › peer-review

169 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	373-381
Number of pages	9
Journal	Bioinformatics
Volume	6
Issue number	4
DOIs	https://doi.org/10.1093/bioinformatics/6.4.373
State	Published - Oct 1990

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1093/bioinformatics/6.4.373

Cite this

@article{54adaa55c0644bafa62a5064731586fc,

title = "A space-efficient algorithm for local similarities",

abstract = "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.",

author = "Xiaoqiu Huang and Hardison, {Ross C.} and Webb Miller",

note = "Funding Information: The authors thank William Pearson for providing the LFASTA program and helping us understand h. Both referees made suggestions that improved the paper. X.H. and W.M. were supported by grant LM05110 from the National Library of Medicine; R.C.H. is supported by PHS grant DK27635 and an RCDA DK0I589.",

year = "1990",

month = oct,

doi = "10.1093/bioinformatics/6.4.373",

language = "English (US)",

volume = "6",

pages = "373--381",

journal = "Bioinformatics",

issn = "1367-4803",

publisher = "Oxford University Press",

number = "4",

}

TY - JOUR

T1 - A space-efficient algorithm for local similarities

AU - Huang, Xiaoqiu

AU - Hardison, Ross C.

AU - Miller, Webb

N1 - Funding Information: The authors thank William Pearson for providing the LFASTA program and helping us understand h. Both referees made suggestions that improved the paper. X.H. and W.M. were supported by grant LM05110 from the National Library of Medicine; R.C.H. is supported by PHS grant DK27635 and an RCDA DK0I589.

PY - 1990/10

Y1 - 1990/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025043566&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025043566&partnerID=8YFLogxK

U2 - 10.1093/bioinformatics/6.4.373

DO - 10.1093/bioinformatics/6.4.373

M3 - Article

C2 - 2257499

AN - SCOPUS:0025043566

SN - 1367-4803

VL - 6

SP - 373

EP - 381

JO - Bioinformatics

JF - Bioinformatics

IS - 4

ER -

A space-efficient algorithm for local similarities

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this