טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentSnir Sagi
SubjectComputational Issues in Phylogenetic Reconstruction:
Analytic Maximum Likelihood Solutions, and Convex
Recoloring
DepartmentDepartment of Computer Science
Supervisor Mr. Ben-Zion Chor


Abstract

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.