Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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.

share|improve this question
Do you want an alignment with exactly some amount of mismatch, insertion, and deletion? Or at most some specified values? – Nicholas Mancuso Dec 1 '12 at 0:17
Also, if you allow insertions and deletions, don't you mean sub-sequences? – Nicholas Mancuso Dec 1 '12 at 5:01
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. – maasha Dec 1 '12 at 8:38
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}$. – Nicholas Mancuso Dec 1 '12 at 20:07
In that case I mean sub-sequence. – maasha Dec 2 '12 at 10:42

2 Answers

up vote 2 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
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. – maasha Dec 1 '12 at 8:34
@maasha, A--G is the optimal global alignment. Why wouldn't it be considered? – Nicholas Mancuso Dec 1 '12 at 17:43
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. – maasha Dec 3 '12 at 8:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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