|
Informatics Report Series
|
|
|
|
|
|
|
|
|
| Title:Evolutionary Trees can be Learned in Polynomial Time in the Two-State 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:375-397
|
|
DOI:10.1137/S0097539798342496
|
- Abstract:
-
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.
- 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{EDI-INF-RR-0465,
- author = {
Mary Cryan
and Leslie Ann Goldberg
and Paul W Goldberg
},
- title = {Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model},
- journal = {SIAM Journal on Computing},
- publisher = {Society for Industrial and Applied Mathematics},
- year = 2002,
- volume = {31(2)},
- pages = {375-397},
- doi = {10.1137/S0097539798342496},
- url = {http://epubs.siam.org/sam-bin/dbq/article/34249},
- }
|
