Efficient Detection of Repeating Sites to Accelerate Phylogenetic Likelihood Calculations.
Syst Biol
; 66(2): 205-217, 2017 Mar 01.
Article
en En
| MEDLINE
| ID: mdl-27576546
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. [Algorithms; maximum likelihood; phylogenetic likelihood function; phylogenetics].
Texto completo:
1
Colección:
01-internacional
Base de datos:
MEDLINE
Asunto principal:
Filogenia
/
Clasificación
/
Modelos Biológicos
Tipo de estudio:
Diagnostic_studies
Idioma:
En
Revista:
Syst Biol
Asunto de la revista:
BIOLOGIA
Año:
2017
Tipo del documento:
Article
País de afiliación:
Alemania