**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

You are here: Homepage » Seminars - Academic year 2023-24 » Combinatorics Seminar » Megan Owen (Cornell)

seminars:comb:abstract.200803owe

What is the distance between two phylogenetic (evolutionary) trees and how can we efficiently compute it? In a 2001 paper, Billera, Holmes and Vogtmann constructed a space containing all phylogenetic trees, and showed the distance between the points corresponding to trees in this space is a reasonable inter-tree distance measure. I present a practical algorithm to compute this distance, showing that the possible shortest paths between two trees can be represented as a partially ordered set, and giving a linear time algorithm for computing the shortest path through a certain Euclidean subspace. Dynamic programming techniques can be used to further prune the search of the partially ordered set for the shortest path.

seminars/comb/abstract.200803owe.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported