DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

             Evolutionary Trees can be Learned in Polynomial Time            
                    in the Two-State General Markov Model                    

                                  Mary Cryan                                 
                    BRICS, Department of Computer Science                    
                             University of Aarhus                            

                     Tuesday, March 13, 2001, at 2:15 PM                     
                               The Seminar Room                              


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