In phylogenetics and other areas of classification, the Buneman graph is commonly used to represent a collection of bipartitions or splits of a (finite) set X in order to display evolutionary relationships. The set X usually corresponds to a set of taxa (or species), and the splits are usually derived from molecular sequence data associated to the taxa. One issue with this approach is that missing molecular data can lead to bipartitions of subsets of X or partial splits, instead of splits of the full set X. In this paper, we show that the definition of the Buneman graph can be naturally extended to collections of partial splits of a set X. Just as with splits, we show that the graph so obtained is an X-labeled median graph but, in contrast to the usual Buneman graph, the elements in X are represented by convex subsets of the vertex set of the graph instead of single vertices. We also show that the Buneman graph for a collection of partial splits is closely related to subtree distances. In particular, for a collection S of weighted partial splits that satisfies a certain pairwise compatibility condition, we show that the corresponding edge-weighted Buneman graph is the unique minimal tree that represents the subtree distance d corresponding to S. Moreover, we show that in this special situation the Buneman graph can also be considered as a type of configuration space for the set of all tree-metrics that minimally extend the subtree distance d.

In evolutionary biology, networks are becoming increasingly used to represent evolutionary histories for species that have undergone non-treelike or reticulate evolution. Such networks are essentially directed acyclic graphs with a leaf set that corresponds to a collection of species, and in which non-leaf vertices with indegree 1 correspond to speciation events and vertices with indegree greater than 1 correspond to reticulate events such as gene transfer. Recently forest-based networks have been introduced, which are essentially (multi-rooted) networks that can be formed by adding some arcs to a collection of phylogenetic trees (or phylogenetic forest), where each arc is added in such a way that its ends always lie in two different trees in the forest. In this paper, we consider the complexity of deciding whether a given network is proper forest-based, that is, whether it can be formed by adding arcs to some underlying phylogenetic forest which contains the same number of trees as there are roots in the network. More specifically, we show that it is NP-complete to decide whether a tree-child network with m roots is proper forest-based, for each m ≥ 2 . Moreover, for binary networks the problem remains NP-complete when m ≥ 3 but becomes polynomial-time solvable for m = 2 . We also give a fixed parameter tractable (FPT) algorithm, with parameters the maximum outdegree of a vertex, the number of roots, and the number of indegree 2 vertices, for deciding if a semi-binary network is proper forest-based. A key element in proving our results is a new characterization for when a network with m roots is proper forest-based in terms of certain m -colorings. • Proper forest-based networks model evolutionary processes such as introgression. • We consider problem (P): Is a given m-rooted network N proper forest-based? • We show (P) can be solved in polynomial time if N is 2-rooted, binary tree-child. • We show (P) is NP-complete if N is m-rooted, binary tree-child with m ≥ 3. • We give an FPT algorithm for (P) in case every vertex in N has indegree at most 2.

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.

Abstract. A network [Formula: see text] on a finite set [Formula: see text], [Formula: see text], is a connected directed acyclic graph with leaf set [Formula: see text] in which every root in [Formula: see text] has outdegree at least 2 and no vertex in [Formula: see text] has indegree and outdegree equal to 1; [Formula: see text] is arboreal if the underlying unrooted, undirected graph of [Formula: see text] is a tree. Networks are of interest in evolutionary biology since they are used, for example, to represent the evolutionary history of a set [Formula: see text] of species whose ancestors have exchanged genes in the past. For [Formula: see text] some arbitrary set of symbols, [Formula: see text] is a symbolic arboreal map if there exists some arboreal network [Formula: see text] whose vertices with outdegree 2 or more are labeled by elements in [Formula: see text] and so that [Formula: see text], [Formula: see text], is equal to the label of the least common ancestor of [Formula: see text] and [Formula: see text] in [Formula: see text] if this exists, and [Formula: see text] otherwise. Important examples of symbolic arboreal maps include the symbolic ultrametrics, which arise in areas such as game theory, phylogenetics, and cograph theory. In this paper we show that a map [Formula: see text] is a symbolic arboreal map if and only if [Formula: see text] satisfies certain 3- and 4-point conditions and the graph with vertex set [Formula: see text] and edge set consisting of those pairs [Formula: see text] with [Formula: see text] is Ptolemaic (i.e., its shortest path distance satisfies Ptolemy’s inequality). To do this, we introduce and prove a key theorem concerning the shared ancestry graph for a network [Formula: see text] on [Formula: see text], where this is the graph with vertex set [Formula: see text] and edge set consisting of those [Formula: see text] such that [Formula: see text] and [Formula: see text] share a common ancestor in [Formula: see text]. In particular, we show that for any connected graph [Formula: see text] with vertex set [Formula: see text] and edge clique cover [Formula: see text] in which there are no two distinct sets in [Formula: see text] with one a subset of the other, there is some network with [Formula: see text] roots and leaf set [Formula: see text] whose shared ancestry graph is [Formula: see text].

Abstract The generalized circumradius of a set of points $$A\subseteq \mathbb {R}^d$$ A ⊆ R d with respect to a convex body K equals the minimum value of $$\lambda \ge 0$$ λ ≥ 0 such that a translate of $$\lambda K$$ λ K contains A. Each choice of K gives a different function on the set of bounded subsets of $$\mathbb {R}^d$$ R d ; we characterize which functions can arise in this way. Our characterization draws on the theory of diversities, a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalized circumradius to a finite subset of $$\mathbb {R}^d$$ R d . We obtain elegant characterizations in the case that K is a simplex or parallelotope.

Recently it was shown that a certain class of phylogenetic networks, called level-2 networks, cannot be reconstructed from their associated distance matrices. In this paper, we show that they can be reconstructed from their induced shortest and longest distance matrices. That is, if two level-2 networks induce the same shortest and longest distance matrices, then they must be isomorphic. We further show that level-2 networks are reconstructible from their shortest distance matrices if and only if they do not contain a subgraph from a family of graphs. A generator of a network is the graph obtained by deleting all pendant subtrees and suppressing degree-2 vertices. We also show that networks with a leaf on every generator side are reconstructible from their induced shortest distance matrix.

The problem of realizing finite metric spaces in terms of weighted graphs has many applications. For example, the mathematical and computational properties of metrics that can be realized by trees have been well-studied and such research has laid the foundation of the reconstruction of phylogenetic trees from evolutionary distances. However, as trees may be too restrictive to accurately represent real-world data or phenomena, it is important to understand the relationship between more general graphs and distances. In this paper, we introduce a new type of metric called a cactus metric, that is, a metric that can be realized by a cactus graph. We show that, just as with tree metrics, a cactus metric has a unique optimal realization. In addition, we describe an algorithm that can recognize whether or not a metric is a cactus metric and, if so, compute its optimal realization in O(n3) time, where n is the number of points in the space.

Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple relations on a set of sequences called orthology relations may be employed. In addition to being interesting from a practical point of view they are also attractive from a theoretical perspective in that e. g. a characterization is known for when such a relation is representable by a certain type of phylogenetic tree. For an orthology relation inferred from real biological data it is however generally too much to hope for that it satisfies that characterization. Rather than trying to correct the data in some way or another which has its own drawbacks, as an alternative, we propose to represent an orthology relation $$\delta $$ in terms of a structure more general than a phylogenetic tree called a phylogenetic network. To compute such a network in the form of a level-1 representation for $$\delta $$ , we formalize an orthology relation in terms of the novel concept of a symbolic 3-dissimilarity which is motivated by the biological concept of a “cluster of orthologous groups”, or COG for short. For such maps which assign symbols rather that real values to elements, we introduce the novel Network-Popping algorithm which has several attractive properties. In addition, we characterize an orthology relation $$\delta $$ on some set X that has a level-1 representation in terms of eight natural properties for $$\delta $$ as well as in terms of level-1 representations of orthology relations on certain subsets of X.

Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set $$\mathbb {T}$$ of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an $$O(3^{|X|} poly(|X|))$$ time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

UNLABELLED: Genome-wide association studies are an invaluable tool for identifying genotypic loci linked with agriculturally important traits or certain diseases. The signal on which such studies rely upon can, however, be obscured by population stratification making it necessary to account for it in some way. Population stratification is dependent on when admixture happened and thus can occur at various levels. To aid in its inference at the genome level, we recently introduced psiko, and comparison with leading methods indicates that it has attractive properties. However, until now, it could not be used for local ancestry inference which is preferable in cases of recent admixture as the genome level tends to be too coarse to properly account for processes acting on small segments of a genome. To also bring the powerful ideas underpinning psiko to bear in such studies, we extended it to psiko2, which we introduce here. AVAILABILITY AND IMPLEMENTATION: Source code, binaries and user manual are freely available at https://www.uea.ac.uk/computing/psiko. CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The ease with which genomic data can now be generated using Next Generation Sequencing technologies combined with a wealth of legacy data holds great promise for exciting new insights into the evolutionary relationships between and within the kingdoms of life. At the subspecies level (e.g., varieties or strains) dendograms, that is, certain edge-weighted rooted trees whose leaves are the elements of a set $X$ of organisms under consideration, are often used to represent those relationships. As is well known, dendrograms can be uniquely reconstructed from distances provided all distances on $X$ are known. More often than not, real biological datasets do not satisfy this assumption, implying that the sought dendrogram need not be uniquely determined by the available distances with regard to topology, edge-weighting, or both. To better understand the structural properties a set $\mathcal{L}\subseteq\binom{X}{2}$ has to satisfy to overcome this problem, various types of lassos have been introduced. Here, we focus on the question of when a lasso uniquely determines the topology of a dendrogram; that is, it is a topological lasso for its underlying tree. We show that any set-inclusion minimal topological lasso for such a tree $T$ can be transformed into a structurally nice minimal topological lasso for $T$. Calling such a lasso a distinguished minimal topological lasso for $T$, we characterize it in terms of the novel concept of a cluster marker map for $T$. In addition, we present novel results concerning the heritability of such lassos in the context of the subtree and supertree problems.

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 rationale 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 $\mathbb{P}(\Sigma)$ consisting of those multisets of partitions $\Pi$ of $X$ with $\Sigma_{\Pi}=\Sigma$. More specifically, we characterize when $\mathbb{P}(\Sigma)$ is nonempty and also identify some partitions in $\mathbb{P}(\Sigma)$ that are of maximum and minimum size. We also show that it is NP-complete to decide when $\mathbb{P}(\Sigma)$ is nonempty in the case when $\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.

In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential runtime in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.

UNLABELLED: Reflecting its continuously increasing versatility and functionality, the popularity of the ape (analysis of phylogenetics and evolution) software package has grown steadily over the years. Among its features, it has a strong distance-based component allowing the user to compute distances from aligned DNA sequences based on most methods from the literature and also build phylogenetic trees from them. However, even data generated with modern genomic approaches can fail to give rise to sufficiently reliable distance estimates. One way to overcome this problem is to exclude such estimates from data analysis giving rise to an incomplete distance data set (as opposed to a complete one). So far their analysis has been out of reach for ape. To remedy this, we have incorporated into ape several methods from the literature for phylogenetic inference from incomplete distance matrices. In addition, we have also extended ape's repertoire for phylogenetic inference from complete distances, added a new object class to efficiently encode sets of splits of taxa, and extended the functionality of some of its existing functions. AVAILABILITY: ape is distributed through the Comprehensive R Archive Network: http://cran.r-project.org/web/packages/ape/index.html Further information may be found at http://ape.mpl.ird.fr/pegas/

Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed.

Given a set $\Sigma$ of bipartitions of some finite set X of cardinality at least 2, one can associate to $\Sigma$ a canonical X-labeled graph $\mathcal{B}(\Sigma)$, called the Buneman graph. This graph has several interesting mathematical properties—for example, it is a median network and therefore an isometric subgraph of a hypercube. It is commonly used as a tool in studies of DNA sequences gathered from populations. In this paper, we present some results concerning the cut vertices of $\mathcal{B}(\Sigma)$, i.e., vertices whose removal disconnect the graph, as well as its blocks or 2-connected components—results that yield, in particular, an intriguing generalization of the well-known fact that $\mathcal{B}(\Sigma)$ is a tree if and only if any two splits in $\Sigma$ are compatible.

Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks--a type of network slightly more general than a phylogenetic tree--from triplets. Our algorithm has been made publicly available as the program LEV1ATHAN. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, LEV1ATHAN runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of LEV1ATHAN is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that LEV1ATHAN is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise.

Multilabeled trees or MUL-trees, for short, are trees whose leaves are labeled by elements of some nonempty finite set X such that more than one leaf may be labeled by the same element of X. This class of trees includes phylogenetic trees and tree shapes. MUL-trees arise naturally in, for example, biogeography and gene evolution studies and also in the area of phylogenetic network reconstruction. In this paper, we introduce novel metrics which may be used to compare MUL-trees, most of which generalize well-known metrics on phylogenetic trees and tree shapes. These metrics can be used, for example, to better understand the space of MUL-trees or to help visualize collections of MUL-trees. In addition, we describe some relationships between the MUL-tree metrics that we present and also give some novel diameter bounds for these metrics. We conclude by briefly discussing some open problems as well as pointing out how MUL-tree metrics may be used to define metrics on the space of phylogenetic networks.

UNLABELLED: Recent advances in gene sequencing for polyploid species, coupled with standard phylogenetic tree reconstruction, leads to gene trees in which the same species can label several leaves. Such multi-labeled trees are then used to reconstruct the evolutionary history of the polyploid species in question. However, this reconstruction process requires new techniques that are not available in current phylogenetic software packages. Here, we describe the software package PADRE (Package for Analyzing and Displaying Reticulate Evolution) that implements such techniques, allowing the reconstruction of complex evolutionary histories for polyploids in the form of phylogenetic networks. AVAILABILITY: PADRE is an open-source Java program freely available from http://www.uea.ac.uk/cmp/research/cmpbio/PADRE.

Many phylogenetic algorithms search the space of possible trees using topological rearrangements and some optimality criterion. FastME is such an approach that uses the balanced minimum evolution (BME) principle, which computer studies have demonstrated to have high accuracy. FastME includes two variants: balanced subtree prune and regraft (BSPR) and balanced nearest neighbor interchange (BNNI). These algorithms take as input a distance matrix and a putative phylogenetic tree. The tree is modified using SPR or NNI operations, respectively, to reduce the BME length relative to the distance matrix, until a tree with (locally) shortest BME length is found. Following computer simulations, it has been conjectured that BSPR and BNNI are consistent, i.e. for an input distance that is a tree-metric, they converge to the corresponding tree. We prove that the BSPR algorithm is consistent. Moreover, even if the input contains small errors relative to a tree-metric, we show that the BSPR algorithm still returns the corresponding tree. Whether BNNI is consistent remains open.

It was recently shown that just five characters (functions on a finite set X) suffice to convexly define a trivalent tree with leaf set X. Here we show that four characters suffice which, since three characters are not enough in general, is the best possible.