Scientists performing DNA sequence alignment often desire a more parametrized way of aligning two strings than simply computing a longest common subsequence between these two strings. One way to achieve such flexibility is to use the Smith-Waterman algorithm, which is generalization of the dynamic programming algorithm for computing a longest common subsequence so that it can handle weighted scoring functions. In particular, for two strings, X and Y , suppose we are given functions, defined on characters, a, from X, and b from Y , as follows: 

M(a, b) = the positive benefit for a match, if a = b 

M(a, b) = the negative cost for a mismatch, if a     = b 

I(a) = the negative cost for inserting a at a position in X 

D(b) = the negative cost of deleting b from some position in Y . 

Given a string, X, of length n and a string, Y , of length m, describe an algorithm running in O(nm) time for finding the maximum-weight way of transforming X into Y , according to the above weight functions, using the operations of matching, substitution, insertion in X, and deletion from Y .