The Library
Evolutionary trees can be learned in polynomial time in the two-state general Markov model
Tools
Tools
Tools
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-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/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 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 | ||||
|---|---|---|---|---|---|
| Alternative Title: | |||||
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||
| ISSN: | 0097-5397 | ||||
| Official Date: | 2001 | ||||
| Dates: |
|
||||
| Volume: | Volume 31 | ||||
| Number: | Number 2 | ||||
| Number of Pages: | 23 | ||||
| Page Range: | pp. 375-397 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
