Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and...

Polynomial-Time Algorithms for Phylogenetic Inference Problems

A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model of speciation and duplication where duplications are clustered in duplication episodes....

Treewidth of display graphs: Bounds, brambles and applications

Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or networks. The treewidth of such graphs is bounded as a function of many common dissimilarity measures between phylogenetic trees and this has been leveraged in fixed...

Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks

Network reconstruction lies at the heart of phylogenetic research. Two well-studied classes of phylogenetic networks include tree-child networks and level-k networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-k network, the maximum number of reticulations contained in a biconnected...

Combining Networks Using Cherry Picking Sequences

Phylogenetic networks are important for the study of evolution. The number of methods to find such networks is increasing, but most such methods can only reconstruct small networks. To find bigger networks, one can attempt to combine small networks. In this paper, we study the Network Hybridization problem, a problem of combining networks...

Polynomial-Time Algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation

A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model with speciation and duplication where duplications are clustered in duplication episodes....

Distinguishing level-1 phylogenetic networks on the basis of data generated by Markov processes

Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees. These networks are able to incorporate reticulate evolutionary events such as hybridization, introgression, and lateral gene transfer. Recently, network-based Markov models of DNA sequence evolution have been introduced along with model...

A unifying characterization of tree-based networks and orchard networks using cherry covers

Phylogenetic networks are used to represent evolutionary relationships between species in biology. Such networks are often categorized into classes by their topological features, which stem from both biological and computational motivations. We study two network classes in this paper: tree-based networks and orchard networks. Tree-based...

The Future of Information Systems in a Post-COVID World by TC8 (Information Systems)

This chapter consists of several sections which contain contributions from members of IFIP Technical Committee 8 (Information Systems). We highlight the accomplishments of Technical Committee 8 (TC8) and its working groups over its 50 years history, and then envisage possible strategies for the future of information systems (IS) in a post...

Level-2 networks from shortest and longest distances

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

Editorial: How to develop a quality research article and avoid a journal desk rejection

The desk rejection of submitted articles can be a hugely frustrating and demotivating process from the perspective of the researcher, but equally, a time-consuming and vital step in the process for the Editor, tasked with selecting appropriate articles that meet the required criteria for further review and scrutiny. The feedback from journal...

A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) ^kpoly (n,...

Orchard Networks are Trees with Additional Horizontal Arcs

Phylogenetic networks are used in biology to represent evolutionary histories. The class of orchard phylogenetic networks was recently introduced for their computational benefits, without any biological justification. Here, we show that orchard networks can be interpreted as trees with additional horizontal arcs. Therefore, they are closely...

Orienting undirected phylogenetic networks

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

A near-linear kernel for bounded-state parsimony distance

The maximum parsimony distance d_MP(T₁,T₂) and the bounded-state maximum parsimony distance d_MP^t(T₁,T₂) measure the difference between two phylogenetic trees T₁,T₂ in terms of the maximum difference between their parsimony scores for any...