7808335482

Bioinformatyka, edycja 2015/2016, laboratorium 4

Dopasowanie lokalne metodą programowania dynamicznego możemy obliczyć w sposób podobny do dopasowania globalnego, z tą różnicą, że pozwalamy aby dopasowanie zaczynało i kończyło się w dowolnym miejscu (wstawiamy zero tam gdzie mutacja i indel dałyby punktację ujemną), tzn. rekonstrukcji dopasowania nie musimy zaczynać od prawego dolnego rogu, ale od dowolnego miejsca tablicy, które jest najlepiej punktowane. Rekonstruujemy dopasowanie aż do miejsca, gdzie natrafimy na punktację zerową, bądź lewy górny róg tablicy. Algorytm dynamiczny dopasowania lokalnego został przedstawiony przez Tempie F. Smith'a and Michael S. Waterman'a w 1981 roku.

Porównanie tych dwóch strategii dla programowania dynamicznego jest widoczne na poniższym rysunku poniżej (rys. 2). Algorytmy te mają jedną podstawową wadę - za cenę dokładnego i z pewnością optymalnego dopasowania płaci się złożonością czasową i pamięciową - 0(n*m), co sprawia, że zastosowanie tych algorytmów dla długich sekwencji (rzędu milionów bądź miliardów nukleotydów, a takie porównania robi się najczęściej) jest mocno ograniczone. Dlatego poszukiwano szybszych metod, które pozwoliłyby np. na dopasowanie lokalne nieznanego fragmentu sekwencji do całego genomu organizmu we względnie krótkim czasie.

6

Wyszukiwarka

Podobne podstrony:
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 44. Algorytm LCS Ponieważ algorytmy
29.10.2015 Bioinformatyka, edycja 2015/2016, laboratorium 45. Algorytm Needlemana-Wunscha (dopasowan
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) =
BIULETYN METODYCZNY nr 1 (34) II SEMESTR 2015/2016 19 Rysunek 1. Dzieci ze Specjalnymi Potrzebami Ed
BIULETYN METODYCZNY nr 1 (34) II SEMESTR 2015/2016 5 przygotowaniem dzieci i młodzieży do funkcjonow
WIMiC 2015/2016. Technologia chemiczna Zagadnienia do egzaminu z chemii organicznej 1.
img084 (29) 5.    Naczynia laboratoryjne, zawierające materiały do badania, nie mogą
Ipf.wppt.pwr.edu.pl fizyka -laboratorium -sprawozdania materiały do sprawozdań

więcej podobnych podstron