WBO – Zadanie 1

UWAGA! Przenosimy termin zadania 1 o tydzień, na 29. kwietnia.

Naszym pierwszym zadaniem będzie implementacja ważonej odległości Robinsona-Fouldsa (RF) na drzewach i jej zastosowanie.

Odległość RF definiujemy następująco:

Dla zadanego nieukorzenionego drzewa T (z długościami krawędzi ), definiujemy dla każdego podziału liści na rozłączne podzbiory A,B, wartość d(T,A,B) jako długość krawędzi rozdzielającej podzbiory A i B w drzewie T (jeśli taka krawędź istnieje) lub 0 (jeśli taka krawędź nie istnieje). Dla dowolnego drzewa T o N liściach wierzchołkach (gdzie wierzchołków jest niemal 2 razy tyle co liści),  liczba niezerowych d(T,A,B) jest równa N-1.

Odległość WRF, to

Nasze zadanie polega na napisaniu programu w pythonie, który oprócz implementacji odległości WRF (w czasie wielomianowym względem N), wykonuje następujące operacje:

1. Wczytuje sekwencje białkowe z pliku homeo2.fa (1 pkt)

2. Oblicza drzewo filogenetyczne (T1) dla nich za pomocą algorytmu ClustalW (2 pkt)

3. Oblicza drzewo filogenetyczne (T2) za pomocą algorytmu NJ na macierzy podobieństwa obliczonej przy pomocy macierzy BLOSUM62 na podstawie multiuliniowienia otrzymanego przy pomocy algorytmu muscle (3 pkt)

4. oblicza odległość WRF drzew T1 i T2 (4 pkt)

Program powinien być napisany czytelnie i skomentowany.

Program wysyłamy do dnia 22. 29. kwietnia 2019, w postaci pliku .py mailem do prowadzącego zajęcia z dopiskiem [WBO-1-2019] w temacie. Po tym terminie można uzyskać maksymalnie 50% punktów za zadanie dosłane przed końcem semestru.