Authors

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.