We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees on $n$ leaves have a maximum agreement subtree (MAST) of size at least $n^{\frac{1}{2}}$. In particular, we show that for any $c>0$, there exist two balanced rooted binary leaf-labeled trees on $n$ leaves such that any MAST for these two trees has size less than $c n^{\frac{1}{2}}$. We also improve the lower bound of the size of such a MAST to $n^{\frac{1}{6}}$.

Tree-based phylogenetic networks, which may be roughly defined as leaf-labeled networks built by adding arcs only between the original tree edges, have elegant properties for modeling evolutionary histories. We answer an open question of Francis, Semple, and Steel about the complexity of determining how far a phylogenetic network is from being tree-based, including non-binary phylogenetic networks. We show that finding a phylogenetic tree covering the maximum number of nodes in a phylogenetic network can be computed in polynomial time via an encoding into a minimum-cost flow problem.

We present a fast and robust atlas-based algorithm for labeling airway trees, using geodesic distances in a geometric tree-space. Possible branch label configurations for an unlabeled airway tree are evaluated using distances to a training set of labeled airway trees. In tree-space, airway tree topology and geometry change continuously, giving a natural automatic handling of anatomical differences and noise. A hierarchical approach makes the algorithm efficient, assigning labels from the trachea and downwards. Only the airway centerline tree is used, which is relatively unaffected by pathology. The algorithm is evaluated on 80 segmented airway trees from 40 subjects at two time points, labeled by three medical experts each, testing accuracy, reproducibility and robustness in patients with chronic obstructive pulmonary disease (COPD). The accuracy of the algorithm is statistically similar to that of the experts and not significantly correlated with COPD severity. The reproducibility of the algorithm is significantly better than that of the experts, and negatively correlated with COPD severity. Evaluation of the algorithm on a longitudinal set of 8724 trees from a lung cancer screening trial shows that the algorithm can be used in large scale studies with high reproducibility, and that the negative correlation of reproducibility with COPD severity can be explained by missing branches, for instance due to segmentation problems in COPD patients. We conclude that the algorithm is robust to COPD severity given equally complete airway trees, and comparable in performance to that of experts in pulmonary medicine, emphasizing the suitability of the labeling algorithm for clinical use.

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 $\mathbb{R}^k$ contained in the subspace of $\mathbb{R}^k$ consisting of all orthants with the first i coordinates nonpositive and the remaining coordinates nonnegative for $0 \leq i \leq k$.

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.