WBO 10 – uzgadnianie drzew

Dzisiaj na wykładzie zajmowaliśmy się uzgadnianiem drzew.

Slajdy do wykładu:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>