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.     

Geometry of the Space of Phylogenetic Trees

We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of trees. This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.     

Simplicial Properties of the Set of Planar Binary Trees

Planar binary trees appear as the the main ingredient of a new homology theory related to dialgebras, cf.(J.-L. Loday, C.R. Acad. Sci. Paris 321 (1995), 141–146.) Here I investigate the simplicial properties of the set of these trees, which are independent of the dialgebra context though they are reflected in the dialgebra homology.The set of planar binary trees is endowed with a natural (almost) simplicial structure which gives rise to a chain complex. The main new idea consists in decomposing the set of trees into classes, by exploiting the orientation of their leaves. (This trick has subsequently found an application in quantum electrodynamics, c.f. (C. Brouder, On the Trees of Quantum Fields, Eur. Phys. J. C12, 535–549 (2000).) This decomposition yields a chain bicomplex whose total chain complex is that of binary trees. The main theorem of the paper concerns a further decomposition of this bicomplex. Each vertical complex is the direct sum of subcomplexes which are in bijection with the planar binary trees. This decomposition is used in the computation of dialgebra homology as a derived functor, cf. (A. Frabetti, Dialgebra (co) Homology with Coefficients, Springer L.N.M., to appear).     

树上马氏链场的若干极限性质

该文引进广义Ｂｅｔｈｅ树和广义Ｃａｙｌｅｙ树的概念,并研究其上马氏链场关于状态和状态序偶出现频率的强极限定理,作为主要结果的推论,得到Ｂｅｔｈｅ树和Ｃａｙｌｅｙ树上马氏链场的ＳｈａｎｎｏｎＭｃＭｉｌｌａｎ定理．证明中采用了研究概率论强极限定理的一种新的方法．     

Groves of Phylogenetic Trees

A major challenge in biological sciences is the reconstruction of the Tree of Life. To this effect, large genomic databases like GenBank and SwissProt are being mined for clusters from which phylogenies can be inferred. Systematists and comparative biologists commonly combine such phylogenies into informative supertrees that reveal information which was not explicitly displayed in any of the original phylogenies. However, whether a supertree is informative depends on particular overlap properties among the clusters from which it originates. In this work we formally introduce the concept of groves — sets of clusters with the potential to construct informative supertrees. Thus maximal potential candidate clusters for informative supertree construction can be identified in large databases through groves, prior to inferring trees for each cluster. Groves also have the potential to lead to informative supermatrix construction. We developed methods that (i) efficiently identify particular types of groves and (ii) find lower and upper bounds on the minimal number of groves needed to cover all the trees or data sets in a database. Finally, we apply our methods to the green plant sequences from GenBank.     

Lattices on Nonuniform Trees

Let X be a locally finite tree, and let G=Aut(X). Then G is a locally compact group. We show that if X has more than one end, and if G contains a discrete subgroup such that the quotient graph of groups \\X is infinite but has finite covolume, then G contains a nonuniform lattice, that is, a discrete subgroup such that \G is not compact, yet has a finite G-invariant measure.     

Extension Operations on Sets of Leaf-Labeled Trees

A fundamental problem in classification is how to combine collections of trees having overlapping sets of leaves. The requirement that such a collection of trees is realized by at least one parent tree determines uniquely some additional subtrees not in the original collection. We analyze the "rules" that arise in this way by defining a closure operator for sets of trees. In particular we show that there exist rules of arbitrarily high order which cannot be reduced to repeated application of lower-order rules.     

Embeddings of Twin Trees

In this article we provide sufficient conditions for when a pair of trees having a semi-codistance function can be embedded in a twin tree with codistance function extending . We use these conditions to show that given a twin tree T of bidegree (d1,d2) there exists a twin tree of bidegree (e1,e2) containing T as a substructure as long as di ei.     

Rigidity of Branch Groups Acting on Rooted Trees

Automorphisms of groups acting faithfully on rooted trees are studied. We find conditions under which every automorphism of such a group is induced by a conjugation from the full automorphism group of the rooted tree. These results are applied to known examples such as Grigorchuk groups, Gupta–Sidki group, etc.     

The Large Scale Geometry of Products of Trees

We establish the quasi-isometric rigidity of the class of groups quasi-isometric to products of trees. In particular, we show that any group quasi-isometric to a product of trees is a lattice in the isometry group of a new product of trees (which are quasi-isometric to the original trees).     

Maximally Symmetric Trees

We characterize the best model geometries for the class of virtually free groups, and we show that there is a countable infinity of distinct best model geometries in an appropriate sense – these are the maximally symmetric trees. The first theorem gives several equivalent conditions on a bounded valence, cocompact tree T without valence 1 vertices saying that T is maximally symmetric. The second theorem gives general constructions for maximally symmetric trees, showing for instance that every virtually free group has a maximally symmetric tree for a model geometry.     

Monotone Shrinkage of Trees

Abstract

We investigate a new method for regression trees which obtains estimates and predictions subject to constraints on the coefficients representing the effects of splits in the tree. The procedure leads to both shrinking of the node estimates and pruning of branches in the tree and for some problems gives better predictions than cost-complexity pruning used in the classification and regression tree (CART) algorithm. The new method is based on the least absolute shrinkage and selection operator (LASSO) method developed by Tibshirani.     

Trees and valuation rings

A subring of a division algebra is called a valuation ring of if or holds for all nonzero in . The set of all valuation rings of is a partially ordered set with respect to inclusion, having as its maximal element. As a graph is a rooted tree (called the valuation tree of ), and in contrast to the commutative case, may have finitely many but more than one vertices. This paper is mainly concerned with the question of whether each finite, rooted tree can be realized as a valuation tree of a division algebra , and one main result here is a positive answer to this question where can be chosen as a quaternion division algebra over a commutative field.

     

Near-optimal Nonlinear Regression Trees

We propose Near-optimal Nonlinear Regression Trees with hyperplane splits (NNRTs) that use a polynomial prediction function in the leaf nodes, which we solve by stochastic gradient methods. On synthetic data, we show experimentally that the algorithm converges to the global optimal. We compare NNRTs, ORT-LH, Multivariate Adaptive Regression Splines (MARS), Random Forests (RF) and XGBoost on 40 real-world datasets and show that overall NNRTs have a performance edge over all other methods.     

Imbalance in Random Digital Trees

The imbalance factor of the nodes containing keys in a trie (a sort of digital trees) is investigated. Accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissonization and the Mellin transform, and the inverse of the two operations. It is also shown from an analysis of the moving poles of the Mellin transform of the poissonized moment generating function that the imbalance factor (under appropriate centering and scaling) follows a Gaussian limit law.      

The Height of Increasing Trees

Increasing trees have been introduced by Bergeron, Flajolet, and Salvy [1]. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies EH _n ~ γlogn (for some constant γ > 0) and Var H _n =  O(1) as n → ∞. The methods used are based on generating functions. This research was supported by the Austrian Science Foundation FWF, project S9604, that is part of the Austrian National Research Network "Analytic Combinatorics and Probabilistic Number Theory".     

Comparing the Likelihood Functions of Phylogenetic Trees

DNA sequence data provide a good source of information on the evolutionary history of organisms. Among the proposed methods, the maximum likelihood methods require an explicit probabilistic model of nucleotide substitution that makes the assumption clear. However, procedures for testing hypotheses on topologies have not been well developed. We propose a revised version of the maximum likelihood estimator of a tree and derive some of its properties. Then we present tests to compare given trees and to derive the most likely candidates for the true topology, applying to maximum likelihoods the notion of contrast, as defined in the framework of the analysis of variance, and the procedures used in multiple comparison. Finally, an example is presented.     

Composition of Plane Trees

The connections recently established between combinatorial bicolored plane trees and Shabat polynomials show that the world of plane trees is incredibly rich with different mathematical structures. In this article we use Shabat polynomials to introduce a new operation, that of a composition, for combinatorial bicolored plane trees. The composition may be considered as a generalized symmetry.     

The Approximation Numbers of Hardy-Type Operators on Trees

The Hardy operator T_a on a tree is defined by Properties of T_a as a map from L^p() into itselfare established for 1 p . The main result is that, with appropriateassumptions on u and v, the approximation numbers a_n(T_a) ofT_a satisfy for a specified constant _p and 1 p < . This extends results of Naimark, Newmanand Solomyak for p = 2. Hitherto, for p 2, (*) was unknowneven when is an interval. Also, upper and lower estimates forthe l^q and weak-l^q norms of a_n(T_a) are determined. 2000 MathematicalSubject Classification: 47G10, 47B10.     

Abstract Commensurators of Groups Acting on Rooted Trees

We show that the abstract commensurator of a nearly level transitive weakly branch group H coincides with the relative commensurator of H in the homeomorphism group of the boundary of the tree on which H acts. It is also shown that the commensurator of an infinite group which is commensurable with its own nth direct power contains a Higman–Thompson group as a subgroup. Applying these results to the Grigorchuk 2-group G we show that the commensurator of G is a finitely presented infinite simple group.