Fast alignment of DNA and protein sequences.
Explore the source record for details and available documents.
Algorithms↗
Biomedical subjects
G M Landau
Publications and source records attributed to G M Landau.
Locating alignments with k differences for nucleotide and amino acid sequences.
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.
Algorithms↗
An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences.
Given a text of length n, a pattern of length m and an integer k, we present an algorithm for finding all occurrences of the pattern in the text, each with at most k substitutions. The algorithm runs in O(k(m log m + n)) time, and requires O(nk) space. This algorithm has direct implications for nucleotide and amino acid sequence comparisons.
Algorithms↗
An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.
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 O(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(k2n) time. For long sequences the gain factor over the currently used algorithms is very large.
Amino Acid Sequence↗