I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions were used for any match.

Using brute force backtrack I can find the matches, but I cannot guarantee that the match was produced using the fewest permutations possible.

Using dynamic programming I can find the matches and guarantee that the match was produced using the fewest permutations possible, but I cannot specify a number of allowed mismatches, insertion and deletions - only a total edit distance.

  • $\begingroup$ Do you want an alignment with exactly some amount of mismatch, insertion, and deletion? Or at most some specified values? $\endgroup$ Dec 1, 2012 at 0:17
  • $\begingroup$ Also, if you allow insertions and deletions, don't you mean sub-sequences? $\endgroup$ Dec 1, 2012 at 5:01
  • $\begingroup$ I am interested in matches with at most some specified limits. I never fully appreciated the difference between substring vs sub-sequence as explained in Wikipedia - I work in biology and here a sequence is something different altogether - so I tend to say substring. $\endgroup$
    – maasha
    Dec 1, 2012 at 8:38
  • $\begingroup$ I am referring to sequence as a mathematical object, not a biological/physical sequence. A sub-string can be (informally) defined as a contiguous sub-sequence of a string. In general a sub-sequence may not be contiguous. For example let $s=\text{ACGTCT}$. A valid sub-string could be $s' = \text{CGTC}$. A valid sub-sequence could be $s'' = \text{ACG--T}$. $\endgroup$ Dec 1, 2012 at 20:07
  • $\begingroup$ In that case I mean sub-sequence. $\endgroup$
    – maasha
    Dec 2, 2012 at 10:42

2 Answers 2


What you want is the so-called (optimal) local alignment of two strings. You can use the standard local alignment algorithm but allow insertions/deletions at the beginning and end (of the the shorter string) for free.

In the classic dynamic programming algorithm, this corresponds to initialising the first row (resp. column) with zero, removing the penalty for steps along the last row (resp. column) and finally looking for the minimum cost in the last row (resp. column) and backtrack from there. You can find alternatives in the Wikipedia article.

Restricting the number of deletions or insertions used can be implemented by adding counters to the cell values; if adding one would take one over the respective limit (stored globally), assign cost $\infty$ to the respective operation.


You should be able to modify the dynamic program for global alignment to return a 3-vector $\langle m, i, d \rangle$ that contains the number of mismatches, insertions, and deletions. It is straightforward to see that edit distance is simply the $\ell_1$ (i.e. sum) of this vector.

If any of these individual values are greater than their allowed amount, you can return $\langle \infty, \infty, \infty \rangle$. If no alignment has less than the number of allowed mismatches, insertions, or deletions, this answer will propogate upward.

  • $\begingroup$ Take the string ATCG and the substring AG. This can be matched with a match-mismatch path. If I allow 0 mismatch and two deletions I could get the match-deletion-deletion-match path as an alternative. However this path will never be considered even if using a 3-vector since the criteria for going up, left or diag is still based on the edit distance. $\endgroup$
    – maasha
    Dec 1, 2012 at 8:34
  • $\begingroup$ @maasha, A--G is the optimal global alignment. Why wouldn't it be considered? $\endgroup$ Dec 1, 2012 at 17:43
  • $\begingroup$ The problem is that if a shorter path exists wihtin the specified maximum edit distance - such as the match-mismatch path, then this will always be chosen - even if I don't allow mismatches. I don't see a way to consider only certain paths. $\endgroup$
    – maasha
    Dec 3, 2012 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.