We consider a problem motivated by evolutionary tree reconstruction: The Two-State General Markov Model of evolution (due to Steel) is a stochastic model concerned with the evolution of strings over a binary alphabet. 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 for the stochastic processes that induce mutations in the binary sequences. 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 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.) for the general class of Two-State Markov Evolutionary Trees.

This was joint research with Leslie Ann Goldberg and Paul W Goldberg.

Host: Jørgen Bang-Jensen