Dzisiaj na wykładzie zajmowaliśmy się uzgadnianiem drzew.
Slajdy do wykładu:
- Wg Pawła Góreckiego (głównie slajdy 1-20) : dlt
- Wg Terry’ego Speed’a (głównie slajdy 14-20): Terry-Speed-Reconciliation
Zadania na lab:
Dzisiaj zajmiemy się uzgadnianiem drzew. Rozważmy sytuację, gdy mamy 1 drzewo gatunków S i drzewo genów G zgodne z tym drzewem gatunków (dla każdego genu g\in G , s(g)\in S). Na początek możesz
1. Napisz algorytm LCA(G,S), który znajduje mapowanie LCA i zwraca je w postaci słownika
2. Napisz funkcje liczące koszty DC(G,S), D(G,S) a następnie wykorzystaj wzór ze slajdu 10, który wylicza koszt L(G,S)
3. Napisz funkcję fat_tree(G,S), która tworzy scenariusz uzgadniający G i S (nie zawsze optymalny), gdzie w korzeniu występują wszystkie duplikacje, zaś wszystkie straty występują w krawędziach prowadzących do liści. Scenariusz w naszym przypadku, to etykietowanie drzewa gatunków zdarzeniami ewolucyjnymi, D i L. Zauważmy, że zarówno straty jak i duplikacje występują na krawędziach drzewa gatunków.
4. Napisz funkcję optimal_tree(G,S), która znajduje jeden z optymalnych scenariuszy uzgadniających G i S. W tym celu musimy przenieść w drzewie “grubym” duplikacje w dół, a straty w górę, jeśli to możliwe.
5. sprawdź na przykładzie drzewa z wykładu (abcde), czy Twój algorytm działa poprawnie