An algebraic metric for phylogenetic trees

The definition of similarity measures for phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in databases, and the assessment of phylogenetic reconstruction methods. The transposition distance for fully resolved trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this work, we generalize the transposition metric from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees (up to isomorphisms) with a fixed number of labeled leaves into a symmetric group. We also show that this transposition distance can be computed in linear time and we establish some of its basic properties.     

Slim sets of binary trees

A classical problem in phylogenetic tree analysis is to decide whether there is a phylogenetic tree T that contains all information of a given collection P of phylogenetic trees. If the answer is “yes” we say that P is compatible and T displays P. This decision problem is NP-complete even if all input trees are quartets, that is binary trees with exactly four leaves. In this paper, we prove a sufficient condition for a set of binary phylogenetic trees to be compatible. That result is used to give a short and self-contained proof of the known characterization of quartet sets of minimal cardinality which are displayed by a unique phylogenetic tree.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

On agreement forests

Tree rearrangement operations are widely used to measure the dissimilarity between phylogenetic trees with identical leaf sets. The tree bisection and reconnection (tbr) distance for unrooted trees can be equivalently defined in terms of agreement forests. For both the tbr distance and the less general subtree prune and regraft (spr) distance, we use such forests to derive new upper and lower bounds on the maximal possible distance between two trees with n leaves.     

The continuum random tree is the scaling limit of unlabeled unrooted trees

We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.     

Extremal f-trees and embedding spaces for molecular graphs

Problems concerning embedding trees in lattice-graph or Euclidean spaces are considered. A tree is defined to be ‘almost-embeddable’ in a lattice-graph if a sequence derived from the distance degree sequence of the lattice-graph and a corresponding sequence for the tree satisfy a specified inequality. This inequality is such that every tree that is embeddable in the lattice-graph is in the set of almost-embeddable trees. For Euclidean space embeddings the lattice-graph sequence is replaced by a sequence defined in terms of sphere packing numbers. This work has two practical objectives: Firstly, to furnish a framework within which intuitive chemical and physical notions about embedding spaces can be made explicit and self-consistent. Secondly, to obtain useable criteria which will exclude from statistical mechanical averaging procedures those molecular species which are inconsistent with a postulated embedding space. The inequality proposed here meets these objectives for molecular trees and its implications for chemical and physical theory are discussed in some detail.     

Projections of the Aldous chain on binary trees: Intertwining and consistency

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→∞ continuum analog of the Aldous chain and will be taken up elsewhere.     

On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

The mean value of the squared path-difference distance for rooted phylogenetic trees

The path-difference metric is one of the oldest distances for the comparison of fully resolved phylogenetic trees, but its statistical properties are still quite unknown. In this paper we compute the mean value of the square of the path-difference metric between two fully resolved rooted phylogenetic trees with n leaves, under the uniform distribution. This complements previous work by Steel and Penny, who computed this mean value for fully resolved unrooted phylogenetic trees.     

Optimizing phylogenetic diversity across two trees

We present a polynomial-time algorithm for finding an optimal set of taxa that maximizes the weighted sum of the phylogenetic diversity across two phylogenetic trees. This resolves one of the challenges proposed as part of the Phylogenetics Programme held at the Isaac Newton Institute for Mathematical Sciences (Cambridge, 2007). It also completely closes the gap between optimizing phylogenetic diversity on one tree, which is known to be in P, and optimizing phylogenetic diversity across three or more trees, which is known to be NP-hard.     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

Visualization of Multivariate Density Estimates With Shape Trees

This article introduces graphical tools for visualizing multivariate functions, specializing to the case of visualizing multivariate density estimates. We visualize a density estimate by visualizing a series of its level sets. From each connected part of a level set a shape tree is formed. A shape tree is a tree whose nodes are associated with regions of the level set. With the help of a shape tree we define a transformation of a multivariate set to a univariate function. The shape trees are visualized with the shape plots and the location plot. By studying these plots one may identify the regions of the Euclidean space where the probability mass is concentrated. An application of shape trees to visualize the distribution of stock index returns is presented.     

On the Combinatorics of Rooted Binary Phylogenetic Trees

We study subtree-prune-and-regraft (SPR) operations on leaf-labelled rooted binary trees, also known as rooted binary phylogenetic trees. This study is motivated by the problem of graphically representing evolutionary histories of biological sequences subject to recombination. We investigate some basic properties of the induced SPR-metric on the space of leaf-labelled rooted binary trees with n leaves. In contrast to the case of unrooted trees, the number |U(T)| of trees in which are one SPR operation away from a given tree depends on the topology of T. In this paper, we construct recursion relations which allow one to determine the unit-neighbourhood size |U(T)| efficiently for any tree topology. In fact, using the recursion relations we are able to derive a simple closed-form formula for the unit-neighbourhood size. As a corollary, we construct sharp upper and lower bounds on the size of unit-neighbourhoods and investigate the diameter of . Lastly, we consider an enumeration problem relevant to population genetics.AMS Subject Classification: 05C05, 92D15.     

The cut‐tree of large trees with small heights

We destroy a finite tree of size n by cutting its edges one after the other and in uniform random order. Informally, the associated cut‐tree describes the genealogy of the connected components created by this destruction process. We provide a general criterion for the convergence of the rescaled cut‐tree in the Gromov‐Prohorov topology to an interval endowed with the Euclidean distance and a certain probability measure, when the underlying tree has branching points close to the root and height of order . In particular, we consider uniform random recursive trees, binary search trees, scale‐free random trees and a mixture of regular trees. This yields extensions of a result in Bertoin (Probab Stat 5 (2015), 478–488) for the cut‐tree of uniform random recursive trees and also allows us to generalize some results of Kuba and Panholzer (Online J Anal Combin (2014), 26) on the multiple isolation of vertices. The approach relies in the close relationship between the destruction process and Bernoulli bond percolation, which may be useful for studying the cut‐tree of other classes of trees. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 404–427, 2017     

The Splits in the Neighborhood of a Tree

A phylogenetic tree represents historical evolutionary relationships between different species or organisms. The space of possible phylogenetic trees is both complex and exponentially large. Here we study combinatorial features of neighbourhoods within this space, with respect to four standard tree metrics. We focus on the splits of a tree: the bipartitions induced by removing a single edge from the tree. We characterize those splits appearing in trees that are within a given distance of the original tree, demonstrating close connections between these splits, the Whitney number of a tree, and the binary characters with a given parsimony length.AMS Subject Classification: 68R10, 05C05, 68Q25, 92D15.     

Self-embeddings of trees

We prove a fixed point theorem for monoids of self-embeddings of trees. As a corollary, we obtain a result by Laflamme, Pouzet and Sauer that a tree either contains a subdivided binary tree as a subtree or has a vertex, an edge, an end or two ends fixed by all its self-embeddings.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004     

Consistency of the QNet algorithm for generating planar split networks from weighted quartets

Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or “QNet” method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method.