@ Comenius University in Bratislava

*Bioinformatický seminár*

Thu 27 Sep. 2012, 10:00

C

**Title:** New fast algorithms for phylogeny reconstruction

**Speaker:** Jakub Truszkowski, University of Waterloo, Canada

Due to rapid expansion in sequence databases, very fast phylogenetic reconstruction algorithms are becoming necessary. Currently, large sequence alignments can contain up to hundreds of thousands of sequences, making tra- ditional methods, such as Neighbour Joining, computationally prohibitive. To address this problem, we have developed two novel fast phylogenetic algorithms. The rst algorithm is a quartet-based heuristic that runs in O(n log n) time. It is based on a theoretical algorithm that reconstructs the correct tree, with high probability, assuming every quartet is inferred correctly with constant probability. The core of our algorithm is a balanced search tree structure that enables us to locate an edge in the tree in O(log n) time. Our algorithm is several times faster than all the current methods, while its accuracy approaches that of Neighbour Joining. This work appeared in CPM 2011 and WABI 2011. In the second part of the talk, I will present the first sub-quadratic time algorithm with theoretical performance guarantees under a Markov model of sequence evolution. Our new algorithm runs in O(n^{1+\gamma(g)} log^2 n) time, where \gamma is an increasing function of an upper bound on the mutation rate along any branch in the phylogeny, the upper bound g must be below 1/2 -\sqrt{1/8} \approx 0.15, and \gamma(g) < 1 for all g. For phylogenies with very short branches, the running time of our algorithm is close to linear. In preliminary experiments, our prototype implementation was more accurate than the current fast algorithms, while being comparably fast. This work appeared in WABI 2012.