Evolutionary trees can be learned in polynomial time in the two-state general Markov model
Cryan, Mary, Goldberg, Leslie Ann and Goldberg, Paul W.. (2001) Evolutionary trees can be learned in polynomial time in the two-state general Markov model. SIAM Journal on Computing, Volume 31 (Number 2). pp. 375-397. ISSN 0097-5397Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/S0097539798342496
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 satis es 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 rst 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.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science|
|Journal or Publication Title:||SIAM Journal on Computing|
|Publisher:||Society for Industrial and Applied Mathematics|
|Number of Pages:||23|
|Page Range:||pp. 375-397|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)
Downloads per month over past year