TL;DR
This paper introduces "lcfit," a novel, four-parameter surrogate function designed to efficiently approximate one-dimensional phylogenetic likelihoods. This approximation significantly speeds up computations in phylogenetics, particularly for branch length optimization and Bayesian sampling, by providing a fast-to-evaluate substitute for computationally expensive original likelihood functions.
What Problem Does This Paper Address?
Modern phylogenetics faces a computational bottleneck due to the ever-increasing size of molecular sequence datasets and the growing complexity of evolutionary models used to describe sequence evolution. Calculating the likelihood of a phylogenetic tree under these complex models is computationally intensive. This is especially true when optimizing or sampling parameters like branch lengths, which often involves repeatedly evaluating the likelihood function. Existing methods for approximating these likelihoods, such as using standard probability distributions, have limitations in capturing the specific shapes of phylogenetic likelihood curves, particularly their behavior at short branch lengths and their non-zero asymptotes. This paper aims to bridge this gap by developing a specialized surrogate function that better mimics the characteristics of phylogenetic likelihoods.
Methods
The core of this paper is the introduction of the "lcfit" surrogate function, a four-parameter function derived from a generalized version of the simplest phylogenetic likelihood function (the binary symmetric model). The function is defined as:
$f(c, m, r, b; t) = c \log\left[\frac{1 + e^{-r(t+b)}}{2}\right] + m \log\left[\frac{1 - e^{-r(t+b)}}{2}\right]$
where $c$, $m$, $r$, and $b$ are the four parameters. The paper details two primary fitting strategies:
- lcfit4: A direct, standard nonlinear least-squares optimization to fit the four parameters of the lcfit function using sampled branch lengths and their corresponding likelihoods.
- lcfit2: A more refined approach that re-parameterizes the function in terms of the maximum likelihood branch length ($t_0$) and the second derivative at that maximum ($f''(t_0)$). This method is particularly useful when the maximum likelihood branch length is positive and aims to capture the shape of the likelihood curve more accurately.
The authors also describe a procedure for using lcfit as a proposal mechanism in rejection sampling for Bayesian Monte Carlo algorithms. This involves fitting the lcfit function to the original likelihood, then using the surrogate to generate proposals that are accepted or rejected based on a comparison with the original likelihood.
Datasets
The paper does not introduce new datasets for training or evaluation. Instead, it leverages existing benchmarks and simulation frameworks:
- Simulated Data: The authors generate simulated sequence alignments under various evolutionary models (e.g., uniform rates, discretized Gamma rates) and tree structures to test the performance of lcfit.
- Existing Benchmarks: They compare their method's performance (specifically, acceptance rates for branch length proposals) to results previously published by Aberer et al. (2016), re-using their simulation data and analysis framework.
Key Insights and Ideas
- Specialized Surrogate for Phylogenetics: The key insight is that phylogenetic likelihood functions have specific characteristics (e.g., asymptotes, behavior at zero branch length) that are not well-captured by general-purpose probability distributions. The lcfit function is specifically designed to mimic these characteristics.
- Four Parameters are Sufficient: The paper demonstrates that a relatively simple four-parameter function can effectively approximate a wide range of one-dimensional phylogenetic likelihoods across different models and tree structures.
- Efficiency Gains in Bayesian Sampling: By using lcfit as a proposal distribution in rejection sampling, the authors show it can lead to higher acceptance rates compared to other surrogate distributions, making Bayesian inference more efficient.
- Practical Implementation: The availability of lcfit as a stand-alone C library makes it easily integrable into existing phylogenetic software, facilitating its adoption.
Key Results
- Performance Comparison: lcfit achieves comparable or slightly better acceptance rates for branch length proposals than gamma and Weibull distributions in benchmarking studies, as shown in Figure 2.
- Kullback-Leibler Divergence: Simulations indicate that the KL divergence between the original likelihood and the lcfit surrogate is generally low, suggesting good approximation accuracy across various models (Figure 3). Interestingly, lcfit performed better for more complex models than for some variants of the simpler binary model.
- Computational Efficiency: While the fitting process itself requires evaluating the original likelihood, the subsequent evaluation of the surrogate function is significantly faster, leading to overall computational savings, especially in iterative optimization or sampling schemes.
Limitations and Future Work
- One-Dimensional Approximation: The current lcfit function is designed for one-dimensional likelihoods (i.e., optimizing a single branch length at a time). The authors suggest that this framework could be extended to higher-dimensional settings, such as approximating likelihoods for multiple branches around a node or for more complex move types.
- Fitting Robustness: While the fitting methods are generally robust, the paper notes that when the ML branch length is non-zero, the method can be less robust to corner cases, leading to the development of the lcfit2 fitting strategy.
- Parameter Interpretation: While the parameters $c$, $m$, and $r$ have a direct interpretation from the Binary Symmetric Model, the parameter $b$ serves primarily to truncate the function, which is a practical adjustment for fitting.
- Future Extensions: The authors envision extending the surrogate function concept to other low-dimensional settings, such as approximating likelihoods for three-taxon trees or for more complex branch length changes and tree rearrangements.
Summary updated