Evolutionary histories, or phylogenies, form an integral part of much work in biology. In addition to the intrinsic interest in the interrelationships between species, phylogenies are used for drug design, multiple sequence alignment, and even as evidence in a recent criminal trial. Much work has been done on designing algorithms that build phylogenetic trees given representative sequences of their DNA. The optimization criteria preferred by biologists for building trees is NP-hard. So, heuristics are often used that return many possible trees, instead of single optimal tree. This talk concentrates on the heuristics used for tree reconstruction, as well as how to summarize, analyze, and visualize these sets of trees. In particular, we will focus on fast reconstruction methods with provably nice properties, calculating biologically meaningful distances between trees quickly, and visualizing large sets of trees using the treecomp package designed by our group, as a module for the Mesquite system (developed by Wayne and David Maddison).

(This work is joint with Nina Amenta, David Hillis, Tamara Munzner, and Tandy Warnow and is supported by grants from the National Science Foundation.)