Learning nonsingular phylogenies and hidden Markov models

ABSTRACT

In this paper, we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning hidden Markov models without the nonsingularity condition is at least as hard as learning parity with noise. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and hidden Markov models.

REFERENCES

• 1: Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
• 2: L. Addario-Berry, B. Chor, M. Hallett, J. Lagergren, A. Panconesi and Todd Wareham, Ancestral Maximum Likelihood of Evolutionary Trees Is Hard, Journal of Bioinformatics and Computational Biology, 2, 257--271, 2004.
• 3: A. Ambainis , R. Desper , M. Farach , S. Kannan, Nearly tight bounds on the learnability of evolution, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.524, October 19-22, 1997
• 4: J. Cavender, Taxonomy with confidence, Mathematical Biosciences, 40, 271--280, 1978.
• 5: J. T. Chang, Full Reconstruction of Markov Models on Evolutionary Trees: Identifiability and Consistency, Mathematical Biosciences, 137, 51--73, 1996.
• 6: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 7: Mary Cryan , Leslie Ann Goldberg , Paul W. Goldberg, Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model, SIAM Journal on Computing, v.31 n.2, p.375-397, 2001 [doi>10.1137/S0097539798342496]
• 8: R. Durbin, S. Eddy, A. Krogh, and G. Mitchison, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
• 9: R. Durrett, Probability: Theory and Examples, Duxbury, 1996.
• 10: Péter L. Erdös , Michael A. Steel , Lázló A. Székely , Tandy J. Warnow, A few logs suffice to build (almost) all trees (l): part I, Random Structures & Algorithms, v.14 n.2, p.153-184, March 1999 [doi>10.1002/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R ]
• 11: Péter L. Erdös , Michael A. Steel , László A. Székely , Tandy J. Warnow, A few logs suffice to build (almost) all trees: part II, Theoretical Computer Science, v.221 n.1-2, p.77-118, June 28, 1999 [doi>10.1016/S0304-3975(99)00028-6 ]
• 12: J. Felsenstein. Inferring Phylogenies. Sinauer, New York, New York, 2004.
• 13: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.230-236, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237868]
• 14: J. Feldman and R. O'Donnell and R. Servedio. Learning mixtures of product distributions, preprint, 2004.
• 15: J. Felsenstein, Cases in which parsimony or compatibility methods will be positively misleading, Systematic Zoology, 27, 410--410, 1978.
• 16: G. H. Golub and C. H. Van Loan, Matrix Computations, Johns Hopkins University Press, 1996.
• 17: R. L. Graham and L. R. Foulds, Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time, Mathematical Biosciences, 60, 133--142, 1982.
• 18: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 19: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
• 20: Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
• 21: Rune B. Lyngsø , Christian N. S. Pedersen, Complexity of Comparing Hidden Markov Models, Proceedings of the 12th International Symposium on Algorithms and Computation, p.416-428, December 19-21, 2001
• 22: E. Mossel, Distorted metrics on trees and phylogenetic forests, preprint, 2004 (available at http://arxiv.org/math.CO/0403508).
• 23: E. Mossel and S.Roch, Learning Nonsingular Phylogenies and Hidden Markov Models, preprint, 2005 (available at http://arxiv.org/cs.LG/0502076).
• 24: L. R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Proceedings of the IEEE, 77(2), 257--286, 1989.
• 25: Kenneth Rice , Tandy Warnow, Parsimony is Hard to Beat, Proceedings of the Third Annual International Conference on Computing and Combinatorics, p.124-133, August 20-22, 1997
• 26: Dana Ron , Yoram Singer , Naftali Tishby, On the learnability and usage of acyclic probabilistic finite automata, Journal of Computer and System Sciences, v.56 n.2, p.133-152, April 1998 [doi>10.1006/jcss.1997.1555 ]
• 27: C. Semple and M. Steel. Phylogenetics, volume 22 of Mathematics and its Applications series. Oxford University Press, 2003.
• 28: M. Steel, Recovering a tree from the leaf colourations it generates under a Markov model, Appl. Math. Lett. 7(2), 19--24, 1994.
• 29: M. A. Steel, L. A. Szekely, and M. D. Hendy, Reconstructing trees when sequence sites evolve at variable rates, J. Comput. Biol. 1(2), 153--63, 1994.
• 30: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms

Keywords:
PAC learning, evolutionary trees, hidden Markov models, phylogenetic reconstruction