Nguyen, L.-T. (2011). An efficient algorithm for phylogeny reconstruction by maximum likelihood [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160135
phylogeny reconstruction; maximum likelihood; metaheuristics; Algorithms; Iterated Local Search
en
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 />