Phylogenetic tree reconstruction using maximum parsimony branch-and-bound algorithm

Metoda maksimalne uštede, kao jedna od metoda za rekonstrukciju filogenetskog stabla, po principu Occamove oštrice zahtjeva da rekonstruirano stablo koristi minimalan broj mutacija potreban za objašnjenje podataka. Metoda maksimalne uštede spada u metode koje se temelje na matrici obilježja i na optimalnom kriteriju. Kako je ovaj problem NP-težak, prilikom implementacije metode korištena je razgranaj-ograniči optimizacija. Programsko rješenje testirano je na nizu različitih sekvenci i dobiveni su rezultati u skladu s očekivanima.Maximum parsimony is a character-based method, akin to Occam's razor principle, that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data. It relies on the use of optimality criteria. Due to the fact that this problem is an NP-hard problem, branch and bound optimization was used in software solution. Software solution was tested on various sets of sequences and the results were as expected