# The Library

### Evolutionary trees can be learned in polynomial time in the two-state general Markov model

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 |