18 citations · 79 across the 28 of their papers we have counts for
31 papers
Order-Dependent Dissimilarity Measures on Phylogenetic Trees
Simone Linz, Katherine St. John, Charles Semple +1
Ordered leaf attachment, Phylo2Vec, and HOP are three recently introduced vector representations for rooted phylogenetic trees where the representation is determined by an ordering…
Bounding the SNPR distance between two tree-child networks using generalised agreement forests
Steven Kelk, Simone Linz, Charles Semple
Agreement forests continue to play a central role in the comparison of phylogenetic trees since their introduction more than 25 years ago. More specifically, they are used to chara…
When is a set of phylogenetic trees displayed by a normal network?
Magnus Bordewich, Simone Linz, Charles Semple
A normal network is uniquely determined by the set of phylogenetic trees that it displays. Given a set of rooted binary phylogenetic trees, this paper presents a poly…
Phylogenetic trees defined by at most three characters
Katharina T. Huber, Simone Linz, Vincent Moulton +1
In evolutionary biology, phylogenetic trees are commonly inferred from a set of characters (partitions) of a collection of biological entities (e.g., species or individuals in a po…
Exploring spaces of semi-directed phylogenetic networks
Simone Linz, Kristina Wicke
Semi-directed phylogenetic networks have recently emerged as a class of phylogenetic networks sitting between rooted (directed) and unrooted (undirected) phylogenetic networks as t…
Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees
Katharina T. Huber, Simone Linz, Vincent Moulton
Phylogenetic networks are a special type of graph which generalize phylogenetic trees and that are used to model non-treelike evolutionary processes such as recombination and hybri…
Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks
Janosch Döcker, Simone Linz, Charles Semple
In the context of reconstructing phylogenetic networks from a collection of phylogenetic trees, several characterisations and subsequently algorithms have been established to recon…
Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics
Steven Kelk, Simone Linz, Ruben Meuwese
We describe a kernel of size 9k-8 for the NP-hard problem of computing the Tree Bisection and Reconnect (TBR) distance k between two unrooted binary phylogenetic trees. We achieve…
Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
Steven Kelk, Simone Linz, Ruben Meuwese
The rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a well-studied measure of topological dissimilarity that is NP-hard to compute.…
A QUBO formulation for the Tree Containment problem
Michael J. Dinneen, Pankaj S. Ghodla, Simone Linz
Phylogenetic (evolutionary) trees and networks are leaf-labeled graphs that are widely used to represent the evolutionary relationships between entities such as species, languages,…
Quasi-Isometric Graph Simplifications
Khí-Uí Soo, Bakhadyr Khoussainov, Simone Linz
Quasi-isometries are mappings on graphs, with distance-distortions parameterized by a multiplicative factor and an additive constant. The distance-distortions of quasi-isometries a…
Non-essential arcs in phylogenetic networks
Simone Linz, Charles Semple
In the study of rooted phylogenetic networks, analyzing the set of rooted phylogenetic trees that are embedded in such a network is a recurring task. From an algorithmic viewpoint,…
Reflections on kernelizing and computing unrooted agreement forests
Rim van Wersch, Steven Kelk, Simone Linz +1
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard proble…
On the maximum agreement subtree conjecture for balanced trees
Magnus Bordewich, Simone Linz, Megan Owen +3
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on leaves have a maximum agreement subtree (MAST) of size at…
Weakly displaying trees in temporal tree-child network
Katharina T. Huber, Simone Linz, Vincent Moulton
Recently there has been considerable interest in the problem of finding a phylogenetic network with a minimum number of reticulation vertices which displays a given set of phylogen…
Caterpillars on three and four leaves are sufficient to reconstruct normal networks
Simone Linz, Charles Semple
While every rooted binary phylogenetic tree is determined by its set of displayed rooted triples, such a result does not hold for an arbitrary rooted binary phylogenetic network. I…
Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Janosch Döcker, Britta Dorn, Simone Linz +1
The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterpart…
New reduction rules for the tree bisection and reconnection distance
Steven Kelk, Simone Linz
Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 ta…
Display sets of normal and tree-child networks
Janosch Doecker, Simone Linz, Charles Semple
Phylogenetic trees canonically arise as embeddings of phylogenetic networks. We recently showed that the problem of deciding if two phylogenetic networks embed the same sets of phy…
Displaying trees across two phylogenetic networks
Janosch Döcker, Simone Linz, Charles Semple
Phylogenetic networks are a generalization of phylogenetic trees to leaf-labeled directed acyclic graphs that represent ancestral relationships between species whose past includes…
A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
Steven Kelk, Simone Linz
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…
On the Subnet Prune and Regraft Distance
Jonathan Klawitter, Simone Linz
Phylogenetic networks are rooted directed acyclic graphs that represent evolutionary relationships between species whose past includes reticulation events such as hybridisation and…
On the existence of a cherry-picking sequence
Janosch Döcker, Simone Linz
Recently, the minimum number of reticulation events that is required to simultaneously embed a collection P of rooted binary phylogenetic trees into a so-called temporal network ha…
Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
Simone Linz, Charles Semple
Throughout the last decade, we have seen much progress towards characterising and computing the minimum hybridisation number for a set P of rooted phylogenetic trees. Roughly speak…