Rekonstrukcija filogenetskog stabla koristeći metodu maksimalne uštede uz razgranaj-ograniči optimizaciju

završni rad

• Naslov (engleski): Phylogenetic tree reconstruction using maximum parsimony branch-and-bound algorithm
• Autor: Ana Marija Selak
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Krešimir Križanović (član povjerenstva)
• Član povjerenstva: Andrej Novak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: metoda maksimalne uštede; matrica obilježja; razgranaj-ograniči
• Ključne riječi (engleski): maximum parsimony; character-based; branch and bound
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:116768
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 11:43:19