The Library
Evolutionary trees can be learned in polynomial time in the twostate general Markov model
Tools
Cryan, Mary, Goldberg, Leslie Ann and Goldberg, Paul W.. (2001) Evolutionary trees can be learned in polynomial time in the twostate general Markov model. SIAM Journal on Computing, Volume 31 (Number 2). pp. 375397. ISSN 00975397
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/S0097539798342496
Abstract
The jstate 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 twostate general Markov model of evolution generalizes the wellknown CavenderFarrisNeyman 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 CavenderFarrisNeyman 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 polynomialtime PAClearning algorithm ( in the sense of Kearns et al. [ Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 273282]) for the general class of twostate 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 > Computer Science  
Journal or Publication Title:  SIAM Journal on Computing  
Publisher:  Society for Industrial and Applied Mathematics  
ISSN:  00975397  
Official Date:  2001  
Dates: 


Volume:  Volume 31  
Number:  Number 2  
Number of Pages:  23  
Page Range:  pp. 375397  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
URI:  http://wrap.warwick.ac.uk/id/eprint/11659 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 