Locating alignments with k differences for nucleotide and amino acid sequences
- 1 March 1988
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 4 (1) , 19-24
- https://doi.org/10.1093/bioinformatics/4.1.19
Abstract
Given two sequences, a pattern of length m, a text of length n and a positive integer k, we give two algorithms. The first finds all occurrences of the pattern in the text as long as these do not differ from each other by more than k differences. It runs in O(nk) time. The second algorithm finds all subsequence alignments between the pattern and the test with at most k differences. This algorithm runs in O(nmk) time, is very simple and easy to program.This publication has 5 references indexed in Scilit:
- An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequencesJournal of Theoretical Biology, 1987
- Confidence limits for homology in protein or gene sequencesJournal of Molecular Biology, 1985
- RNA secondary structures and their predictionBulletin of Mathematical Biology, 1984
- Comparison of biosequencesAdvances in Applied Mathematics, 1981
- The theory and computation of evolutionary distances: Pattern recognitionJournal of Algorithms, 1980