The Library
Evolutionary trees can be learned in polynomial time in the two-state general Markov model
Tools
Tools
Tools
UNSPECIFIED. (2001) Evolutionary trees can be learned in polynomial time in the two-state general Markov model. SIAM JOURNAL ON COMPUTING, 31 (2). pp. 375-397. ISSN 0097-5397
Full text not available from this repository.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 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 |
| Journal or Publication Title: | SIAM JOURNAL ON COMPUTING |
| Publisher: | SIAM PUBLICATIONS |
| ISSN: | 0097-5397 |
| Date: | 11 October 2001 |
| Volume: | 31 |
| Number: | 2 |
| Number of Pages: | 23 |
| Page Range: | pp. 375-397 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/11659 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
