A normal network is uniquely determined by the set of phylogenetic trees that it displays. Given a set $\mathcal{P}$ of rooted binary phylogenetic trees, this paper presents a polynomial-time algorithm that reconstructs the unique binary normal network whose set of displayed binary trees is $\mathcal{P}$, if such a network exists. Additionally, we show that any two rooted phylogenetic trees can be displayed by a normal network and show that this result does not extend to more than two trees. This is in contrast to tree-child networks where it has been previously shown that any collection of rooted phylogenetic trees can be displayed by a tree-child network. Lastly, we introduce a type of cherry-picking sequence that characterises when a collection $\mathcal{P}$ of rooted phylogenetic trees can be displayed by a normal network and, further, characterise the minimum number of reticulations needed over all normal networks that display $\mathcal{P}$. We then exploit these sequences to show that, for all $n\ge 3$, there exist two rooted binary phylogenetic trees on $n$ leaves that can be displayed by a tree-child network with a single reticulation, but cannot be displayed by a normal network with less than $n-2$ reticulations.

Abstract. A partitioned matroid [Formula: see text] consists of a matroid [Formula: see text] and a partition [Formula: see text] of its ground set. As such structures arise frequently in structural matroid theory, this paper introduces a general technique for analyzing those special properties of partitioned matroids that depend solely on the values of the connectivities [Formula: see text], the local connectivities [Formula: see text], and the dual local connectivities [Formula: see text]. In particular, we consider those partitioned matroids in which each [Formula: see text] is an independent, coindependent set of clones of cardinality [Formula: see text]. Calling such partitioned matroids clonal-core matroids, we show that special results of the above type for partitioned matroids can be verified in general by proving them just for clonal-core matroids. Aiming at the long-term goal of finding the unavoidable minors of 4-connected matroids, we illustrate this technique by studying 4-paths. These are sequences [Formula: see text] of sets that partition the ground set of a matroid so that the union of any proper initial segment of parts is 4-separating. Viewing the ends [Formula: see text] and [Formula: see text] as fixed, we call such a partition a 4-flexipath if [Formula: see text] is a 4-path for all permutations [Formula: see text] of [Formula: see text]. A straightforward simplification enables us to focus on [Formula: see text]-flexipaths for some [Formula: see text] in [Formula: see text], that is, those 4-flexipaths for which [Formula: see text] and [Formula: see text] for all distinct [Formula: see text] and [Formula: see text]. Our main result for 4-paths is that the only nontrivial case that arises here is when [Formula: see text]. In that case, there are essentially only two possible dual pairs of [Formula: see text]-flexipaths when [Formula: see text].

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. For integers [Formula: see text] and [Formula: see text] exceeding one, a matroid [Formula: see text] on [Formula: see text] elements is nearly [Formula: see text]- cyclic if there is a cyclic ordering [Formula: see text] of its ground set such that every [Formula: see text] consecutive elements of [Formula: see text] are contained in an [Formula: see text]-element circuit and every [Formula: see text] consecutive elements of [Formula: see text] are contained in a [Formula: see text]-element cocircuit. In the case [Formula: see text], nearly [Formula: see text]-cyclic matroids have been studied previously. In this paper, we show that if [Formula: see text] is nearly [Formula: see text]-cyclic and [Formula: see text] is sufficiently large, then these [Formula: see text]-element circuits and [Formula: see text]-element cocircuits are consecutive in [Formula: see text] in a prescribed way, that is, [Formula: see text] is “[Formula: see text]-cyclic.” Furthermore, we show that, given [Formula: see text] and [Formula: see text] where [Formula: see text], every [Formula: see text]-cyclic matroid on [Formula: see text] elements is a weak-map image of the [Formula: see text]th truncation of a certain [Formula: see text]-cyclic matroid. If [Formula: see text], this certain matroid is the rank-[Formula: see text] whirl, and if [Formula: see text], this certain matroid is the rank-[Formula: see text] free swirl.

We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labeled trees on $n$ leaves have a maximum agreement subtree (MAST) of size at least $n^{\frac{1}{2}}$. In particular, we show that for any $c>0$, there exist two balanced rooted binary leaf-labeled trees on $n$ leaves such that any MAST for these two trees has size less than $c n^{\frac{1}{2}}$. We also improve the lower bound of the size of such a MAST to $n^{\frac{1}{6}}$.

Phylogenetic Diversity (PD) is a prominent quantitative measure of the biodiversity of a collection of present-day species (taxa). This measure is based on the evolutionary distance among the species in the collection. Loosely speaking, if T is a rooted phylogenetic tree whose leaf set X represents a set of species and whose edges have real-valued lengths (weights), then the PD score of a subset S of X is the sum of the weights of the edges of the minimal subtree of T connecting the species in S. In this paper, we define several natural variants of the PD score for a subset of taxa which are related by a known rooted phylogenetic network. Under these variants, we explore, for a positive integer k, the computational complexity of determining the maximum PD score over all subsets of taxa of size k when the input is restricted to different classes of rooted phylogenetic networks.

A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$ is connected or, equivalently, if $M^*$ has no two skew circuits. Pfeil showed that a simple graphic matroid $M(G)$ is unbreakable exactly when $G$ is either a cycle or a complete graph. We extend this result to describe which graphs are the underlying graphs of unbreakable frame matroids.

Tutte's wheels-and-whirls theorem is a basic inductive tool for dealing with $3$-connected matroids. This paper proves a generalization of that theorem for the class of $2$-polymatroids. Such structures include matroids, and they model both sets of points and lines in a projective space and sets of edges in a graph. The main result proves that, in a $3$-connected $2$-polymatroid that is not a whirl or the cycle matroid of a wheel, one can obtain another $3$-connected $2$-polymatroid by deleting or contracting some element, or by performing a new operation that generalizes series contraction in a graph. Moreover, we show that unless one uses some reduction operation in addition to deletion and contraction, the set of minimal $2$-polymatroids that are not representable over a fixed field ${\mathbb F}$ is infinite, irrespective of whether ${\mathbb F}$ is finite or infinite.

Semple and Steel (2002) showed that if ${\cal T}$ is a phylogenetic $X$-tree and ${\cal C}$ is a collection of $r$-state characters that defines ${\cal T}$, then $|{\cal C}|\ge \lceil(n-3)/(r-1)\rceil$, where $n=|X|$. In this paper, we show that, provided $n$ is sufficiently large, this lower bound is sharp. Furthermore, we show that, for all n\ge 13, there exists a collection of 4-state characters of size $\lceil(n-3)/3\rceil$ that defines ${\cal T}$, but there is a phylogenetic $X$-tree with n=12 which is not defined by any set of 3 characters.

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.

Answering a problem posed by Nakhleh, we prove that counting the number of phylogenetic trees inferred by a (binary) phylogenetic network is \#P-complete. An immediate consequence of this result is that counting the number of phylogenetic trees commonly inferred by two (binary) phylogenetic networks is also \#P-complete.

Reticulate evolution--the umbrella term for processes like hybridization, horizontal gene transfer, and recombination--plays an important role in the history of life of many species. Although the occurrence of such events is widely accepted, approaches to calculate the extent to which reticulation has influenced evolution are relatively rare. In this paper, we show that the NP-hard problem of calculating the minimum number of reticulation events for two (arbitrary) rooted phylogenetic trees parameterized by this minimum number is fixed-parameter tractable.

The Nature Reserve Selection Problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to conserve so that the phylogenetic diversity of the set of species contained within those regions is maximized. Recently, it was shown in a paper by Moulton et al. that this problem is NP-hard. In this paper, we establish a tight polynomial-time approximation algorithm for the Nature Reserve Section Problem. Furthermore, we resolve a question on the computational complexity of a related problem left open in Moulton et al.

Reticulation processes in evolution mean that the ancestral history of certain groups of present-day species is non-tree-like. These processes include hybridization, lateral gene transfer, and recombination. Despite the existence of reticulation, such events are relatively rare and so a fundamental problem for biologists is the following: Given a collection of rooted binary phylogenetic trees on sets of species that correctly represent the tree-like evolution of different parts of their genomes, what is the smallest number of "reticulation" vertices in any network that explains the evolution of the species under consideration? It has been previously shown that this problem is NP-hard even when the collection consists of only two rooted binary phylogenetic trees. However, in this paper, we show that the problem is fixed-parameter tractable in the two-tree instance, when parameterized by this smallest number of reticulation vertices.

Graphs obtained from a binary leaf labeled ("phylogenetic") tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call "unicyclic networks") also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem and a simple, fast algorithm to determine 1-cycle compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multicyclic networks.

Amalgamating smaller evolutionary trees into a single parent tree is an important task in evolutionary biology. Traditionally, the (supertree) methods used for this amalgamation take a collection of leaf-labeled trees as their input. However, it has been recently highlighted that, in practice, such an input is somewhat limiting and that one would like supertree methods for collections of trees in which some of the interior vertices, as well as all of the leaves, are labeled [R. D. M. Page, in Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, O. Bininda-Emonds, ed., Kluwer, Dordrecht, The Netherlands, 2004, pp. 247--265]. In this paper, we describe what appears to be the first approach for constructing such methods and show that any method using this approach satisfies particular desirable properties.

MOTIVATION: Supertree methods have been often identified as a possible approach to the reconstruction of the 'Tree of Life'. However, a limitation of such methods is that, typically, they use just leaf-labelled phylogenetic trees to infer the resulting supertree. RESULTS: In this paper, we describe several new supertree algorithms that extend the allowable information that can be used for phylogenetic inference. These algorithms have been recently implemented and we describe here two illustrative applications. AVAILABILITY: These new algorithms are freely available for application at http://darwin.zoology.gla.ac.uk/cgi-bin/build.pl.