Heuristics for Phylogenetic Reconstruction under Various Probabilitstic Models

Itsik Pe'er

Sequence evolution is generally stochastically modeled as a randomally choosing the root (ancient) sequence, and then randomally mutating it, down to the sequences of the leaves (contemporary taxa). When one tries to infer the correct tree topology from the given contemporary sequences, one wishes to:
  1. Minimize complexity
  2. Best utilize the information.
I will present several heuristics that tackle this problem, along with various assumptions that simplify the general Markov model. In some scenario high probability of success can be guarenteed, even on short (polynomial) sequences.
Main reference: M. Csuros and M. Y. Kao, "Reconstructing Evolutionary Trees in a General Markov Model", submitted to ESA '99 (please do not distribute)