Search

Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that are used to represent the evolution of species which have undergone reticulate evolution. In this paper we consider spaces of such networks defined by some novel local operations that we introduce for converting one phylogenetic network into another. These operations are modeled on the well-studied nearest-neighbor interchange (NNI) operations on phylogenetic trees, and lead to natural generalizations of the tree spaces that have been previously associated to such operations. We present several results on spaces of some relatively simple networks, called level-1 networks, including the size of the neighborhood of a fixed network, and bounds on the diameter of the metric defined by taking the smallest number of operations required to convert one network into another.We expect that our results will be useful in the development of methods for systematically searching for optimal phylogenetic networks using, for example, likelihood and Bayesian approaches.

In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on a set $X$ of species from a multiset $\Pi$ of partitions corresponding to various attributes of these species. One approach that is used to solve this problem is to try instead to associate a tree (or even a network) to the multiset $\Sigma_{\Pi}$ consisting of all those bipartitions $\{A,X-A\}$ with $A$ a part of some partition in $\Pi$. The rational behind this approach is that a phylogenetic tree with leaf set $X$ can be uniquely represented by the set of bipartitions of $X$ induced by its edges. Motivated by these considerations, given a multiset $\Sigma$ of bipartitions corresponding to a phylogenetic tree on $X$, in this paper we introduce and study the set $P(\Sigma)$ consisting of those multisets of partitions $\Pi$ of $X$ with $\Sigma_{\Pi}=\Sigma$. More specifically, we characterize when $P(\Sigma)$ is non-empty, and also identify some partitions in $P(\Sigma)$ that are of maximum and minimum size. We also show that it is NP-complete to decide when $P(\Sigma)$ is non-empty in case $\Sigma$ is an arbitrary multiset of bipartitions of $X$. Ultimately, we hope that by gaining a better understanding of the mapping that takes an arbitrary partition system $\Pi$ to the multiset $\Sigma_{\Pi}$, we will obtain new insights into the use of median networks and, more generally, split-networks to visualize sets of partitions., Comment: 28 pages, submitted to SIAM J. Discrete Mathematics

The Yule-Harding-Kingman (YHK) model and the proportional to distinguishable arrangements (PDA) model are two binary tree generating models that are widely used in evolutionary biology. Understanding the distributions of clade sizes under these two models provides valuable insights into macro-evolutionary processes, and is important in hypothesis testing and Bayesian analyses in phylogenetics. Here we show that these distributions are log-convex, which implies that very large clades or very small clades are more likely to occur under these two models. Moreover, we prove that there exists a critical value $\kappa(n)$ for each $n\geqslant 4$ such that for a given clade with size $k$, the probability that this clade is contained in a random tree with $n$ leaves generated under the YHK model is higher than that under the PDA model if $1, Comment: 21pages

Tree rearrangement operations typically induce a metric on the space of phylogenetic trees. One important property of these metrics is the size of the neighborhood, that is, the number of trees exactly one operation from a given tree. We present an exact expression for the size of the TBR (tree bisection and reconnection) neighborhood, thus answering a question first posed by Allen and Steel . In addition, we also obtain a characterization of the extremal trees whose TBR neighborhoods are maximized and minimized.

Tree reconciliation approach to inferring the duplication history for a gene family poses challenging problems when input gene and species trees are non-binary. We present the first linear-time algorithm that outputs a reconciliation of a non-binary gene tree and a binary species tree that minimizes the gene loss cost under the constraint of having the smallest gene duplication cost. As a part of a method for reconciling two non-binary trees, this algorithm has been implemented in a software package (http://phylotoo.appspot.com).

Introduction A gene tree for a gene family is often discordant with the containing species tree because of its complex evolutionary course during which gene duplication, gene loss and incomplete lineage sorting events might occur. Hence, it is of great challenge to infer the containing species tree from a set of gene trees. One common approach to this inference problem is through gene tree and species tree reconciliation. Results In this paper, we generalize the traditional least common ancestor (LCA) reconciliation to define a reconciliation between a gene tree and species tree under the tree homomorphism framework. We then study the structural properties of the space of all reconciliations between a gene tree and a species tree in terms of the gene duplication, gene loss or deep coalescence costs. As application, we show that the LCA reconciliation is the unique one that has the minimum deep coalescence cost, provide a novel characterization of the reconciliations with the optimal duplication cost, and present efficient algorithms for enumerating (nearly-)optimal reconciliations with respect to each cost. Conclusions This work provides a new graph-theoretic framework for studying gene tree and species tree reconciliations.

Background: Horizontal gene transfer and gene duplication are two significant forces behind genome evolution. As more and more well-supported examples of HGTs are being revealed, there is a growing awareness that HGT is more widespread than previously thought, occurring often not only within bacteria, but also between species remotely related such as bacteria and plants or plants and animals. Although a substantial number of genomic sequences are known, HGT inference remains challenging. Parsimony-based inferences of HGT events are typically NP-hard under the framework of gene tree and species tree comparison; it is even more timeconsuming if the maximum likelihood approach is used. The fact that gene tree and species tree incongruence can be further confounded by gene duplication and gene loss events motivates us to incorporate considerations for these events into our inference of HGT events. Similarly, it will be beneficial if known HGT events are considered in the inference of gene duplications and gene losses.

A hierarchical structure describing the inter-relationships of species has long been a fundamental concept in systematic biology, from Linnean classification through to the more recent quest for a ‘Tree of Life’. In this paper we use an approach based on discrete mathematics to address a basic question: could one delineate this hierarchical structure in nature purely by reference to the ‘genealogy’ of present-day individuals, which describes how they are related with one another by ancestry through a continuous line of descent? We describe several mathematically precise ways by which one can naturally define collections of subsets of present day individuals so that these subsets are nested (and so form a tree) based purely on the directed graph that describes the ancestry of these individuals. We also explore the relationship between these and related clustering constructions.

Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.

Defining a subset B of a connected topological space T to be a barrier (in T) if B is connected and its complement T-B is disconnected, we will investigate barriers B in the tight span View the MathML source Turn MathJax on of a metric D defined on a finite set X (endowed, as a subspace of RX, with the metric and the topology induced by the l8-norm) that are of the form B=Be(f)?{g?T(D):?f-g?8=e} Turn MathJax on for some f?T(D) and some e=0. In particular, we will present some conditions on f and e which ensure that such a subset of T(D) is a barrier in T(D). More specifically, we will show that Be(f) is a barrier in T(D) if there exists a bipartition (or split) of the e-support View the MathML source of f into two non-empty sets A and B such that f(a)+f(b)=ab+e holds for all elements a?A and b?B while, conversely, whenever Be(f) is a barrier in T(D), there exists a bipartition of View the MathML source into two non-empty sets A and B such that, at least, f(a)+f(b)=ab+2e holds for all elements a?A and b?B.

Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element π∈G such that d(π,e)=k, for some given value k. Here we show that this problem is NP-complete for many well-known metrics. An analogous problem in matrix groups, eigenvalue-free problem, and two related problems in permutation groups, the maximum and minimum weight problems, are also investigated in this paper.