<div class="csl-bib-body">
<div class="csl-entry">Nguyen, L.-T. (2011). <i>An efficient algorithm for phylogeny reconstruction by maximum likelihood</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160135</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/160135
-
dc.description.abstract
An Efficient Algorithm for Phylogeny Reconstruction by Maximum Likelihood.<br />Understanding the evolutionary relationships among species has been of tremendous interest since Darwin published the Origin of Species (Darwin, 1859). The evolutionary history (phylogeny) of species is typically represented as a phylogenetic tree. Nowadays, the reconstructing of the evolutionary history is still a major research topic. With the rise of molecular sequencing technologies, advanced computational approaches have been proposed to reconstruct phylogenies.<br />Maximum likelihood is a statistical method for reconstructing phylogeny which gives better estimate of the true tree than those produced by other approaches. Howerver, maximum likelihood, is highly computational expensive.<br />Therefore, different heuristics haven been proposed to solve this NP-hard problem. Among these, IQPNNI (Vinh and von Haeseler, 2004) has been shown to have highly regarded results. Nevertheless, it requires a lot of computation time. In the present work we introduce an improved version of the IQPNNI algorithm called IQ-Tree. Here we focus on improving the runtime performance of IQPNNI by proposing a fast and reliable search algorithm for phylogeny reconstruction.<br />To this end, we used the metaheuristic Iterated Local Search (ILS) as our underlying search framework, from which the possibility of using the search history to improve performance has been identified. Based on the search history we propose a strategy that directs the search to move quickly through regions, in which better trees are unlikely to be found.<br />Furthermore, we introduce a vectorization technique to speed up computations in the tree evaluation function. Our results showed that IQ-Tree runs two to four times faster than IQPNNI, while the reconstructed phylogenetic trees have equal or better likelihood than those produced by IQPNNI.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.subject
Phylogenetische Rekonstruktion
de
dc.subject
Maximum-Likelihood-Methode
de
dc.subject
Metaheuristik
de
dc.subject
phylogeny reconstruction
en
dc.subject
maximum likelihood
en
dc.subject
metaheuristics
en
dc.subject
Algorithms
en
dc.subject
Iterated Local Search
en
dc.title
An efficient algorithm for phylogeny reconstruction by maximum likelihood