7808335480

29.10.2015

Bioinformatyka, edycja 2015/2016, laboratorium 4

4. Algorytm LCS

Ponieważ algorytmy wyznaczające dopasowanie globalne i lokalne są algorytmami dynamicznymi, jako rozgrzewkę przypomnimy sobie algorytm najdłuższego wspólnego podciągu (LCS - longest common subseąuence). Pamiętajmy, że ważną cechą problemów do których możemy używać algorytmów dynamicznych jest własność optymalnej podstruktury tzn. jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.

Zadanie 2.

Jaki jest sens algorytmu LCS dla sekwencji DNA i białkowych - jakiego typu mutacji nie bierze on pod uwagę?

Algorytm:

Mamy dwa ciągi V i W długości odpowiednio n i m. Konstruujemy tablicę s rozmiaru n * m, gdzie pole s[j][j] oznacza LCS dla odpowiednio V[l..i] i W[l..j]. Ostatecznie w polu s[n][m] otrzymamy LCS dla całego V i W. W danym kroku wyliczamy s[j][j] na podstawie wcześniejszych obliczonych LCS dla podproblemów :

-jeśli V[i] = W[j] wtedy dołączamy zgodny znak do wyniku: s[i][j] = s[i-l][j-l]+l

-jeśli V[i] = W[j] wtedy sprawdzamy, który LCS dla podproblemów odpowiednio (V[ 1 ..i]; W[l..j-1]) i (V [l.i-l];W[l.j]) był dłuższy:

s[i]D] = max {s[i-l][j]; s[i][j-l] }

Dodatkowo możemy określić ilość zmian - insercji, delecji potrzebnych , aby przeprowadzić V w W, (s(V;W) oznacza długość LCS(V;W)):

d(V;W) = n + m - 2s(V;W)

0 o El a 0 61

0	0	0	0	0	0	0
0	'	1 0	t 0	\ 1		\ 1
0	0	- 1	- 1	ł 11	\
0	1 1	t	0	_ 2	<	t
0	\ 1	1	2	1 2		— 3
0	1 1	\		1		3
0	1 1	1	1	\ 3	3
0	\ 1	1	1	1 3	•

Computing similarity s(V,W)=4

V and W have a subsequence TCTA in conin:

1    2    3    4    5    6

T    ©    ^c    ©    T    A

0	1		3			6
Q	1	1 3	1 4	\ 3	— 4	\
		■		1	\ 3
3		1 3		- o	1 4	1
4	\ 3	1 4	1 3	1
5	1	' 3	t 4	1	o *	f 5
6	1	1 4	1	\
7	\ 6	J	1 <5	1 5	4

Computing distance d(\^r.W)=5

V can be ttansfonned mio W by delfinie A.G.T and inserling GA

= 0 30 » 0

5 G

.0

AT-    C    -    T    G    A    T

Alismnent:    * „    „    .    ^

- T G    C    A    T    -    A    -

Rysunek 3: Rysunek przebiegu LCS dla dwóch przykładowych sekwencji oraz pow stałe dopasowanie (przykład z książki „An Introduction to Bioinformatics Algorithms”, Jones, Pcvzner, MIT Press 2004).

4