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

Computing the Rooted Triplet Distance for Phylogenetic Trees and Caterpillars

In phylogenetics, it is important to figure out what method to obtain a phylogenetic tree, a tree showing how species evolve from one another, is more reliable. A phylogenetic tree is a mathematical tree, where every internal vertex has at least 2 children, and the leaves are labeled bijectively with a set $X$. One useful tool to help determine...

Creating phylogenetic networks from clusters

In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous...

Treewidth based algorithms for Tree Containment in phylogenetics

TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree...

A new polynomial for describing Phylogenetic Networks

Describing phylogenetic trees or networks with a polynomial is a tool to distinguish between them. In this thesis, a new polynomial for describing rooted binary internally labeled phylogenetic networks and trees is introduced based on the research of P. Liu and J. Pons et al. Two different cases are considered, one where the reticulation nodes...

Embedding Phylogenetic Trees in Networks of Low Treewidth

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input...

New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5 ^k· n· m). We also present the concept...

Encoding level-k phylogenetic networks

Phylogenetic networks are used to describe evolutionary histories and are a generalisation of evolutionary trees. They can contain so called reticulations, representing reticulate evolution, such as hybridization, lateral gene transfer and recombination. Methods are being developed to construct certain rooted phylogenetic networks from their...

Different reduction rules for the Maximum Parsimony distance on phylogenetic trees

In this report, the bounded Maximum Parsimony distance will be considered when<br/>applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it...

A Third Strike Against Perfect Phylogeny

Perfect phylogenies are fundamental in the study of evolutionary trees because they capture the situation when each evolutionary trait emerges only once in history; if such events are believed to be rare, then by Occam's Razor such parsimonious trees are preferable as a hypothesis of evolution. A classical result states that 2-state...

Leaf-Reconstructibility of Phylogenetic Networks

An important problem in evolutionary biology is to reconstruct the evolutionary history of a set X of species. This history is often represented as a phylogenetic network, that is, a connected graph with leaves labelled by elements in X (for example, an evolutionary tree), which is usually also binary, i.e., all vertices have degree 1 or 3. A...

Nonbinary Tree-Based Phylogenetic Networks

Rooted phylogenetic networks are used to describe evolutionary histories that contain non-treelike evolutionary events such as hybridization and horizontal gene transfer. In some cases, such histories can be described by a phylogenetic base-tree with additional linking arcs, which can for example represent gene transfer events. Such phylogenetic...

Reconstructing phylogeny by aligning multiple metabolic pathways using functional module mapping

Comparison of metabolic pathways provides a systematic way for understanding the evolutionary and phylogenetic relationships in systems biology. Although a number of phylogenetic methods have been developed, few efforts have been made to provide a unified phylogenetic framework that sufficiently reflects the metabolic features of organisms....

Finding a most parsimonious or likely tree in a network with respect to an alignment

Phylogenetic networks are often constructed by merging multiple conflicting phylogenetic signals into a directed acyclic graph. It is interesting to explore whether a network constructed in this way induces biologically-relevant phylogenetic signals that were not present in the input. Here we show that, given a multiple alignment A for a set...

Detecting mixed Mycobacterium tuberculosis infections and differences in drug susceptibility with WGS data

Tuberculosis is a pulmonary disease caused by the pathogen Mycobacterium tuberculosis and is the second leading cause of death from an infectious disease. Individuals infected by multiple strains referred to as a mixed infection are associated with poor treatment outcomes when the infecting strains differ in their susceptibility against...

Hybridization Number on Three Rooted Binary Trees is EPT

Phylogenetic networks are leaf-labeled directed acyclic graphs that are used to describe nontreelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all in-degrees minus the number of nodes plus one. The hybridization number problem takes as input a...

On computing the maximum parsimony score of a phylogenetic network

Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we...

Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets

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