Importance Sampling Approximation of Sequence Evolution Models With Site-Dependence

Joseph Mathews, Scott C. Schmidler · 2025

Read Importance Sampling Approximation of Sequence Evolution Models With Site-Dependence by Joseph Mathews, Scott C. Schmidler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11461.txt.

Introduction

Likelihoods for sequence evolution with site dependence can be approximated by importance sampling, Joseph Mathews and Scott Schmidler show in a 2025 paper. In their models, transition rates at each site depend on the local sequence context. That gives a time-inhomogeneous Markov process where sites evolve under a complex dependency structure, which makes exact likelihood computation hard.

A randomized approximation algorithm computes the marginal sequence likelihood by importance sampling. Matching order upper and lower bounds on the finite-sample error are provided. For two sequences with a modest fraction of observed mutations, the sampler's cost grows with the number of mutations rather than exponentially with length. Problem-specific bounds are derived for a well-known dependent-site model from phylogenetics.

Catalog record

CREATORJoseph Mathews, Scott C. Schmidler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-11461

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Importance Sampling Approximation of Sequence Evolution Models With Site-Dependence Joseph Mathews, Scott C. Schmidler Abstract We consider models for molecular sequence evolution in which the transition rates at each site depend on the local sequence context, giving rise to a time-inhomogeneous Markov process in which sites evolve under a complex dependency structure. We introduce a randomized approximation algorithm for the marginal sequence likelihood under these models using importance sampling, and provide matching order upper and lower bounds on the finite sample approximation error. Given two sequences of length n n with r r observed mutations, we show that for practical regimes of r / n r/n , the complexity of the importance sampler does not grow exponentially n n , but rather in r r , making the algorithm practical for many applied problems. We demonstrate the use of our techniques to obtain problem-specific complexity bounds for a well-known dependent-site model from the phylogenetics literature. † † orcid: 0000-0000-0000-0000 and ?? Department of Statistical Science, Duke University , ?? ?? Department of Statistical Science, Duke University , ?? 1 Introduction 1.1 Problem: Consider a sequence of random variables \mathbf{x}=(x_{1},x_{2},\ldots,x_{n}) each taking values in some finite alphabet \scrA\ni x_{i} of size a:=|\scrA| , and evolving according to a continuous-time Markov process, thus giving rise to a stochastic process \mathbf{x}_{t}=(x_{1}(t),\ldots,x_{n}(t)) taking values in \scrA^{n} for every t\in[0,\infty) . For example, \mathbf{x} may be a DNA sequence with \scrA=\{\tA,\tG,\tC,\tT\} . We consider models in which the time evolution of \mathbf{x}_{t} is given by a time- inhomogeneous CTMC with a^{n}\times a^{n} rate matrix \tilde{\mathbf{Q}} specified by a sequence context-dependent rate function \displaystyle\tilde{\gamma}_{i}(b;\tilde{x}_{i})=\gamma_{i}(b;x_{i})\phi(b;\tilde{x}_{i})\quad\text{ for }\;b\in\scrA\setminus x_{i} (1) where \gamma_{i}:\scrA^{2}\rightarrow(0,\infty) is the context-independent rate at which x_{i}\in\scrA mutates to b , \phi:\scrA^{k+1}\rightarrow(0,\infty) is a context-dependent multiplier, and \displaystyle\tilde{x}_{i}=(x_{i_{1}},\ldots,x_{i_{k/2}},x_{i},x_{i_{k/2+1}},\ldots,x_{i_{k}}) denotes the sequence context of site x_{i} . When k=0 we have a standard sequence evolution model, with the sites evolving independently, each according to a CTMC with a\times a rate matrix \mathbf{Q} specified by \gamma_{i} (see e.g. Yang 2014 ). Examples of \mathbf{Q} include the well-known Jukes-Cantor (JC69) [ 20 ] and generalized time reversible (GTR) [ 41 ] models. Let \mathbf{y}=(y_{1},y_{2},\ldots,y_{n})=\mathbf{x}_{T} denote an observation of the process at time T . A fundamental quantity in phylogenetics is the probability that \mathbf{x} transitions to \mathbf{y} in time T : \displaystyle p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}):=\text{Pr}(\mathbf{x}_{T}=\mathbf{y}\mid\mathbf{x}_{0}=\mathbf{x})=(e^{T\tilde{\mathbf{Q}}})_{\mathbf{x},\mathbf{y}}, (2) Calculation of p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) arises in evaluating the likelihood function for a wide variety of evolutionary inference problems: the reconstruction of phylogenetic tree topologies [ 9 , 37 , 8 ] ; the estimation of divergence times (branch lengths) [ 39 , 42 , 21 ] , mutation model parameters [ 36 , 48 ] , and selection coefficients [ 12 , 51 ] ; and the reconstruction of ancestral sequences [ 30 , 50 ] , to name just a few. Most models and software packages in common use invoke the independent site model (ISM) assumption for computational tractability; namely, k=0 and the processes x_{i}(t) and x_{j}(t) are assumed to evolve independently for i\neq j . This enables straightforward calculation of p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) since under an ISM it factors site-by-site: \displaystyle p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x})=\prod^{n}_{i=1}p_{(T,\mathbf{Q})}(y_{i}\mid x_{i})=\prod^{n}_{i=1}(e^{T\mathbf{Q}})_{x_{i},y_{i}} (3) However, independent-site models fail to capture certain important features of biological evolution known to give rise to dependence among sites; examples include CpG di-nucleotide mutability [ 31 ] , enzyme-driven somatic hypermutation in B-cell affinity maturation [ 46 , 27 ] , and structural constraints in RNA and proteins [ 33 ] . In the latter case, dependencies arise between sites that are not necessarily contiguous in the DNA sequence, allowing for long-range dependence. A variety of dependent site models (DSMs) have been proposed to relax this independence assumption [ 33 , 40 , 17 , 32 , 22 , 16 , 45 , 6 , 1 , 25 ] but exact compution of p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) under models with site dependence is generally intractable since the corresponding likelihood no longer factors. Markov chain Monte Carlo (MCMC) algorithms [ 17 , 33 , 16 , 35 , 34 , 14 , 15 , 23 ] address this by sampling unobserved sequence evolution paths from \mathbf{x} to \mathbf{y} , and p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) can be obtained by marginalization over all such paths (see equation ( 5 ) in Section 2 ). However, MCMC algorithms suffer from several undesirable properties that limit their practical utility in many applications of DSMs (e.g. phylogenetic tree reconstruction), which often require repeated calculation of marginal likelihoods during iterative sampling (Bayesian MCMC) or optimization (MLE). These undesirable properties include their iterative nature and the necessity of assessing convergence empirically [ 11 , 7 ] along with the challenges of doing so in high dimensional spaces [ 2 , 44 ] , the lack of simple parallelization [ 43 ] , and the difficulty of obtaining theoretical guarantees on the accuracy of the resulting estimators, the latter requiring rare and difficult-to-obtain quantitative mixing-time bounds [ 38 , 19 ] . Moreover, estimation of marginal likelihoods directly from MCMC output is notoriously difficult [ 47 , 10 , 5 ] . In situations requiring repeated evaluation within an optimization or sampling loop, we instead desire a highly computationally efficient estimator, ideally with bounded approximation error. Here we propose an approach to approximating p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) under an arbitrary DSM using importance sampling, with instrumental distribution based on an ISM. A practical benefit of this approach is that it allows practitioners to leverage the vast software resources developed by the phylogenetics community over several decades [ 24 ] . Because calculation of the transition probability is straightforward under an ISM, and endpoint-conditioned path sampling under an ISM is feasible (see Section 2.2 ), we readily obtain an importance sampling estimator using an ISM as an instrumental distribution. Our main result is a bound on the \chi^{2} -divergence between the corresponding independent and dependent site models, which in turn provides an upper bound on the number of samples needed to approximate p_{(T,\tilde{\mathbf{Q}})}(\mathbf{y}\mid\mathbf{x}) under the DSM with \epsilon -relative error. A common shortcoming of importance sampling is that the sample complexity typically grows exponentially in the problem dimension. Here, we show that the required sample size depends on the sequence length n only through the number r of observed mutations, although it grows exponentially in r . Nevertheless, we demonstrate that our approach yields practical sample sizes on a popular DSM known as the CpG model [ 13 ] . We also provide a lower bound on the KL-divergence of the ISM and DSM models, providing conditions under which our upper bounds are near-optimal by appealing to results of Chatterjee and Diaconis 2018 . The main technical difficulty in establishing our results is that the weights (density ratio) between the ISM and DSM models \mu and \pi are not uniformly bounded, because there is no limit on the number of possible unobserved jumps along any endpoint-conditioned path from \mathbf{x} to \mathbf{y} . As a result, error bounds are not readily obtained using standard probability concentration tail bounds. Instead we directly bound the \chi^{2} -divergence by obtaining a bound on the moment generating function of the total number of such unobserved mutations. We then take advantage of a connection between the space of paths from \mathbf{x} to \mathbf{y} and the symmetric

Read the complete text