Evolutionary trees can be learned in polynomial time in the two-state general Markov model

Citation
M. Cryan et al., Evolutionary trees can be learned in polynomial time in the two-state general Markov model, SIAM J COMP, 31(2), 2001, pp. 375-397
Citations number
14
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
375 - 397
Database
ISI
SICI code
0097-5397(20011011)31:2<375:ETCBLI>2.0.ZU;2-7
Abstract
The j-state general Markov model of evolution ( due to Steel) is a stochast ic model concerned with the evolution of strings over an alphabet of size j . In particular, the two-state general Markov model of evolution generalize s 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 in to a "0" along the edge). Farach and Kannan showed how to probably approxim ately correct ( PAC)-learn Markov evolutionary trees in the Cavender-Farris -Neyman model provided that the target tree satis es the additional restric tion 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 r st polynomial-time PAC-learning algorithm ( in the sense of Kearns et al. [ Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1 994, pp. 273-282]) for the general class of two-state Markov evolutionary t rees.