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
Alismnent: * „ „ . ^
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
Wyszukiwarka
Podobne podstrony:
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 45. Algorytm Needlemana-Wunscha (dopasowan
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 4 Instytut Informatyki I Matematyki Komput
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 4 Możliwa jest również sytuacja, kiedy
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 4Zadanie 1. - Wejdź na
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 4 Rysunek 4: Z materiałów do kursu
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 4Global Alignment vs. Local
Piekary Śląskie 29.10.2015 Radny Rady Miasta Piekary Śląskie Łukasz
6 10(1) 2015/2016 Piotr Bieranowski - ćwiczenia z WYTRZYMAŁOŚCI MATERIAŁÓW, CZ. VI. RRS: 0) =
GRUPA D 2015/2016^^. PIŁKA RĘCZNA UMCS Lublin - AZS Politechnika Lubelska 29:25 (14:10) UMCS: Pawelc
BIULETYN METODYCZNY nr 1 (34) II SEMESTR 2015/2016 10 Uczniowie różnią się od siebie nie tylko rodza
Harmonogram zajęć kierunek lekarski rok IV semestr 7 (zimowy) 2015/2016 Liczba studentów na roku - 4
I Rok Wydział Lekarski - „Biologia Medyczna” - Rok Akad. 2015/2016 Ćwiczenie 10 Temat: Genetyka medy
ROK I 2015/2016 (edycja 2015/2016 - 2017/2018) Lp. Nazwa
więcej podobnych podstron