Tree Space (Joint work with my graduate student Jonathan Ingram.)
Abstract
There is a well-known topology on the space of all trees with given taxa, where each edge has a length. (These are usually called weighted trees.) I will describe this topology and define some metrics on it, including the L^2 metric of Billera, Holmes and Vogtmann. We have not studied these different metrics extensively in a biological context, but it seems as though the L^1 metric is the most biologically informative. To compute the L^1 distance between two trees is computationally trivial. Computing L^2 distances is a difficult problem, and it may turn out to be NP, in one of the many senses of NP. On the other hand, I like the L^2 distance a lot, because it has beautiful mathematical properties (discovered by Billera, Holmes and Vogtmann). I will present a nice algorithm for computing the L^2-distance, much quicker than any naive algorithm, and will sketch the non-trivial proof that the algorithm gives the correct answer.
If I can prepare the results before the meeting, I may present some applications in biology of some of our computer programs.