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.

Recently, there has been a growing interest in the relationships between unrooted and rooted phylogenetic networks. In this context, a natural question to ask is if an unrooted phylogenetic network U can be oriented as a rooted phylogenetic network such that the latter satisfies certain structural properties. In a recent preprint, Bulteau et al. claim that it is NP-hard to decide if U has a funneled (resp. funneled tree-child) orientation, for when the internal vertices of U have degree at most 5. Unfortunately, the proof of their funneled tree-child result appears to be incorrect. In this paper, we show that, despite their incorrect proof, it is NP-hard to decide if U has a funneled tree-child orientation even if each internal vertex has degree 5 and that NP-hardness remains for other popular classes of rooted phylogenetic networks such as funneled normal and funneled reticulation-visible. Additionally, our results hold regardless of whether U is rooted at an existing vertex or by subdividing an edge with the root.

We describe a kernel of size 9k−8 for the NP-hard problem of computing the Tree Bisection and Reconnection (TBR) distance k between two unrooted binary phylogenetic trees. To achieve this, we extend the existing portfolio of reduction rules with three novel new reduction rules. Two of the rules are based on the idea of topologically transforming the trees in a distance-preserving way in order to guarantee execution of earlier reduction rules. The third rule extends the local neighbourhood approach introduced in [20] to more global structures, allowing new situations to be identified when deletion of a leaf definitely reduces the TBR distance by one. The bound on the kernel size is tight up to an additive term. Our results also apply to the equivalent problem of computing a Maximum Agreement Forest (MAF) between two unrooted binary phylogenetic trees. We anticipate that our results will be more widely applicable for computing agreement-forest based dissimilarity measures.

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}}$.

This paper proposes an efficient method for the weighted region problem (WRP) on the surface of three-dimensional terrains. WRP is a classical path planning problem, asking for the minimum cost path between two given points crossing different regions in which each region is assigned a traversal cost per unit distance. Although WRP has been studied for decades, the exact solution for WRP, even in a two-dimensional environment, is unknown. Thus, the existing solutions for WRP are all approximations with decomposition-based and heuristic methods being the most widely-used in practice. However, when a very-close to optimal path is required, especially on real terrains with many regions, these approaches are not guaranteed or cannot return a satisfactory result in reasonable time. In this paper, we first present a new algorithm of finding a very-close optimal path, based on a user-defined parameter δ, between two points, crossing the surface of a sequence of regions in 3D, using Snell's law of physical refraction. We then show how to combine this algorithm with one existing decomposition-based method to compute a close optimal path over the whole terrain. In addition to a theoretical analysis, with an extensive set of test cases, the practicality and feasibility of our method are confirmed by that, our method always runs faster and returns closer to optimal paths in comparison with the existing ones.

In 2001 Allen and Steel showed that, if subtree and chain reduction rules have been applied to two unrooted phylogenetic trees, the reduced trees will have at most 28k taxa where $k$ is the tree bisection and reconnection distance between the two trees. Here we reanalyze Allen and Steel's kernelization algorithm and prove that the reduced instances will in fact have at most 15k-9 taxa. Moreover we show, by describing a family of instances which have exactly 15k-9 taxa after reduction, that this new bound is tight. These instances also have no common clusters, showing that a third commonly encountered reduction rule, the cluster reduction, cannot further reduce the size of the kernel in the worst case. To achieve these results we introduce and use “unrooted generators” which are analogues of rooted structures that have appeared earlier in the phylogenetic networks literature. Using similar arguments we show that, for the minimum hybridization problem on two rooted trees, 9k-2 is a tight bound (when subtree and chain reduction rules have been applied) and 9k-4 is a tight bound (when, additionally, the cluster reduction has been applied) on the number of taxa, where $k$ is the hybridization number of the two trees.

A minimum hybridization network is a rooted phylogenetic network that displays two given rooted phylogenetic trees using a minimum number of reticulations. Previous mathematical work on their calculation has usually assumed the input trees to be bifurcating, correctly rooted, or that they both contain the same taxa. These assumptions do not hold in biological studies and "realistic" trees have multifurcations, are difficult to root, and rarely contain the same taxa. We present a new algorithm for computing minimum hybridization networks for a given pair of "realistic" rooted phylogenetic trees. We also describe how the algorithm might be used to improve the rooting of the input trees. We introduce the concept of "autumn trees", a nice framework for the formulation of algorithms based on the mathematics of "maximum acyclic agreement forests". While the main computational problem is hard, the run-time depends mainly on how different the given input trees are. In biological studies, where the trees are reasonably similar, our parallel implementation performs well in practice. The algorithm is available in our open source program Dendroscope 3, providing a platform for biologists to explore rooted phylogenetic networks. We demonstrate the utility of the algorithm using several previously studied data sets.

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.

We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa $X$ has a constant factor polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an $\text{O}( \log r \log \log r)$ approximation for the hybridization number where $r$ is the correct value.

We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of BETWEENNESS, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that QUARTET COMPATIBILITY, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel’s QUARTET CHALLENGE, which asks whether a solution to QUARTET COMPATIBILITY is unique, is coNP-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.