Skip Navigation

This Article
Right arrow Full Text (Print PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Huang, X.
Right arrow Articles by Miller, W.
Right arrow Search for Related Content
PubMed
Right arrow Articles by Huang, X.
Right arrow Articles by Miller, W.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© IRL Press

A space-efficient algorithm for local similarities

Xiaoqiu Huang , Ross C. Hardison 1 and Webb Miller 2

Department of Computer Science, Michigan Technological University Houghton, Ml 49931
1Department of Molecular and Cell Biology USA
2Department of Computer Science, The Pennsylvania State University, University Park PA 16802. USA

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.

Received on January 29, 1990; accepted on May 30, 1990

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 BioinformaticsHome page
S. Wong and M. A. Ragan
MACHOS: Markov clusters of homologous subsequences
Bioinformatics, July 1, 2008; 24(13): i77 - i85.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
A.-L. Abraham, E. P. C. Rocha, and J. Pothier
Swelfe: a detector of internal repeats in sequences and structures
Bioinformatics, July 1, 2008; 24(13): 1536 - 1537.
[Abstract] [Full Text] [PDF]

Home page
 J. Bacteriol.Home page
L. Neff, S. Daher, P. Muzzin, U. Spenato, F. Gulacar, C. Gabay, and S. Bas
Molecular Characterization and Subcellular Localization of Macrophage Infectivity Potentiator, a Chlamydia trachomatis Lipoprotein
J. Bacteriol., July 1, 2007; 189(13): 4739 - 4748.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
J. Zhang, R. P. Finney, W. Rowe, M. Edmonson, S. H. Yang, T. Dracheva, J. Jen, J. P. Struewing, and K. H. Buetow
Systematic analysis of genetic alterations in tumors using Cancer Genome WorkBench (CGWB)
Genome Res., July 1, 2007; 17(7): 1111 - 1117.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
Y.-m. Huang and C. Bystroff
Improved pairwise alignments of proteins in the Twilight Zone using local structure predictions
Bioinformatics, February 15, 2006; 22(4): 413 - 422.
[Abstract] [Full Text] [PDF]

Home page
 J. Virol.Home page
S. Boulant, C. Vanbelle, C. Ebel, F. Penin, and J.-P. Lavergne
Hepatitis C Virus Core Protein Is a Dimeric Alpha-Helical Protein Exhibiting Membrane Protein Features
J. Virol., September 1, 2005; 79(17): 11353 - 11365.
[Abstract] [Full Text] [PDF]

Home page
 Cancer Res.Home page
A. Huang, C. S.W. Ho, R. Ponzielli, D. Barsyte-Lovejoy, E. Bouffet, D. Picard, C. E. Hawkins, and L. Z. Penn
Identification of a Novel c-Myc Protein Interactor, JPO2, with Transforming Activity in Medulloblastoma Cells
Cancer Res., July 1, 2005; 65(13): 5607 - 5619.
[Abstract] [Full Text] [PDF]

Home page
 J. Biol. Chem.Home page
D. Ghibaudo, L. Cohen, F. Penin, and A. Martin
Characterization of GB Virus B Polyprotein Processing Reveals the Existence of a Novel 13-kDa Protein with Partial Homology to Hepatitis C Virus p7 Protein
J. Biol. Chem., June 11, 2004; 279(24): 24965 - 24975.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
J. Zhang, W. L. Rowe, J. P. Struewing, and K. H. Buetow
HapScope: a software system for automated and visual analysis of functionally annotated haplotypes
Nucleic Acids Res., December 1, 2002; 30(23): 5213 - 5221.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
R. E. Ellsworth, D. C. Jamison, J. W. Touchman, S. L. Chissoe, V. V. Braden Maduro, G. G. Bouffard, N. L. Dietrich, S. M. Beckstrom-Sternberg, L. M. Iyer, L. A. Weintraub, et al.
Comparative genomic sequence analysis of the human and mouse cystic fibrosis transmembrane conductance regulator genes
PNAS, February 1, 2000; 97(3): 1172 - 1177.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. M. Fullerton, J. Bond, J. A. Schneider, B. Hamilton, R. M. Harding, A. J. Boyce, and J. B. Clegg
Polymorphism and Divergence in the {beta}-Globin Replication Origin Initiation Region
Mol. Biol. Evol., January 1, 2000; 17(1): 179 - 188.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
N. Jareborg, E. Birney, and R. Durbin
Comparative Analysis of Noncoding Regions of 77 Orthologous Mouse and Human Gene Pairs
Genome Res., September 1, 1999; 9(9): 815 - 824.
[Abstract] [Full Text]

Home page
 Genome ResHome page
W. Jang, A. Hua, S. V. Spilson, W. Miller, B. A. Roe, and M. H. Meisler
Comparative Sequence of Human and Mouse BAC Clones from the mnd2 Region of Chromosome 2p13
Genome Res., January 1, 1999; 9(1): 53 - 61.
[Abstract] [Full Text]

Home page
 BloodHome page
M.A. Bender, A. Reik, J. Close, A. Telling, E. Epner, S. Fiering, R. Hardison, and M. Groudine
Description and Targeted Deletion of 5' Hypersensitive Site 5 and 6 of the Mouse beta -Globin Locus Control Region
Blood, December 1, 1998; 92(11): 4394 - 4403.
[Abstract] [Full Text] [PDF]

Home page
 J. Biol. Chem.Home page
J. Li, C. T. Noguchi, W. Miller, R. Hardison, and A. N. Schechter
Multiple Regulatory Elements in the 5'-Flanking Sequence of the Human epsilon -Globin Gene
J. Biol. Chem., April 24, 1998; 273(17): 10202 - 10209.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
M. A. Ansari-Lari, J. C. Oeltjen, S. Schwartz, Z. Zhang, D. M. Muzny, J. Lu, J. H. Gorrell, A. C. Chinault, J. W. Belmont, W. Miller, et al.
Comparative Sequence Analysis of a Gene-Rich Cluster at Human Chromosome 12p13 and its Syntenic Region in Mouse Chromosome 6
Genome Res., January 1, 1998; 8(1): 29 - 40.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
R. C. Hardison, J. Oeltjen, and W. Miller
Long Human-Mouse Sequence Alignments Reveal Novel Regulatory Elements: A Reason to Sequence the Mouse Genome
Genome Res., October 1, 1997; 7(10): 959 - 966.
[Full Text] [PDF]

Home page
 BloodHome page
D. C. Tang, D. Ebb, R. C. Hardison, and G. P. Rodgers
Restoration of the CCAAT Box or Insertion of the CACCC Motif Activate delta -Globin Gene Expression
Blood, July 1, 1997; 90(1): 421 - 427.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
J. Zhang and T. L. Madden
PowerBLAST: A New Network BLAST Application for Interactive or Automated Sequence Analysis and Annotation
Genome Res., June 1, 1997; 7(6): 649 - 656.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
J. C. Oeltjen, T. M. Malley, D. M. Muzny, W. Miller, R. A. Gibbs, and J. W. Belmont
Large-Scale Comparative Sequence Analysis of the Human and Murine Bruton's Tyrosine Kinase Loci Reveals Conserved Regulatory Domains
Genome Res., April 1, 1997; 7(4): 315 - 329.
[Abstract] [Full Text] [PDF]

Home page
 J. Biol. Chem.Home page
F. Charbonnier, B. D. Gaspera, A.-S. Armand, W. J. Van der Laarse, T. Launay, C. Becker, C.-L. Gallien, and C. Chanoine
Two Myogenin-related Genes Are Differentially Expressed in Xenopus laevis Myogenesis and Differ in Their Ability to Transactivate Muscle Structural Genes
J. Biol. Chem., January 4, 2002; 277(2): 1139 - 1147.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.