×

Counting labeled transitions in continuous-time Markov models of evolution. (English) Zbl 1145.60323

Summary: Counting processes that keep track of labeled changes to discrete evolutionary traits play critical roles in evolutionary hypothesis testing. If we assume that trait evolution can be described by a continuous-time Markov chain, then it suffices to study the process that counts labeled transitions of the chain. For a binary trait, we demonstrate that it is possible to obtain closed-form analytic solutions for the probability mass and probability generating functions of this evolutionary counting process. In the general, multi-state case we show how to compute moments of the counting process using an eigen decomposition of the infinitesimal generator, provided the latter is a diagonalizable matrix. We conclude with two examples that demonstrate the utility of our results.

MSC:

60J27 Continuous-time Markov processes on discrete state spaces
92D15 Problems related to evolution
92D20 Protein sequences, DNA sequences

Software:

Seq-Gen; fastDNAml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adachi J. and Hasegawa M. (1996). Model of amino acid substitution in proteins encoded by mitochondrial DNA. J. Mol. Evol. 42: 459–468 · doi:10.1007/BF02498640
[2] Ball F. (1997). Empirical clustering of bursts of openings in Markov and semi-Markov models of single channel gating incorporating time interval omission. Adv. Appl. Probab. 29: 909–946 · Zbl 0903.60058 · doi:10.2307/1427847
[3] Ball F. and Milne R.K. (2005). Simple derivations of properties of counting processes associated with Markov renewal processes. J. Appl. Probab. 42: 1031–1043 · Zbl 1106.60069 · doi:10.1239/jap/1134587814
[4] Chatfield C. (2004). The Analysis of Time Series: An Introduction. Chapman & Hall, London · Zbl 1050.62089
[5] Darroch J.N and Morris K.W. (1967). Some passage-time generating functions for discrete-time and continuous-time finite Markov chains. J. Appl. Probab. 4: 496–507 · Zbl 0159.46803 · doi:10.2307/3212217
[6] Felsenstein J. (1981). Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 13: 93–104
[7] Felsenstein J. (2004). Inferring Phylogenies. Sinauer Associates Inc., Sunderland
[8] Fitch W.M., Bush R.M., Bender C.A. and Cox N.J. (1997). Long term trends in the evolution of H(3) HA1 human influenza type A. Proc. Natl. Acad. Sci. USA 94: 7712–7718 · doi:10.1073/pnas.94.15.7712
[9] Guttorp P. (1995). Stochastic Modeling of Scientific Data. Chapman & Hall, Suffolk · Zbl 0862.60034
[10] Hasegawa M., Kishino H. and Yano T. (1985). Dating the human-ape splitting by a molecular clock of mitochondrial DNA. J. Mol. Evol. 22: 160–174 · doi:10.1007/BF02101694
[11] Henikoff S. and Henikoff J.G. (1992). Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. USA 89: 10915–10919 · doi:10.1073/pnas.89.22.10915
[12] Hobolth, A., Jensen, J.L.: Statistical inference in evolutionary models of DNA sequences via the EM algorithm. Stat. Appl. Gen. Mol. Biol. 4, Article 18 (2005) · Zbl 1081.62094
[13] Kass R.E. and Raftery A.E. (1995). Bayes factors. J. Am. Stat. Assoc. 90: 773–795 · Zbl 0846.62028 · doi:10.2307/2291091
[14] Meng X.L. (1994). Posterior predictive P-values. Ann. Stat. 22: 1142–1160 · Zbl 0820.62027 · doi:10.1214/aos/1176325622
[15] Narayana S. and Neuts M.F. (1992). The first two moment matrices of the counts for the Markovian arrival process. Stoch. Models 8: 459–477 · Zbl 0756.60095 · doi:10.1080/15326349208807234
[16] Neuts M.F. (1979). A versatile Markovian point process. J. Appl. Probab. 16: 764–779 · Zbl 0422.60043 · doi:10.2307/3213143
[17] Neuts M.F. (1992). Models based on the Markovian arrival process. IEICE Trans. Commun. E75-B: 1255–1265
[18] Neuts M.F. (1995). Algorithmic Probability: a Collection of Problems. Chapman and Hall, London · Zbl 0870.60002
[19] Nielsen R. (2002). Mapping mutations on phylogenies. Syst. Biol. 51: 729–739 · doi:10.1080/10635150290102393
[20] Nielsen R. (2005). Molecular signatures of natural selection. Ann. Rev. Gen. 39: 197–218 · doi:10.1146/annurev.genet.39.073003.112420
[21] Oakley T.H. and Cunningham C.W. (2002). Molecular phylogenetic evidence for the independent evolutionary origin of an arthropod compound eye. Proc. Natl. Acad. Sci. USA 99: 1426–1430 · doi:10.1073/pnas.032483599
[22] Pagel M. (1994). Detecting correlated evolution on phylogenies: a general method for the comparative analysis of discrete characters. Proc. R. Soc. B 255: 37–45 · doi:10.1098/rspb.1994.0006
[23] Pagel M. (1999). The maximum likelihood approach to reconstructing ancestral character states of discrete characters on phylogenies. Syst. Biol. 48: 612–622 · doi:10.1080/106351599260184
[24] Pollock D.D., Taylor W.R. and Goldman N. (1999). Coevolving protein residues: maximum likelihood identification and relationship to structure. J. Mol. Biol. 287: 187–198 · doi:10.1006/jmbi.1998.2601
[25] Rambaut A. and Grassly N.C. (1997). Seq-Gen: An application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Comput. Appl. Biosci. 13: 235–238
[26] Schadt E. and Lange K. (2002). Codon and rate variation models in molecular phylogeny. Mol. Biol. Evol. 19: 1534–1549
[27] Schadt E.E., Sinsheimer J.S. and Lange K. (1998). Computational advances in maximum likelihood methods for molecular phylogeny. Genome Res. 8: 222–233
[28] Siepel, A., Pollard, K.S., Haussler, D.: New methods for detecting lineage-specific selection. In: Proceedings of the 10th international conference on research in computational molecular biology, pp. 190–205 (2006) · Zbl 1302.92092
[29] Suchard M.A., Weiss R.E., Dorman K.S. and Sinsheimer J.S. (2002). Inferring spatial phylogenetic variation along nucleotide sequences: a multiple change-point model. J. Am. Stat. Assoc. 98: 427–437 · Zbl 1041.62095 · doi:10.1198/016214503000215
[30] Templeton A.R. (1996). Contingency tests of neutrality using intra/interspecific gene trees: the rejection of neutrality for the evolution of the mitochondrial cytochrome oxidase II gene in the hominoid primates. Genetics 144: 1263–1270
[31] Yang Z. (1994). Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites: approximate methods. J. Mol. Evol. 39: 306–314 · doi:10.1007/BF00160154
[32] Yang Z. (1995). A space-time process model for the evolution of DNA sequences. Genetics 139: 993–1005
[33] Yang Z., Nielsen R., Goldman N. and Pedersen A.M.K. (2000). Codon-substitution models for heterogeneous selection pressure at amino acid sites. Genetics 155: 431–449
[34] Zheng Q. (2001). On the dispersion index of a Markovian molecular clock. Math. Biosci. 172: 115–128 · Zbl 0989.92018 · doi:10.1016/S0025-5564(01)00067-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.