J Mol Biol. 1991 Oct 20;221(4):1367-78.

An efficient algorithm for identifying matches with errors in multiple long molecular sequences.

Leung MY, Blaisdell BE, Burge C, Karlin S.

Source

Division of Mathematics, Computer Science and Statistics, University of Texas, San Antonio 78249-0664.

Abstract

An efficient algorithm is described for finding matches, repeats and other word relations, allowing for errors, in large data sets of long molecular sequences. The algorithm entails hashing on fixed-size words in conjunction with the use of a linked list connecting all occurrences of the same word. The average memory and run time requirement both increase almost linearly with the total sequence length. Some results of the program's performance on a database of Escherichia coli DNA sequences are presented.

PMID:: 1942056; [PubMed - indexed for MEDLINE]

Publication Types, MeSH Terms, Grant Support

Publication Types

MeSH Terms

Grant Support

LinkOut - more resources

Full Text Sources

Other Literature Sources

COS Scholar Universe

Libraries

LinkOut Holdings

Supplemental Content

Save items

Related citations in PubMed

Multiple alignment using simulated annealing: branch point definition in human mRNA splicing. [Nucleic Acids Res. 1992]
Multiple alignment using simulated annealing: branch point definition in human mRNA splicing.
Lukashin AV, Engelbrecht J, Brunak S. Nucleic Acids Res. 1992 May 25; 20(10):2511-6.
A RAPID algorithm for sequence database comparisons: application to the identification of vector contamination in the EMBL databases. [Bioinformatics. 1999]
A RAPID algorithm for sequence database comparisons: application to the identification of vector contamination in the EMBL databases.
Miller C, Gurd J, Brass A. Bioinformatics. 1999 Feb; 15(2):111-21.
Refined repetitive sequence searches utilizing a fast hash function and cross species information retrievals. [BMC Bioinformatics. 2005]
Refined repetitive sequence searches utilizing a fast hash function and cross species information retrievals.
Reneker J, Shyu CR. BMC Bioinformatics. 2005 May 3; 6:111. Epub 2005 May 3.
An efficient algorithm to locate all locally optimal alignments between two sequences allowing for gaps. [Comput Appl Biosci. 1993]
An efficient algorithm to locate all locally optimal alignments between two sequences allowing for gaps.
Barton GJ. Comput Appl Biosci. 1993 Dec; 9(6):729-34.
Review Short palindromic repetitive DNA elements in enterobacteria: a survey. [Res Microbiol. 1999]
Review Short palindromic repetitive DNA elements in enterobacteria: a survey.
Bachellier S, Clément JM, Hofnung M. Res Microbiol. 1999 Nov-Dec; 150(9-10):627-39.

See reviews... See all...

Cited by 11 PubMed Central articles

CLUSS: clustering of protein sequences based on a new similarity measure. [BMC Bioinformatics. 2007]
CLUSS: clustering of protein sequences based on a new similarity measure.
Kelil A, Wang S, Brzezinski R, Fleury A. BMC Bioinformatics. 2007 Aug 4; 8:286. Epub 2007 Aug 4.
CGAT: a comparative genome analysis tool for visualizing alignments in the analysis of complex evolutionary changes between closely related genomes. [BMC Bioinformatics. 2006]
CGAT: a comparative genome analysis tool for visualizing alignments in the analysis of complex evolutionary changes between closely related genomes.
Uchiyama I, Higuchi T, Kobayashi I. BMC Bioinformatics. 2006 Oct 24; 7:472. Epub 2006 Oct 24.
Application of a superword array in genome assembly. [Nucleic Acids Res. 2006]
Application of a superword array in genome assembly.
Huang X, Yang SP, Chinwalla AT, Hillier LW, Minx P, Mardis ER, Wilson RK. Nucleic Acids Res. 2006; 34(1):201-5. Epub 2006 Jan 5.

See all...

Related information

Related Citations
Calculated set of PubMed citations closely related to the selected article(s) retrieved using a word weight algorithm. Related articles are displayed in ranked order from most to least relevant, with the “linked from” citation displayed first.
Cited in PMC
Full-text articles in the PubMed Central Database that cite the current articles.

Recent activity

Clear Turn Off Turn On

An efficient algorithm for identifying matches with errors in multiple long mole...
An efficient algorithm for identifying matches with errors in multiple long molecular sequences.
J Mol Biol. 1991 Oct 20 ;221(4):1367-78.

PubMed
Large-scale mRNA sequencing determines global regulation of RNA editing during b...
Large-scale mRNA sequencing determines global regulation of RNA editing during brain development.
Genome Res. 2009 Jun ;19(6):978-86. Epub 2009 May 6 .

PubMed
Evidence for an ancestral core structure in nucleotide-binding proteins with the...
Evidence for an ancestral core structure in nucleotide-binding proteins with the type A motif.
J Mol Biol. 1991 Oct 5 ;221(3):751-4.

PubMed
Evolution of Complex RNA Polymerases: The Complete Archaeal RNA Polymerase Struc...
Evolution of Complex RNA Polymerases: The Complete Archaeal RNA Polymerase Structure.
PLoS Biol. 2009 May 5;7(5):e102. [Epub ahead of print]

PubMed
MAP5 in cultured hippocampal neurons: expression diminishes with time and growth...
MAP5 in cultured hippocampal neurons: expression diminishes with time and growth cones are not immunostained.
J Neurocytol. 1991 Aug ;20(8):627-36.

PubMed

Your browsing activity is empty.

Activity recording is turned off.

Turn recording back on

PubMed

Result Filters

Display Settings:

Send to: