7808335481

Bioinformatyka, edycja 2015/2016, laboratorium 4

5. Algorytm Needlemana-Wunscha (dopasowanie globalne)

Algorytm LCS jest w pewnym sensie użyteczny dla zagadnienia dopasowania sekwencji, natomiast bierze on pod uwagę tylko możliwość indeli, czyli insercji lub delecji nukleotydów lub aminokwasów, przy czym dopasowanie nie jest w żadnej sposób za nie „karane”. Można pomyśleć nad takim wariantem algorytmu, który punktowałby również podstawienia, czyli zamianę nukleotydu czy aminokwasu na inny oraz w pewien sposób obniżał punktację dopasowania, jeśli nastąpi indel, ponieważ pojawienie się mutacji punktowej - zamiany nukleotydu czy aminokwasu na inny jest w naturze dużo bardziej prawdopodobne niż indel.

Tego typu algorytm zaproponowali panowie Needleman i Wunsch w 1970 roku.

s[/'- !][/- 1] + S (V[i],    gdy dopasowanie lub substytucja

$[/' - 1] [_/], gdy przerwa w V

s[z'][y - 1], gdy przerwa w W

gdzie macierz 5 jest macierzą punktacji, d jest liniową karą za przerwę. Dla nukleotydów macierz punktacji to np. +1 za dopasowanie, -2 za niedopasowanie, natomiast dla aminokwasów sytuacja jest bardziej skomplikowana i wykorzystuje się macierze substytucji.

Możliwe są też inne typy kary za przerwę, np. najczęściej używany jest afiniczny model kary za przerwę:

Gappcnally = Gap₀pcning + k * Gap_c,xicnsion

Wiemy, że otwarcie przerwy, czyli możliwość insercji lub delecji jest dość rzadka, natomiast jeżeli już przerwa się pojawi, to jest duże prawdopodobieństwo, że wstawi się lub zniknie wiele nukleotydów na raz. Dlatego lepiej jest gdy mamy mniej przerw, ale są one dłuższe, niż więcej krótkich. Stąd nakładamy dużą karę za otwarcie przerwy, które jest mało prawdopodobne, a potem dokładamy dużo mniejszą karę za wydłużenie przerwy.

6. Algorytm Smitha-Watermana - dopasowanie lokalne

Aby utworzyć algorytm dopasowania lokalnego na podstawie powyższego wzoru na dopasowanie globalne, należy dołożyć jeszcze jedną możliwość.

s[z- 1 ][y- 1]+ 8 (F[/‘], łT[y]), gdy dopasowanie lub substytucja sfz - l][y], gdy przerwa w V s[/][y - 1], gdy przerwa w W 0, gdy zaczynamy nowe loka ln e dopasowanie

5

Wyszukiwarka

Podobne podstrony:
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 44. Algorytm LCS Ponieważ algorytmy
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