Informatics Report Series






Title:Evolutionary Trees can be Learned in Polynomial Time in the TwoState General Markov Model 
Authors:
Mary Cryan
; Leslie Ann Goldberg
; Paul W Goldberg

Date: 2002 
Publication Title:SIAM Journal on Computing 
Publisher:Society for Industrial and Applied Mathematics 
Publication Type:Journal Article
Publication Status:Published

Volume No:31(2)
Page Nos:375397

DOI:10.1137/S0097539798342496

 Abstract:

The jstate 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 twostate general Markov model of evolution generalizes the wellknown CavenderFarrisNeyman 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 CavenderFarrisNeyman 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 polynomialtime PAClearning algorithm (in the sense of Kearns et al. [Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 273282]) for the general class of twostate Markov evolutionary trees.
 Links To Paper
 This is the Journal webpage for this paper, with links to .ps and .pdf versions.
 Mary Cryan's publications webpage, which also has a copy of the paper.
 Bibtex format
 @Article{EDIINFRR0465,
 author = {
Mary Cryan
and Leslie Ann Goldberg
and Paul W Goldberg
},
 title = {Evolutionary Trees can be Learned in Polynomial Time in the TwoState General Markov Model},
 journal = {SIAM Journal on Computing},
 publisher = {Society for Industrial and Applied Mathematics},
 year = 2002,
 volume = {31(2)},
 pages = {375397},
 doi = {10.1137/S0097539798342496},
 url = {http://epubs.siam.org/sambin/dbq/article/34249},
 }
