Hadamard Conjugation for the Kimura 3ST Model: Combinatorial Proof Using Path Sets

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: Benny Chor , Amit Khetan , Sagi Snir, Maximum likelihood on four taxa phylogenetic trees: analytic solutions, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.76-83, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640084]
• 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 , B. Sturmfels, Algebraic Statistics for Computational Biology, Cambridge University Press, New York, NY, 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: Mike Steel , Michael D. Hendy , David Penny, Reconstructing phylogenies from nucleotide pattern probabilities: a survey and some new results, Discrete Applied Mathematics, v.88 n.1-3, p.367-396, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00080-8]
• 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. A. Székely , M. A. Steel , P. L. Erdős, Fourier calculus on evolutionary trees, Advances in Applied Mathematics, v.14 n.2, p.200-216, June 1993 [doi>10.1006/aama.1993.1011]
• 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

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Trees

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Theory

Keywords:
Hadamard conjugation, K3ST model, path-sets, phylogenetic trees, phylogenetic invariants