Abstract / Description of output
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.
Original language | English |
---|---|
Pages (from-to) | 375-397 |
Number of pages | 23 |
Journal | SIAM Journal on Computing |
Volume | 31 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2001 |