Evolutionary trees can be learned in polynomial time in the two-state general Markov model
UNSPECIFIED (1998) Evolutionary trees can be learned in polynomial time in the two-state general Markov model. In: 39th Annual Symposium on Foundations of Computer Science, PALO ALTO, CA, NOV 08-11, 1998. Published in: 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS pp. 436-445.Full text not available from this repository.
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 generalises 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 mt edge is the same as the probability that a '1' turns into a '0' along the edge). Farach and Kannan showed how to 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 hate 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.) far the general class of Two-State Markov Evolutionary Trees.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE|
|Journal or Publication Title:||39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS|
|Publisher:||IEEE COMPUTER SOC|
|Number of Pages:||4|
|Page Range:||pp. 436-445|
|Title of Event:||39th Annual Symposium on Foundations of Computer Science|
|Location of Event:||PALO ALTO, CA|
|Date(s) of Event:||NOV 08-11, 1998|
Actions (login required)