Source author record

Charles Semple

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Populations and Evolution Data Structures and Algorithms Quantitative Methods

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A splitter theorem for elastic elements in $3$ -connected matroids

An element $e$ of a $3$ -connected matroid $M$ is elastic if ${\rm si}(M/e)$ , the simplification of $M/e$ , and ${\rm co}(M\backslash e)$ , the cosimplification of $M\backslash e$ , are both $3$ -connected. It was recently shown that if $|E(M)|\geq 4$ , then $M$ has at least four elastic elements provided $M$ has no $4$ -element fans and no member of a specific family of $3$ -separators. In this paper, we extend this wheels-and-whirls type result to a splitter theorem, where the removal of elements is with respect to elasticity and keeping a specified $3$ -connected minor. We also prove that if $M$ has exactly four elastic elements, then it has path-width three. Lastly, we resolve a question of Whittle and Williams, and show that past analogous results, where the removal of elements is relative to a fixed basis, are consequences of this work.

preprint2022arXiv

Counting and optimising maximum phylogenetic diversity sets

In conservation biology, phylogenetic diversity (PD) provides a way to quantify the impact of the current rapid extinction of species on the evolutionary `Tree of Life'. This approach recognises that extinction not only removes species but also the branches of the tree on which unique features shared by the extinct species arose. In this paper, we investigate three questions that are relevant to PD. The first asks how many sets of species of given size $k$ preserve the maximum possible amount of PD in a given tree. The number of such maximum PD sets can be very large, even for moderate-sized phylogenies. We provide a combinatorial characterisation of maximum PD sets, focusing on the setting where the branch lengths are ultrametric (e.g. proportional to time). This leads to a polynomial-time algorithm for calculating the number of maximum PD sets of size $k$ by applying a generating function; we also investigate the types of tree shapes that harbour the most (or fewest) maximum PD sets of size $k$ . Our second question concerns optimising a linear function on the species (regarded as leaves of the phylogenetic tree) across all the maximum PD sets of a given size. Using the characterisation result from the first question, we show how this optimisation problem can be solved in polynomial time, even though the number of maximum PD sets can grow exponentially. Our third question considers a dual problem: If $k$ species were to become extinct, then what is the largest possible {\em loss} of PD in the resulting tree? For this question, we describe a polynomial-time solution based on dynamical programming.

preprint2022arXiv

Cyclic matroids

For all positive integers $s$ and $t$ exceeding one, a matroid $M$ on $n$ elements is {\em nearly $(s, t)$ -cyclic} if there is a cyclic ordering $σ$ of its ground set such that every $s-1$ consecutive elements of $σ$ are contained in an $s$ -element circuit and every $t-1$ consecutive elements of $σ$ are contained in a $t$ -element cocircuit. In the case $s=t$ , nearly $(s, s)$ -cyclic matroids have been studied previously. In this paper, we show that if $M$ is nearly $(s, t)$ -cyclic and $n$ is sufficiently large, then these $s$ -element circuits and $t$ -element cocircuits are consecutive in $σ$ in a prescribed way, that is, $M$ is " $(s, t)$ -cyclic". Furthermore, we show that, given $s$ and $t$ where $t\ge s$ , every $(s, t)$ -cyclic matroid on $n > s+t-2$ elements is a weak-map image of the $\left(\frac{t-s}{2}\right)$ -th truncation of a certain $(s, s)$ -cyclic matroid. If $s=3$ , this certain matroid is the rank- $\frac{n}{2}$ whirl, and if $s=4$ , this certain matroid is the rank- $\frac{n}{2}$ free swirl.

preprint2019arXiv

A class of phylogenetic networks reconstructable from ancestral profiles

Rooted phylogenetic networks provide an explicit representation of the evolutionary history of a set $X$ of sampled species. In contrast to phylogenetic trees which show only speciation events, networks can also accommodate reticulate processes (for example, hybrid evolution, endosymbiosis, and lateral gene transfer). A major goal in systematic biology is to infer evolutionary relationships, and while phylogenetic trees can be uniquely determined from various simple combinatorial data on $X$ , for networks the reconstruction question is much more subtle. Here we ask when can a network be uniquely reconstructed from its `ancestral profile' (the number of paths from each ancestral vertex to each element in $X$ ). We show that reconstruction holds (even within the class of all networks) for a class of networks we call `orchard networks', and we provide a polynomial-time algorithm for reconstructing any orchard network from its ancestral profile. Our approach relies on establishing a structural theorem for orchard networks, which also provides for a fast (polynomial-time) algorithm to test if any given network is of orchard type. Since the class of orchard networks includes tree-sibling tree-consistent networks and tree-child networks, our result generalise reconstruction results from 2008 and 2009. Orchard networks allow for an unbounded number $k$ of reticulation vertices, in contrast to tree-sibling tree-consistent networks and tree-child networks for which $k$ is at most $2|X|-4$ and $|X|-1$ , respectively.

preprint2018arXiv

Excluded minors are almost fragile

Let $M$ be an excluded minor for the class of $\mathbb{P}$ -representable matroids for some partial field $\mathbb P$ , and let $N$ be a $3$ -connected strong $\mathbb{P}$ -stabilizer that is non-binary. We prove that either $M$ is bounded relative to $N$ , or, up to replacing $M$ by a $Δ$ - $Y$ -equivalent excluded minor, we can choose a pair of elements $\{a,b\}$ such that either $M\backslash \{a,b\}$ is $N$ -fragile, or $M^* \backslash \{a,b\}$ is $N^*$ -fragile.

preprint2016arXiv

On the Quirks of Maximum Parsimony and Likelihood on Phylogenetic Networks

Maximum parsimony is one of the most frequently-discussed tree reconstruction methods in phylogenetic estimation. However, in recent years it has become more and more apparent that phylogenetic trees are often not sufficient to describe evolution accurately. For instance, processes like hybridization or lateral gene transfer that are commonplace in many groups of organisms and result in mosaic patterns of relationships cannot be represented by a single phylogenetic tree. This is why phylogenetic networks, which can display such events, are becoming of more and more interest in phylogenetic research. It is therefore necessary to extend concepts like maximum parsimony from phylogenetic trees to networks. Several suggestions for possible extensions can be found in recent literature, for instance the softwired and the hardwired parsimony concepts. In this paper, we analyze the so-called big parsimony problem under these two concepts, i.e. we investigate maximum parsimonious networks and analyze their properties. In particular, we show that finding a softwired maximum parsimony network is possible in polynomial time. We also show that the set of maximum parsimony networks for the hardwired definition always contains at least one phylogenetic tree. Lastly, we investigate some parallels of parsimony to different likelihood concepts on phylogenetic networks.

preprint2014arXiv

Representing Partitions on Trees

In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on a set $X$ of species from a multiset $Π$ of partitions corresponding to various attributes of these species. One approach that is used to solve this problem is to try instead to associate a tree (or even a network) to the multiset $Σ_Π$ consisting of all those bipartitions $\{A,X-A\}$ with $A$ a part of some partition in $Π$ . The rational behind this approach is that a phylogenetic tree with leaf set $X$ can be uniquely represented by the set of bipartitions of $X$ induced by its edges. Motivated by these considerations, given a multiset $Σ$ of bipartitions corresponding to a phylogenetic tree on $X$ , in this paper we introduce and study the set $P(Σ)$ consisting of those multisets of partitions $Π$ of $X$ with $Σ_Π=Σ$ . More specifically, we characterize when $P(Σ)$ is non-empty, and also identify some partitions in $P(Σ)$ that are of maximum and minimum size. We also show that it is NP-complete to decide when $P(Σ)$ is non-empty in case $Σ$ is an arbitrary multiset of bipartitions of $X$ . Ultimately, we hope that by gaining a better understanding of the mapping that takes an arbitrary partition system $Π$ to the multiset $Σ_Π$ , we will obtain new insights into the use of median networks and, more generally, split-networks to visualize sets of partitions.

preprint2010arXiv

Locating a tree in a phylogenetic network

Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level- $k$ networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Charles Semple

Research overview

Is this your work?

8 publications

A splitter theorem for elastic elements in $3$ -connected matroids

Counting and optimising maximum phylogenetic diversity sets

Cyclic matroids

A class of phylogenetic networks reconstructable from ancestral profiles

Excluded minors are almost fragile

On the Quirks of Maximum Parsimony and Likelihood on Phylogenetic Networks

Representing Partitions on Trees

Locating a tree in a phylogenetic network

See the researcher in context

Building this map preview

Charles Semple

Research overview

Is this your work?

8 publications

A splitter theorem for elastic elements in 333-connected matroids

Counting and optimising maximum phylogenetic diversity sets

Cyclic matroids

A class of phylogenetic networks reconstructable from ancestral profiles

Excluded minors are almost fragile

On the Quirks of Maximum Parsimony and Likelihood on Phylogenetic Networks

Representing Partitions on Trees

Locating a tree in a phylogenetic network

See the researcher in context

Building this map preview

A splitter theorem for elastic elements in $3$ -connected matroids