Skip to content

PLG

Seminar

Practical distance computation in the space of phylogenetic trees

Owen, M (Cornell)
Tuesday 18 December 2007, 10:20-10:40

Seminar Room 1, Newton Institute

Abstract

There are many different methods for constructing phylogenetic trees from biological data. To either compare one such algorithm with another, or to find the likelihood of a certain tree generated from the data, researchers often compute a distance between trees. In this talk, we present a practical algorithm for computing the geodesic distance, as well as the geodesic path, between two phylogenetic trees in the tree space introduced by Billera, Holmes, and Vogtmann(2001). In doing so, we show that the possible shortest paths between two trees can be represented as chains in a partially ordered set, whose elements are the sets formed by a closure relation on the incompatible edges between the trees. Furthermore, we give a linear time algorithm for computing the geodesic candidate corresponding to each maximal chain in this partially ordered set. Dynamic programming techniques can be used to further prune the search of the partially ordered set for the shortest path.

Presentation

[pdf ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧