Evolutionary Trees can be Learned in Polynomial-Time in the Two-State General Markov Model - Danish National Research Database-Den Danske Forskningsdatabase

Cryan, Mary^{2}; Goldberg, Leslie Ann^{2}; Goldberg, Paul Wilfred^{2}

Affiliations:

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} unknown

Abstract:

The j-state general Markov model of evolution (due to Steel) is a stochastic model concerned with the evolution of strings over an alphabet of size j. In particular, the two-state general Markov model of evolution generalizes the well-known Cavender-Farris-Neyman model of evolution by removing the symmetry restriction (which requires that the probability that a "0" turns into a "1" along an edge is the same as the probability that a "1" turns into a "0" along the edge). Farach and Kannan showed how to probably approximately correct (PAC)-learn Markov evolutionary trees in the Cavender--Farris--Neyman model provided that the target tree satisfies the additional restriction that all pairs of leaves have a sufficiently high probability of being the same. We show how to remove both restrictions and thereby obtain the first polynomial-time PAC-learning algorithm (in the sense of Kearns et al. [Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 273--282]) for the general class of two-state Markov evolutionary trees.

Type:

Journal article

Language:

English

Published in:

Proceedings 39th Annual Symposium on Foundations of Computerscience (cat. No.98cb36280), 2001, Vol Session 6B, Issue 4, p. 436-445