[Math] How to prove that a dynamic programming algorithm is a monotonic function

proof-writingrecursive algorithms

I've written an algorithm, which is based on the Needleman-Wunsch algorithm for matching sequences of proteins. This algorithm is a dynamic programming approach, where the optimal matching of two sequences A and B, with length m and n is being calculated by first solving the same problem for the respective substrings.

Currently I'm working on a proof of optimality and one lemma I (think I) need to prove first, is that my algorithm (lets call it A) always yields a score which is higher or equal to the score, than when applying the algorithm to substrings of A and B.

These are my main problems:

  • The algorithm/function has two dimensions (the "size" of the two substrings)
  • Every cell value of the value matrix used in the algorithm is defined to be the maximum of some values, based on values calculated before (overlapping subproblems)

I've found some help regarding multidimensional induction in a blogpost, but I don't know how to approach the max-function.

It would be great if you could give me a hint or a topic I should read about!

Thanks in advance,

das_weezul

EDIT:

Here is a simplified version of the algorithm (Lets call it MATCH). $a_m$ is the m-th symbol of string A, and $b_n$ is the n-th symbol of string B. $SIM(a_m,b_n)$ is the similarity of $a_m$ and $b_n$, which is 1 if $a_m$ and $b_n$ are equal and -1 if not:

$
SIM(a_m,b_n) = \begin{cases}
1, a_m = b_n\\
-1, otherwise
\end{cases}\\
MATCH(0,0) = 0\\
MATCH(0,n) = 0\\
MATCH(m,0) = 0\\
MATCH(m,n) = max \begin{cases}
MATCH(m-1,n-1)+ sim(a_m,b_n)\\
MATCH(m,n-1)\\
MATCH(m-1,n)
\end{cases}
$

What I want to show is something like this:

$MATCH(m-i,n-j) \leq MATCH(m,n), 0 \leq i \lt m \wedge 0 \leq j \lt n $

Best Answer

Isn't that obvious? $$ MATCH(m,n) = max \begin{cases} (a): MATCH(m-1,n-1)+ sim(a_m,b_n)\\ (b): MATCH(m,n-1)\\ (c): MATCH(m-1,n). \end{cases} $$ Apply (b) recursively, we get \begin{align} MATCH(m,n) &\ge MATCH(m,n-1)\\ &\ge MATCH(m,n-2)\\ &\ge \ldots\\ &\ge MATCH(m,n-j). \end{align} Now apply (c) recursively and get \begin{align} MATCH(m,n-j) &\ge MATCH(m-1,n-j)\\ &\ge MATCH(m-2,n-j)\\ &\ge \ldots\\ &\ge MATCH(m-i,n-j). \end{align} Put this two sequences of inequalities together, we obtain $$MATCH(m,n)\ge MATCH(m-i,n-j).$$ In other words, you first traverse from the node $(m,n)$ horizontally to the left until you reach $(m,n-j)$, then traverse vertically down to the node $(m-i,n-j)$. By the defintion of the $MATCH$ function, the value of the node will decreases along this path.

Related Question