Scientists performing DNA sequence alignment often desire a more parametrized way of aligning two strings than simply
Question:
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 .
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia