An efficient string matching algorithm withkdifferences for nudeotide and amino acid sequences
Open Access
- 1 January 1986
- journal article
- Published by Oxford University Press (OUP) in Nucleic Acids Research
- Vol. 14 (1) , 31-46
- https://doi.org/10.1093/nar/14.1.31
Abstract
There are a few algorithms designed to solve the problem of the optimal alignment of one sequence, the pattern, of length m, with another, longer sequence the text, of length n These algorithms allow mismatches, deletions and insertions. Algorithms to date run in 0(mn) time. Let us define an integer. k, which is the maximal number of differences allowed We present a simple algorithm showing that sequences can be optimally aligned in O(k2) time. For long sequences the gain factor over the currently used algorithms is very large.Keywords
This publication has 12 references indexed in Scilit:
- Fast optimal alignmentNucleic Acids Research, 1984
- Rapid similarity searches of nucleic acid and protein data banks.Proceedings of the National Academy of Sciences, 1983
- Pattern recognition in nucleic acid sequences. I. A general method for finding local homologies and symmetriesNucleic Acids Research, 1982
- Efficient algorithms for folding and comparing nucleic acid sequencesNucleic Acids Research, 1982
- Enhanced graphic matrix analysis of nucleic acid and protein sequences.Proceedings of the National Academy of Sciences, 1981
- Fast algorithm for predicting the secondary structure of single-stranded RNA.Proceedings of the National Academy of Sciences, 1980
- Pattern recognition in genetic sequencesProceedings of the National Academy of Sciences, 1979
- Matching Sequences under Deletion/Insertion ConstraintsProceedings of the National Academy of Sciences, 1972
- Estimation of Secondary Structure in Ribonucleic AcidsNature, 1971
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970