Abstract.-Most models and algorithms developed to perform statistical inference from DNA data make the assumption that substitution processes affecting distinct nucleotide sites are stochastically independent. This assumption ensures both mathematical and computational tractability but is in disagreement with observed data in many situations-one wellknown example being CpG dinucleotide hypermutability in mammalian genomes. In this paper, we consider the class of RN95 + YpR substitution models, which allows neighbor-dependent effects-including CpG hypermutability-to be taken into account, through transitions between pyrimidine-purine dinucleotides. We show that it is possible to adapt inference methods originally developed under the assumption of independence between sites to RN95 + YpR models, using a mathematically rigorous framework provided by specific structural properties of this class of models. We assess how efficient this approach is at inferring the CpG hypermutability rate from aligned DNA sequences. The method is tested on simulated data and compared against several alternatives; the results suggest that it delivers a high degree of accuracy at a low computational cost. We then apply our method to an alignment of 10 DNA sequences from primate species. Model comparisons within the RN95 + YpR class show the importance of taking into account neighbor-dependent effects. An application of the method to the detection of hypomethylated islands is discussed. [CpG hypermutability; CpG islands; maximum likelihood phylogeny; neighbor-dependent substitution.] Many stochastic models of nucleotide substitution have been developed since the early work of Jukes and Cantor (1969) . They rely on increasingly elaborate Markov substitution processes as they incorporate more and more biological characteristics of actual nucleotide substitution processes (see Yang 1996; Lió and Goldman 1998; Felsenstein 2004 for an overview of evolutionary models). The most common models are based on a 4 × 4 rate matrix describing a neighbor-independent Markov nucleotide substitution process. Such a matrix comprises 12 substitution rates, and biological hypotheses are usually built into the model to somehow constrain the parameters and have it reflect some relevant biological features. These models are mathematically tractable and allow for the development of efficient algorithms for phylogenetic inference, using, for example, maximum likelihood or Bayesian methods. Early algorithms made use of the assumptions that the sequences were at equilibrium and evolved under a reversible substitution model. To accommodate for situations where these assumptions are not met, more general maximum likelihood algorithms were developed, which can handle nonreversible and nonstationary situations, and still are very efficient at performing inference, see Felsenstein (2004) . An important property shared by the models just described is neighbor independence: The matrix of substitution rates at a site is unaffected by the base composition at other sites in the sequence. As a consequence, the substitution processes affecting distinct sites in the sequence are stochastically independent, and, for example, the long-term frequency of a dinucleotide xy has to be equal to the product of the long-term frequencies of x and y. Statistical analyses have shown that, for many genomes, this is not true (Burge et al. 1992; Karlin and Burge 1995) , even in noncoding regions. In mammalian genomes, the most important neighbordependent effect comes from the hypermutability of CpG dinucleotides: Because of cytosine methylation, the substitution rate of a CpG dinucleotide into TpG or CpA is about 10 times higher than the overall substitution rate of a C into a T or a G into an A (Bird 1980; Nachman and Crowell 2000; Zhang et al. 2007 ). The problem of extending available inference tools to include models that take into account such neighbor-dependent substitution rates is thus biologically relevant. The main difficulty with neighbor-dependent substitution rates lies in the propagation of dependencies from site to site. Technically speaking, models with neighbordependent substitution rates lead to arbitrarily longrange dependencies, even though these dependencies are most often expected to decay exponentially fast along the sequence. The complexity of such processes is usually impossible to handle exactly, and either approximations or simulation-based methods have to be used. One approach is to approximate the complicated dependence structure induced by the model, by a simpler structure leading to tractable computations. A surrogate for the original likelihood of the model can thus be computed and exploited within a maximum likelihood or a
A different direction is the prediction of the rates of variation of the nucleotides in the RNA sequences of successive generations of the virus REF .
Accurate Estimation of Substitution Rates with Neighbor-Dependent Models in a Phylogenetic Context
Systematic biology
Systematic biology
Medicine Biology