UC Berkeley

This dissertation discusses how to write efficient, deterministic

programs to infer phylogenetic trees. These programs are based on a

theoretically optimal polynomial time algorithm. The programs are

practical and efficient.

The problem is to infer phylogenetic trees from sequence data at the

leaves. Likelihood approaches attempt to solve an NP-complete

optimization problem, and are computationally intense.

Our approach is to apply efficient, polynomial time algorithms which

are provably accurate to within a constant factor of optimal.

We present a program which is practical and computationally efficient.