Hadamard Conjugation for the Kimura 3ST Model: Combinatorial Proof Using Path Sets
Pages 461 - 471
Abstract
Under a stochastic model of molecular sequence evolution the probability of each possible pattern of a characters is well defined. The Kimura's three-substitution-types (K3ST) model of evolution, allows analytical expression for these probabilities of by means of the Hadamard conjugation as a function of the phylogeny T and the substitution probabilities on each edge of TM . In this paper we produce a direct combinatorial proof of these results, using pathset distances which generalise pairwise distances between sequences. This interpretation provides us with tools that were proved useful in related problems in the mathematical analysis of sequence evolution.
References
[1]
E.S. Allman and J.A. Rhodes, "Phylogenetic Invariants for the General Markov Model of Sequence Mutation," Math. Biosciences, vol. 186, pp. 113-144, 2003.
[2]
E.S. Allman and J.A. Rhodes, "Quartets and Parameter Recovery for the General Markov Model of Sequence Mutation," Applied Math. Research eXpress, vol. 4, pp. 107-131, 2004.
[3]
E.S. Allman and J.A. Rhodes, "Phylogenetic Ideals and Varieties for the General Markov Model," Advances in Applied Math., vol. 40, no. 2, pp. 127-148, 2008.
[4]
M. Casanellas and J. Fernández-Sánchez, "Performance of a New Invariants Method on Homogeneous and Nonhomogeneous Quartet Trees," Molecular Biology and Evolution, vol. 24, no. 1, pp. 288-293, 2007.
[5]
B. Chor, M.D. Hendy, and S. Snir, "Maximum Likelihood Jukes-Cantor Triplets: Analytic Solutions," Molecular Biology and Evolution , vol. 23, no. 3, pp. 626-632, 2006.
[6]
B. Chor, A. Khetan, and S. Snir, "Maximum Likelihood on Four Taxa Phylogenetic Trees: Analytic Solutions," Proc. Seventh Ann. Int'l Conf. Computational Molecular Biology (RECOMB '03), pp. 76- 83, 2003.
[7]
B. Chor and S. Snir, "Molecular Clock Fork Phylogenies: Closed Form Analytic Maximum Likelihood Solutions," Systematic Biology, vol. 53, no. 6, pp. 963-967, 2004.
[8]
B. Chor, M. Hendy, B. Holland, and D. Penny, "Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach," Molecular Biology and Evolution, vol. 17, pp. 1529-1541, 2000.
[9]
S.N. Evans and T.P. Speed, "Invariants of Some Probability Models Used in Phylogenetic Inference," Annals of Statistics, vol. 21, pp. 355-377, 1993.
[10]
M.D. Hendy, "The Relationship between Simple Evolutionary Tree Models and Observable Sequence Data," Systematic Zoology, vol. 38, pp. 310-321, 1989.
[11]
M.D. Hendy, "A Combinatorial Description of the Closest Tree Algorithm for Finding Evolutionary Trees," Discrete Math., vol. 96, pp. 51-58, 1991.
[12]
M.D. Hendy, "Hadamard Conjugation: An Analytic Tool for Phylogenetics," Math. of Evolution and Phylogeny, chapter 6, first ed., O. Gascuel, ed., pp. 143-177, Oxford Univ. Press, 2005.
[13]
M.D. Hendy and D. Penny, A Framework for the Quantitative Study of Evolutionary Trees, Systematic Zoology, vol. 38, pp. 297-309, 1989.
[14]
M.D. Hendy and D. Penny, "Spectral Analysis of Phylogenetic Data," J. Classification, vol. 10, pp. 5-24, 1993.
[15]
M.D. Hendy and D. Penny, "Complete Families of Linear Invariants for Some Stochastic Models of Sequence Evolution with and without the Molecular Clock Assumption," J. Computational Biology, vol. 3, pp. 19-31, 1996.
[16]
M.D. Hendy, D. Penny, and M.A. Steel, "A Discrete Fourier Analysis for Evolutionary Trees," Proc. Nat'l Academy of Sciences, vol. 91, pp. 3339-3343, 1994.
[17]
B. Holland, D. Penny, and M. Hendy, "Outgroup Misplacement and Phylogenetic Inaccuracy under a Molecular Clock--A Simulation Study," Systematic Biology, vol. 52, pp. 229-238, 2003.
[18]
K.T. Huber, M. Langton, D. Penny, V. Moulton, and M. Hendy, "Spectronet: A Package for Computing Spectra and Median Networks," Applied Bioinformatics, vol. 1, pp. 159-161, 2002.
[19]
T.H. Jukes and C.R. Cantor, "Evolution of Protein Molecules," Mammalian Protein Metabolism III, H.N. Munro, ed., Academic Press, 1969.
[20]
M. Kimura, "A Simple Method for Estimating Evolutionary Rates of Base Substitutions through Comparative Studies of Nucleotide Sequences," J. Molecular Evolution, vol. 16, pp. 111-120, 1980.
[21]
M. Kimura, "Estimation of Evolutionary Distances between Homologous Nucleotide Sequences," Proc. Nat'l Academy of Sciences, vol. 78, pp. 454-458, 1981.
[22]
J.L. Neyman, "Molecular Studies of Evolution: A Source of Novel Statistical Problems," Statistical Decision Theory and Related Topics, S.S. Gupta and J. Yackel, eds., Academic Press, 1971.
[23]
L. Pachter and B. Sturmfels, Algebraic Statistics for Computational Biology. Cambridge Univ. Press, 2005.
[24]
L. Pachter and B. Sturmfels, "The Mathematics of Phylogenomics," submitted for publication.
[25]
M.A. Steel, M.D. Hendy, L.A. Székely, and P.L. Erdös, "Spectral Analysis and a Closest Tree Method for Genetic Sequences," Applied Math. Letters, vol. 5, pp. 63-67, 1992.
[26]
M.A. Steel, M.D. Hendy, and D. Penny, "Reconstructing Phylogenies from Nucleotide Pattern Probabilities: A Survey and Some New Results," Discrete Applied Math., vol. 88, pp. 367-396, 1998.
[27]
B. Sturmfels and S. Sullivant, "Toric Ideals of Phylogenetic Invariants," J. Computational Biology, vol. 12, pp. 204-228, 2005.
[28]
L. Székely, P.L. Erdös, M.A. Steel, and D. Penny, "A Fourier Inversion Formula for Evolutionary Trees," Applied Math. Letters, vol. 6, pp. 13-17, 1993.
[29]
L. Székely, M.A. Steel, and P.L. Erdös, "Fourier Calculus on Evolutionary Trees," Advances in Applied Math., vol. 14, pp. 200- 216, 1993.
[30]
P.J. Waddell and M.D. Hendy, "Using Phylogenetic Invariants to Enhance Spectral Analysis of Nucleotide Sequence Data," Information and Math. Sciences Report Series B, Massey Univ., 1997.
Index Terms
- Hadamard Conjugation for the Kimura 3ST Model: Combinatorial Proof Using Path Sets
Recommendations
Hadamard Matrices and Dihedral Groups
Special issue containing papers presented at the Second Upper Michigan Combinatorics Workshop on Designs, Codes and GeometriesLet D_{2p} be a dihedral group of order 2p , where p is an odd integer. Let ZD_{2p} be the group ring of D_{2p} over the ring Z of integers. We identify elements of ZD_{2p} and their matrices of the regular representation of ZD_{2p} . Recently we ...
Difference sets and doubly transitive actions on Hadamard matrices
Non-affine groups acting doubly transitively on a Hadamard matrix have been classified by Ito. Implicit in this work is a list of Hadamard matrices with non-affine doubly transitive automorphism group. We give this list explicitly, in the process ...
Cocyclic Hadamard matrices over Latin rectangles
AbstractIn the literature, the theory of cocyclic Hadamard matrices has always been developed over finite groups. This paper introduces the natural generalization of this theory to be developed over Latin rectangles. In this regard, once we ...
Comments
Information & Contributors
Information
Published In
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 July 2008
Published in TCBB Volume 5, Issue 3
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 1,641Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in