Praca dotyczy algorytmu z pracy "Paweł Górecki and Oliver Eulenstein, A linear time algorithm for error-corrected reconciliation of unrooted gene trees", który jest rozszerzeniem zaimplementowanego już algorytmu (URec, C/C++). Po zaimplementowaniu planuję publikację typu "application note".
Wymagania: dobra znajomość C/C++, algorytmy, grafy, ambitny student
Słowa kluczowe: error correction, unrooted gene tree, reconciled tree, phylogenetic tree

Praca dotyczy tematyki związanej z algorytmami obliczania najniższego/najpóźniejszego wspólnego przodka (least/lowest common ancestor) w drzewach ukorzenionych. Tematyką byłaby m.in. implementacja szybkiego algorytmu z pracy Bender, Farach-Colton ``The LCA Problem Revisited'' w kontekście drzew uzgadniających.
Słowa kluczowe: LCA problem, reconciled tree, phylogenetic tree

Rozważany problem: wejście to zbiór drzew genów z długościami krawędzi oraz drzewo gatunków bez długości krawędzi. Obliczyć długości krawędzi dla drzewa gatunków, przy założeniu, że użyty model do obliczeń jest biologicznie uzasadniony (np. model drzew uzgadniających).
Słowa kluczowe: gene tree, species tree, reconciled tree, branch length

Kontakt: gorecki@mimuw.edu.pl  Home page