Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model
Authors: Mary Cryan ; Leslie Ann Goldberg ; Paul W Goldberg
Date: 2002
Publication Title:SIAM Journal on Computing
Publisher:Society for Industrial and Applied Mathematics
Publication Type:Journal Article Publication Status:Published
Volume No:31(2) Page Nos:375-397
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 satisfies 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 first 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.
Links To Paper
This is the Journal webpage for this paper, with links to .ps and .pdf versions.
Mary Cryan's publications webpage, which also has a copy of the paper.
Bibtex format
author = { Mary Cryan and Leslie Ann Goldberg and Paul W Goldberg },
title = {Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model},
journal = {SIAM Journal on Computing},
publisher = {Society for Industrial and Applied Mathematics},
year = 2002,
volume = {31(2)},
pages = {375-397},
doi = {10.1137/S0097539798342496},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh