I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.

The problem:

Given two strings S1 and S2, find the score of their optimal global alignment with gaps. The gap costs are given by a general function-𝑤(𝑘). It is known that for gaps lengths-𝑘 ≥ 𝑑, 𝑤(𝑘) equals a constant C.

Suggest an algorithm solving the problem with space O(min{|S1|,|S2|}*d) and time O(|S1|*|S2|*d).

Instruction: When choosing the optimal gap length at each matrix entry, process separately the gaps of a length less than d and the longer gaps. Store in each matrix entry the optimal value obtained by using the longer gaps, in addition to the regular optimal value.

Now we learned the following 2 algorithms:

Alignment with gaps where we do not know anything about the cost function: enter image description here

Alignment with affine gap cost function enter image description here

my solution:

I know that I have to use a d-rows table in order to meet the space requirements, and to use both methods but I'm having troubles to combine it into one recursive formula, Here is what I have done so far: enter image description here

But I'm not sure how to include the cost for elongating an existing gap that is longer than d, and not even sure how to check if my recursive formula is correct. Any help would be appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.