7808335483

29.10.2015

Bioinformatyka, edycja 2015/2016, laboratorium 4

Global Alignment vs. Local alignment

Needleman-Wunsch alaorithm		Smith-Waterman alaorithm
Initialization:	F(0, 0) = 0	Initialization:	F(0,j) = F(i, 0) = 0
Iteration:		Iteration:	[ o
F(i,j) = max	F(i — 1, j) — d F(i,j-1)-d F(i-1.j-1) + s(xlly,)	F(i, j) = max	F(i — 1. j) — d F(i, j — 1) — d F(i - 1. j -1) + s(xi, yj)
Termination:	Bottom right	Termination:	Anywhere

Rysunek 5: Z materiałów do kursu „Computational Biology: Genomes, Networks, Evolution”, MIT Open-CourseWare

Zadanie 3.

Wykorzystując program NW-align (http://zhanglab.ccmb.med.umich.edu/NW-alignA porównaj ze sobą sekwencje aminokwasowe (w nawiasach podano identyfikatory sekwencji w bazie Protein)-.

-    hemoglobiny beta u człowieka (GI:40886941) i szczura (GI:34849618)

-    hemoglobiny beta u człowieka (GI:40886941) i mioglobiny ludzkiej (GI: 44955888)

-    dowolnych dwóch cytochromów P450 człowieka (hasło do wyszukiwania: cytochrome P450 homo sapiens)

Jakie wnioski możesz wyciągnąć z dokonanych przyrównań?

Jakie znaczenie ma zastosowanie w porównaniach macierzy substytucji?

Zadanie 5

Zaimplementuj algorytm Needlemana-Wunscha dopasowania globalnego par sekwencji w modelu liniowym.

Dla uproszczenia można przyjąć, że rozważane będą wyłącznie sekwencje aminokwasowe (wykorzystaj macierz substytucji, np. BLOSUM62), kara za przerwę: -7 pkt.

Gdy istnieje więcej niż jedno optymalne dopasowanie, program powinien wypisać wszystkie.

7