Programowanie dynamiczne.PDF

(2263 KB) Pobierz
Olga RUSINEK
Karol SIWEK
Mateusz SUCHOCKI
Zastosowanie i znaczenie
bioinformatyczne
Podobieństwo porównywanych sekwencji może
świadczyć o:
podobnej funkcji sekwencji
podobnej strukturze białek
wspólnej historii ewolucyjnej sekwencji
Dopasowanie dwóch sekwencji
Globalne dopasowanie dwóch sekwencji otrzymujemy
przez wstawienie pustych miejsc(spacji, tyld) zarówno
w środek jak i na końcu sekwencji S1 i S2, następnie
umieszczenie tych sekwencji jedna nad drugą w ten
sposób, że każdy znak (litera lub spacja) w jednej
sekwencji posiada odpowiedni znak lub spację w
przeciwległej sekwencji.
A L A M A K O T _ K A
M _ A K A R O N I K _
Definicja formalna:
Rozważamy słowa nad alfabetem Σ. Dodajemy nowy
symbol spacji Σ’ = Σ
υ
{_}. Dla słów
u, w
∈
Σ*
ich
liniowym dopasowaniem
nazywamy parę słów
u*,w*
∈
(Σ’)*
spełniających warunki:
Usunięcie spacji z u* i w* daje w wyniku odpowiednio u i w,
|u*| = |w*|
∀
i≤|u*|
u*[i]≠’_’
∨
u*[i]≠’_’
Przykład: u=ALAMAKOTKA, w=MAKARONIK
u* = A L A M A K O T _ K A
w* = M _ A K A R O N I K _
Odległośd edycyjna „ważona”
Odległością edycyjną
(edit distance)
między dwoma
sekwencjami jest minimalna liczba operacji edycji
(działań prostych) – wstawiania, usuwania i zamiany
symboli, konieczna do transformacji pierwszej
sekwencji z drugą. Symbole pasujące nie są liczone.
Odległość edycyjna ważona
– operacje: wstawiania,
usuwania i zamiany mogą mieć różne wagi.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin