A 3-approximation algorithm for the subtree distance between phylogenies

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.     

A Cluster Reduction for Computing the Subtree Distance Between Phylogenies

Calculating the rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a frequently applied process in various areas of molecular evolution. However, computing this distance is an NP-hard problem and practical algorithms for computing it exactly are rare. In this paper, a divide-and-conquer approach to calculating the rSPR distance is established. This approach breaks the problem instance into a number of smaller and more tractable subproblems. Two reduction rules which were previously used to show that computing the rSPR distance is fixed-parameter tractable can easily be used to complement this new theoretical result, and so a significant positive impact on the running time of calculating this distance in practice is likely.     

A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces

Phylogenetic trees are commonly used to model the evolutionary relationships among a collection of biological species. Over the past fifteen years, the convergence properties for Markov chains defined on phylogenetic trees have been studied, yielding results about the time required for such chains to converge to their stationary distributions. In this work we derive an upper bound on the relaxation time of two Markov chains on rooted binary trees: one defined by nearest neighbor interchanges (NNI) and the other defined by subtree prune and regraft (SPR) moves.     

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 butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Isolating a Leaf in Rooted Trees via Random Cuttings

We consider a recursive procedure for destroying rooted trees and isolating a leaf by removing a random edge and keeping the subtree, which does not contain the original root. For two tree families, the simply generated tree families and increasing tree families, we study here the number of random cuts that are necessary to isolate a leaf. We can show limiting distribution results of this parameter for simply generated trees and certain increasing trees. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

On the average number of nodes in a subtree of a tree

For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least $\text{(n + 2)}\text{3}$, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least $\text{(n + 1)}\text{2}$ and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.     

Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees

. Leaf-labelled trees are widely used to describe evolutionary relationships, particularly in biology. In this setting, extant species label the leaves of the tree, while the internal vertices correspond to ancestral species. Various techniques exist for reconstructing these evolutionary trees from data, and an important problem is to determine how "far apart" two such reconstructed trees are from each other, or indeed from the true historical tree. To investigate this question requires tree metrics, and these can be induced by operations that rearrange trees locally. Here we investigate three such operations: nearest neighbour interchange (NNI), subtree prune and regraft (SPR), and tree bisection and reconnection (TBR). The SPR operation is of particular interest as it can be used to model biological processes such as horizontal gene transfer and recombination. We count the number of unrooted binary trees one SPR from any given unrooted binary tree, as well as providing new upper and lower bounds for the diameter of the adjacency graph of trees under SPR and TBR. We also show that the problem of computing the minimum number of TBR operations required to transform one tree to another can be reduced to a problem whose size is a function just of the distance between the trees (and not of the size of the two trees), and thereby establish that the problem is fixed-parameter tractable.     

The distribution of the size of the ancestor‐tree and of the induced spanning subtree for random trees

We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor‐tree of p given nodes in a rooted tree T is the subtree of T, spanned by the root and these p nodes and generalizes the depth (ancestor‐tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor‐tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all () possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulæ for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulæ for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

The shape of random tanglegrams

A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.     

A tanglegram Kuratowski theorem

A tanglegram consists of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. Tanglegrams are drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines, and the perfect matching inside the strip. If this can be done without any edges crossing, a tanglegram is called planar. We show that every nonplanar tanglegram contains one of two nonplanar 4-leaf tanglegrams as an induced subtanglegram, which parallels Kuratowski's Theorem.     

Inverse sequences, rooted trees and their end spaces

In this paper we prove that if we consider the standard real metric on simplicial rooted trees then the category Tower-Set of inverse sequences can be described by means of the bounded coarse geometry of the naturally associated trees. Using this we give a geometrical characterization of Mittag-Leffler property in inverse sequences in terms of the metrically proper homotopy type of the corresponding tree and its maximal geodesically complete subtree. We also obtain some consequences in shape theory. In particular we describe some new representations of shape morphisms related to infinite branches in trees.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

A Framework for Representing Reticulate Evolution

Acyclic directed graphs (ADGs) are increasingly being viewed as more appropriate for representing certain evolutionary relationships, particularly in biology, than rooted trees. In this paper, we develop a framework for the analysis of these graphs which we call hybrid phylogenies. We are particularly interested in the problem whereby one is given a set of phylogenetic trees and wishes to determine a hybrid phylogeny that embeds each of these trees and which requires the smallest number of hybridisation events. We show that this quantity can be greatly reduced if additional species are involved, and investigate other combinatorial aspects of this and related questions.Received November 12, 2003     

An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure has only been concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled with the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms.Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.     

Branchings in rooted graphs and the diameter of greedoids

LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr ²–r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2^r–1.     

Bidendriform bialgebras, trees, and free quasi-symmetric functions

We introduce bidendriform bialgebras, which are bialgebras such that both product and coproduct can be split into two parts satisfying good compatibilities. For example, the Malvenuto-Reutenauer Hopf algebra and the non-commutative Connes-Kreimer Hopf algebras of planar decorated rooted trees are bidendriform bialgebras. We prove that all connected bidendriform bialgebras are generated by their primitive elements as a dendriform algebra (bidendriform Milnor-Moore theorem) and then is isomorphic to a Connes-Kreimer Hopf algebra. As a corollary, the Hopf algebra of Malvenuto-Reutenauer is isomorphic to the Connes-Kreimer Hopf algebra of planar rooted trees decorated by a certain set. We deduce that the Lie algebra of its primitive elements is free in characteristic zero (G. Duchamp, F. Hivert and J.-Y. Thibon conjecture).     

Indistinguishable Trees and Graphs

We show that a number of graph invariants are, even combined, insufficient to distinguish between non-isomorphic trees or general graphs. Among these are: the spectrum of eigenvalues (equivalently, the characteristic polynomial), the number of independent sets of all sizes or the number of connected subgraphs of all sizes. We therefore extend the classical theorem of Schwenk that almost every tree has a cospectral mate, and we provide an answer to a question of Jamison on average subtree orders of trees. The simple construction that we apply for this purpose is based on finding graphs with two distinguished vertices (called pseudosimilar) that do not belong to the same orbit but whose removal yields isomorphic graphs.     

2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.