Efficient algorithms for inverting evolution

ABSTRACT

Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection.A stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. Maximum Likelihood Estimation (MLE) methods seek the evolutionary tree which is most likely to have produced the DNA under consideration. While these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability.In this paper, we address the intractability of MLE methods as follows: We introduce a metric on stochastic process models of evolution. We show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochastic models that are close according to this metric, it needs to be given many observations. We complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (We will use the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from DNA sequence data.) The tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available.Though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. Ours is also the first polynomial-time algorithm that is proven to converge at all to the correct tree.

REFERENCES

• 1: Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
• 2: 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
• 3: CAVENDER, J. 1978. Taxonomy with confidence. Math. Biosci. 40, 271-280.
• 4: Mary Cryan , Leslie Ann Goldberg , Paul W. Goldberg, Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.436, November 08-11, 1998
• 5: 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]
• 6: 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]
• 7: FARRIS, J.S. 1972. Estimating phylogenetic trees from distance matrices. Am. Nat. 106, 645-668.
• 8: FELSENSTEIN, J. 1983. Statistical inference of phylogenies. J. Roy. Stat. Soc. A 146, 246-272.
• 9: FELSENSTEIN, J. 1988. Phylogenies from molecular sequences: Inference and reliability. Ann. Rev. Gen. 22, 521-565.
• 10: KASHYAP, R. L., AND SUBAS, S. 1974. Statistical estimation of parameters in a phylogenetic tree using a dynamic model of the substitutional process. J. Theor. Biol., 47, 74-101.
• 11: 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]
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: NEI, M. 1987. Molecular Evolutionary Genetics. Columbia University Press, New York.
• 14: STEEL, M., HENDY, M. D., AND PENNY, D. 1994. A discrete fourier analysis for evolutionary trees. Proc. Natl. Acad. Sci. 91, 3339-3343.
• 15: Mike Steel , Laszlo A. Szekely , Peter L. Erdos, The number of nucleotide sites needed to accurately reconstructlarge evolutionary trees, Certer for Discrete Mathematics & Theoretical Computer Science, 1996
• 16: SWOFFORD, D. L., AND OLSEN, G. J. 1990. Phylogeny reconstruction. In Molecular Systematics, D. M. Hillis and C. Moritz, eds. Sinauer Associates Inc., Sunderland, Mass., pp. 411-501.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms