Two novel closure rules for constructing phylogenetic super-networks

Uprooted Phylogenetic Networks

The need for structures capable of accommodating complex evolutionary signals such as those found in, for example, wheat has fueled research into phylogenetic networks. Such structures generalize the standard model of a phylogenetic tree by also allowing for cycles and have been introduced in rooted and unrooted form. In contrast to phylogenetic trees or their unrooted versions, rooted phylogenetic networks are notoriously difficult to understand. To help alleviate this, recent work on them has also centered on their "uprooted" versions. By focusing on such graphs and the combinatorial concept of a split system which underpins an unrooted phylogenetic network, we show that not only can a so-called (uprooted) 1-nested network N be obtained from the Buneman graph (sometimes also called a median network) associated with the split system [Formula: see text] induced on the set of leaves of N but also that that graph is, in a well-defined sense, optimal. Along the way, we establish the 1-nested analogue of the fundamental "splits equivalence theorem" for phylogenetic trees and characterize maximal circular split systems.

Reconstructing a phylogenetic level-1 network from quartets

We describe a method that will reconstruct an unrooted binary phylogenetic level-1 network on [Formula: see text] taxa from the set of all quartets containing a certain fixed taxon, in [Formula: see text] time. We also present a more general method which can handle more diverse quartet data, but which takes [Formula: see text] time. Both methods proceed by solving a certain system of linear equations over the two-element field [Formula: see text]. For a general dense quartet set, i.e. a set containing at least one quartet on every four taxa, our [Formula: see text] algorithm constructs a phylogenetic level-1 network consistent with the quartet set if such a network exists and returns an [Formula: see text]-sized certificate of inconsistency otherwise. This answers a question raised by Gambette, Berry and Paul regarding the complexity of reconstructing a level-1 network from a dense quartet set, and more particularly regarding the complexity of constructing a cyclic ordering of taxa consistent with a dense quartet set.