Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the minimum value of the Colless index and the bifurcating trees that achieve it
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted bifurcating trees, introduced by Colless (1982). While many of its statistical properties under different probabilistic models for phylogenetic trees have already been established, little is known about its minimum value and the trees that achieve it. In this manuscript, we fill this gap in the literature. To begin with, we derive both recursive and closed expressions for the minimum Colless index of a tree with $n$ leaves. Surprisingly, these expressions show a connection between the minimum Colless index and the so-called Blancmange curve, a fractal curve. We then fully characterize the tree shapes that achieve this minimum value and we introduce both an algorithm to generate them and a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index.
rate research
Read More
Computational inference of dated evolutionary histories relies upon various hypotheses about RNA, DNA, and protein sequence mutation rates. Using mutation rates to infer these dated histories is referred to as molecular clock assumption. Coalescent theory is a popular class of evolutionary models that implements the molecular clock hypothesis to facilitate computational inference of dated phylogenies. Cancer and virus evolution are two areas where these methods are particularly important. Methodologically, phylogenetic inference methods require a tree space over which the inference is performed, and geometry of this space plays an important role in statistical and computational aspects of tree inference algorithms. It has recently been shown that molecular clock, and hence coalescent, trees possess a unique geometry, different from that of classical phylogenetic tree spaces which do not model mutation rates. Here we introduce and study a space of discrete coalescent trees, that is, we assume that time is discrete, which is inevitable in many computational formalisations. We establish several geometrical properties of the space and show how these properties impact various algorithms used in phylogenetic analyses. Our tree space is a discretisation of a known time tree space, called t-space, and hence our results can be used to approximate solutions to various open problems in t-space. Our tree space is also a generalisation of another known trees space, called the ranked nearest neighbour interchange space, hence our advances in this paper imply new and generalise existing results about ranked trees.
Measures of tree balance play an important role in various research areas, for example in phylogenetics. There they are for instance used to test whether an observed phylogenetic tree differs significantly from a tree generated by the Yule model of speciation. One of the most popular indices in this regard is the Colless index, which measures the degree of balance for rooted binary trees. While many statistical properties of the Colless index (e.g. asymptotic results for its mean and variance under different models of speciation) have already been discussed in different contexts, we focus on its extremal properties. While it is relatively straightforward to characterize trees with maximal Colless index, the analysis of the minimal value of the Colless index and the characterization of trees that achieve it, are much more involved. In this note, we therefore focus on the minimal value of the Colless index for any given number of leaves. We derive both a recursive formula for this minimal value, as well as an explicit expression, which shows a surprising connection between the Colless index and the so-called Blancmange curve, a fractal curve that is also known as the Takagi curve. Moreover, we characterize two classes of trees that have minimal Colless index, consisting of the set of so-called emph{maximally balanced trees} and a class of trees that we call emph{greedy from the bottom trees}. Furthermore, we derive an upper bound for the number of trees with minimal Colless index by relating these trees with trees with minimal Sackin index (another well-studied index of tree balance).
A recent paper (Manceau and Lambert, 2016) developed a novel approach for describing two well-defined notions of species based on a phylogenetic tree and a phenotypic partition. In this paper, we explore some further combinatorial properties of this approach and describe an extension that allows an arbitrary number of phenotypic partitions to be combined with a phylogenetic tree for these two species notions.
Weighted Szeged index is a recently introduced extension of the well-known Szeged index. In this paper, we present a new tool to analyze and characterize minimum weighted Szeged index trees. We exhibit the best trees with up to 81 vertices and use this information, together with our results, to propose various conjectures on the structure of minimum weighted Szeged index trees.
Phylogenetic tree inference using deep DNA sequencing is reshaping our understanding of rapidly evolving systems, such as the within-host battle between viruses and the immune system. Densely sampled phylogenetic trees can contain special features, including sampled ancestors in which we sequence a genotype along with its direct descendants, and polytomies in which multiple descendants arise simultaneously. These features are apparent after identifying zero-length branches in the tree. However, current maximum-likelihood based approaches are not capable of revealing such zero-length branches. In this paper, we find these zero-length branches by introducing adaptive-LASSO-type regularization estimators to phylogenetics, deriving their properties, and showing regularization to be a practically useful approach for phylogenetics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
