How Much Does it Cost to Align Two Symbols?click to expand
As we saw in “Counting Optimal Alignments”, there will usually be a huge number of different optimal alignments
of two given strings. In this problem, which represents a first attempt to understand
how much optimal alignments can differ,
we will select two symbols at a time from the two strings and ask how much the maximum alignment score
can differ from the optimal score if we demand that these two symbols must be aligned (i.e., implying
that one symbol must be substituted for the other).
Problem
Say that we have two strings s and t of respective lengths m and n and an alignment score.
Let's define a matrix M corresponding to s and t by setting
Mj,k equal to the maximum score of any alignment that aligns s[j] with t[k].
So each entry in M can be equal to at most the maximum score of any alignment of s and t.
Return: The maximum alignment score of a global alignment of s and t, followed by
the sum of all elements of the matrix M corresponding to s and t that was defined above. Apply the mismatch score
introduced in “Finding a Motif with Modifications”.
Sample Dataset
>Rosalind_35
ATAGATA
>Rosalind_5
ACAGGTA
Sample Output
3
-139
Citationclick to expand
This problem follows Jones & Pevzner, An Introduction to Bioinformatics Algorithms, Problem 6.21
Hintclick to expand
For the sample dataset
M=[30−1−4−5−10−11030−1−4−7−10−103−2−1−6−7−4−1030−3−6−7−4−3230−3−10−5−6−303−2−11−10−5−6−1−23]
