Parallelization of a local similarity algorithm

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

doi:10.1093/bioinformatics/8.2.155

Parallelization of a local similarity algorithm

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

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

24 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	155-165
Number of pages	11
Journal	Bioinformatics
Volume	8
Issue number	2
DOIs	https://doi.org/10.1093/bioinformatics/8.2.155
State	Published - Apr 1992

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/8.2.155

Cite this

@article{2e097f1cc72e404da9f82b20803b71bb,

title = "Parallelization of a local similarity algorithm",

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

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

note = "Funding Information: The authors are very grateful to the anonymous referees for the helpful suggestions. X.H., W.M. and S.S. were supported in part by grant R01 LM05110 from the National Library of Medicine. R.C.H. was supported by PHS grant DK27635 and an RCDA DK01589.",

year = "1992",

month = apr,

doi = "10.1093/bioinformatics/8.2.155",

language = "English (US)",

volume = "8",

pages = "155--165",

journal = "Bioinformatics",

issn = "1367-4803",

publisher = "Oxford University Press",

number = "2",

}

TY - JOUR

T1 - Parallelization of a local similarity algorithm

AU - Huang, Xiaoqiu

AU - Miller, Webb

AU - Schwartz, Scott

AU - Hardison, Ross C.

N1 - Funding Information: The authors are very grateful to the anonymous referees for the helpful suggestions. X.H., W.M. and S.S. were supported in part by grant R01 LM05110 from the National Library of Medicine. R.C.H. was supported by PHS grant DK27635 and an RCDA DK01589.

PY - 1992/4

Y1 - 1992/4

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

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

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

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

U2 - 10.1093/bioinformatics/8.2.155

DO - 10.1093/bioinformatics/8.2.155

M3 - Article

C2 - 1591611

AN - SCOPUS:0026519753

SN - 1367-4803

VL - 8

SP - 155

EP - 165

JO - Bioinformatics

JF - Bioinformatics

IS - 2

ER -

Parallelization of a local similarity algorithm

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this