期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 25, 期 4, 页码 1506-1529出版社
SIAM PUBLICATIONS
DOI: 10.1137/090751396
关键词
phylogeny; tree space; geodesic distance; computational geometry; shortest path
资金
- NSF at Cornell University [DMS-0555268]
We present two algorithms for computing the geodesic distance between phylogenetic trees in tree space, as introduced by Billera, Holmes, and Vogtmann [Adv. Appl. Math., 27 ( 2001), pp. 733 767]. We show that the possible combinatorial types of shortest paths between two trees can be compactly represented by a partially ordered set. We calculate the shortest distance along each candidate path by converting the problem into one of finding the shortest path through a certain region of Euclidean space. In particular, we show there is a linear time algorithm for finding the shortest path between a point in the all-positive orthant and a point in the all-negative orthant of R-k contained in the subspace of R-k consisting of all orthants with the first i coordinates nonpositive and the remaining coordinates nonnegative for 0 <= i <= k.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据