Local Alignment & Gap Penalties - CBCB

Local Alignment & Gap Penalties

CMSC 423

Global, Semi-global, Local Alignments

? Last time, we saw a dynamic programming algorithm for global

alignment: both strings s and t must be completely matched:

s t

? Semiglobal:

s

t

Gaps at starts and ends of some sequences come for free

? Local:

s

t

Best alignment between substrings of s and t.

Free gaps at ends of sequences

max of orange =

best ignoring spaces at end of x

C 9 9g A 8 8g G 7 7g T 6 6g

y T 5 5g

G 4 4g C 3 3g A 2 2g A 1 1g

0 0 1g 2g 3g 4g 5g 6g 7g 8g 9g 10g 11g 12g 0 1 2 3 4 5 6 7 8 9 10 11 12 AAGGT A TGAA T C

x

OPT(n, m)

max of blue = best ignoring spaces at end of y

best alignment between x and a prefix of y

Free gaps at the start of sequences

set orange = 0 to ignore spaces at start of x

C 9 9g A 8 8g G 7 7g T 6 6g

y T 5 5g

G 4 4g C 3 3g A 2 2g A 1 1g

00000000000000 0 1 2 3 4 5 6 7 8 9 10 11 12 AAGGT A TGAA T C

x

set blue = 0 to ignore spaces at start of x

Semiglobal Recap

Free spaces @ end of x end of y start of x start of y

What to do take max of topmost row take max of rightmost row set bottommost row to 0

set leftmost row to 0

? Can combine these arbitrarily: e.g. to have free spaces at the start

of x and both ends of y:

set bottom- and left-most rows to 0 and take the max of the rightmost row.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download