CODEWITHSUNDEEP
sequence-alignment
arman imen
arman imen

Reputation: 41

global alignment using gap penalty function

can any body help me with the following problem?!

For a parameter k, compute the global alignment between two strings, subject to the constraint that the alignment contains at most k gaps (blocks of consecutive indels).

Upvotes: 4

Views: 893

Answers (2)

GoldenaArcher
GoldenaArcher

Reputation: 983

I was looking for the similar question, and finally found the solution which the proper term is called Affine Gap Penalties. The slide can be found at Advanced Sequence Alignment, which is one of the old course slides from UNC-Chapel Hill.

The related slide start from #12.

In short answer is that:

  1. There will be a slight different penalty for consecutive indels (gap extension penalty);

  2. we need 3 matrices to keep all the values, the screenshot came from the slide:

    switching-between-3-layers

Upvotes: 1

seaotternerd
seaotternerd

Reputation: 6419

You should be able to handle this as an extension of the standard dynamic programming approach to sequence alignment. The wrinkle is that there are now multiple ways that you could be at a given cell in the matrix, because you could have gotten there with using different amounts of gaps. As a result, you need to keep track of the best score that you could have in each cell given that you used a certain number of gaps to get there.

You can accomplish this by using the same intuition used to keep track of gap length when implementing an affine penalty: by keeping track of k + 1 matrices. The dynamic programming algorithm starts on the 0th matrix. This matrix will represent the best score that you could have at any point in the grid without having inserted any gaps. If you choose either "add gap in x" or "add gap in y" from matrix 0, you will record the resulting score in matrix 1. If you add a gap from matrix 1, you go to matrix 2, and so on. If you are in matrix k, adding a gap is not an option. The start-point for traceback will be the lower right-hand corner with the highest score.

Upvotes: 1

Related Questions