Ph.D Student | Snir Sagi |
---|---|

Subject | Computational Issues in Phylogenetic Reconstruction: Analytic Maximum Likelihood Solutions, and Convex Recoloring |

Department | Department of Computer Science |

Supervisor | Mr. Ben-Zion Chor |

This thesis is
in the area of computational biology known as molecular phylogenetics.
Specifically, we focus on two issues of phylogenetics: *analytic maximum
likelihood (ML) solutions* and *minimum convex recoloring for phylogenetic
trees*. The first part is dedicated to the ML issue. Up to now, the only
known general analytical ML solution were for rooted triplets on the simplest
evolutionary model - the Neyman two states under molecular clock. We here
present three ML solutions for three different topologies on two different
evolutionary models. Each extends the existing knowledge by either considering
a ``larger'' topology, or a more general evolutionary model. The molecular clock
fork and the comb extend from three species to four while retaining the
evolutionary model. The JC triplet retains the topology and the molecular clock
assumption while extending the substitution model to four states Jukes-Cantor.

The second
part of this thesis deals with the theme of Minimum Convex Recoloring for
Phylogenetic Trees. A coloring of a tree is *convex* if the vertices that
pertain to any color induce a connected subtree. When a coloring of a tree is
not convex, it is natural to ask "how far" it is from a convex one.
That is, what is the minimal number of color changes at the vertices needed to
make the coloring convex? We show that finding each of these distances is
NP-hard even for paths. Next, we present few algorithms which, for any fixed
number of colors, solve the problem in linear time. Finally, we present
polynomial time approximation algorithms for the problem.