Kobert, K;
Stamatakis, A;
Flouri, T;
(2017)
Efficient Detection of Repeating Sites to Accelerate Phylogenetic Likelihood Calculations.
Systematic Biology
, 66
(2)
pp. 205-217.
10.1093/sysbio/syw075.
Preview |
Text
Flouris_syw075.pdf - Published Version Download (792kB) | Preview |
Abstract
The phylogenetic likelihood function (PLF) is the major computational bottleneck in several applications of evolutionary biology such as phylogenetic inference, species delimitation, model selection, and divergence times estimation. Given the alignment, a tree and the evolutionary model parameters, the likelihood function computes the conditional likelihood vectors for every node of the tree. Vector entries for which all input data are identical result in redundant likelihood operations which, in turn, yield identical conditional values. Such operations can be omitted for improving run-time and, using appropriate data structures, reducing memory usage. We present a fast, novel method for identifying and omitting such redundant operations in phylogenetic likelihood calculations, and assess the performance improvement and memory savings attained by our method. Using empirical and simulated data sets, we show that a prototype implementation of our method yields up to 12-fold speedups and uses up to 78% less memory than one of the fastest and most highly tuned implementations of the PLF currently available. Our method is generic and can seamlessly be integrated into any phylogenetic likelihood implementation.
| Type: | Article |
|---|---|
| Title: | Efficient Detection of Repeating Sites to Accelerate Phylogenetic Likelihood Calculations |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1093/sysbio/syw075 |
| Publisher version: | http://doi.org/10.1093/sysbio/syw075 |
| Language: | English |
| Additional information: | Copyright © The Author(s) 2016. Published by Oxford University Press, on behalf of the Society of Systematic Biologists. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Algorithms, maximum likelihood, phylogenetic likelihood function, phylogenetics |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Div of Biosciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Div of Biosciences > Genetics, Evolution and Environment |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10047989 |
Archive Staff Only
 |
View Item |
