Charles Semple

AN UPGRADED WHEELS-AND-WHIRLS THEOREM FOR 3-CONNECTED MATROIDS (2009)

Abstract. Let M be a 3-connected matroid other than a wheel or a whirl. In the next paper in this series, we prove that there is an element whose deletion from M or M ∗ is 3-connected and whose...

Quantifying the Extent of Lateral Gene Transfer Required to Avert a `Genome of Eden' (2009)

Abstract. Let M be a 3-connected matroid that is not a wheel or a whirl. In this paper, we prove that M has an element e such that M\e or M/e is 3-connected and has no 3-separation that is not...

Van Iersel, Leo, Semple, Charles, Steel, Mike

The complex pattern of presence and absence of many genes across different species provides tantalising clues as to how genes evolved through the processes of gene genesis, gene loss and lateral gene...

triangles in 3-connected matroids (2009)

FORK-DECOMPOSITIONS OF MATROIDS (2009)

Abstract. Let {a, b, c} be a triangle in a 3-connected matroid M. In this paper, we describe the structure of M relative to {a, b, c} when, for all t in {a, b, c}, either M\t is not 3-connected, or...

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. One of the central problems in matroid theory is Rota’s conjecture that, for all prime powers q, the class of GF (q)–representable matroids has a finite set of excluded minors. This...

Running head: A Reduction Algorithm for Hybridization (2009)

Magnus Bordewich, Simone Linz, Katherine St. John, Charles Semple

duesseldorf.de

Unicyclic networks: compatibility and enumeration (2008)

NEGATIVE CORRELATION IN GRAPHS AND MATROIDS (2008)

Abstract—Graphs obtained from a binary leaf labeled (“phylogenetic”) tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular...

Charles Semple, Dominic Welsh

Abstract. The following two conjectures arose in the work of Grimmett and Winkler, and Pemantle: the uniformly random forest F and the uniformly random connected subgraph C of a finite graph G have...

OPTIMIZING PHYLOGENETIC DIVERSITY UNDER CONSTRAINTS (2008)

Vincent Moulton, Charles Semple, Mike Steel

Abstract. Phylogenetic diversity (PD) is a measure of the extent to which different subsets of taxa span an evolutionary tree, and provides a quantitative tool for studying biodiversity conservation....

REPLACING CLIQUES BY STARS IN QUASI-MEDIAN GRAPHS (2008)

Katharina T. Huber, Vincent Moulton, Charles Semple

Abstract. For a multi-set Σ of splits (bipartitions) of a finite set X, we introduce the multi-split graph G(Σ). This graph is a natural extension of the Buneman graph. Indeed, it is shown that...

Unicyclic networks: compatibility and enumeration (2008)

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. For all positive integers k, theclassBk of matroids of branch-width at most k is minor-closed. When k is 1 or 2, the class Bk is, respectively, the class of direct sums of loops and...

2005. A class of general supertree methods for nested taxa (2008)

Abstract. Graphs obtained from a binary leaf labelled (‘phyloge-netic’) tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular...

Philip Daniel, Charles Semple

Abstract. Amalgamating smaller evolutionary trees into a single parent tree is an important task in evolutionary biology. Traditionally, the (supertree) methods used for this amalgamation take a...

Reconstructing minimal rooted trees (2008)

Charles Semple

Abstract. For a set T of rooted binary leaf-labelled trees, we present an algorithm that finds all of the minor-minimal trees that are compatible with T. The running time of this algorithm is...

Identifying X-Trees with Few Characters (2008)

Magnus Bordewich, Charles Semple, Mike Steel

Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree T, there is a set of four characters that define T. Here we deal with the general case, where T is an...

COMPUTING THE MINIMUM NUMBER OF HYBRIDIZATION EVENTS FOR A CONSISTENT EVOLUTIONARY HISTORY (2008)

Magnus Bordewich, Charles Semple

Abstract. It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events...

A CHAIN THEOREM FOR MATROIDS (2008)

Identifying X-Trees with Few Characters (2008)

Abstract. Tutte’s Wheels-and-Whirls Theorem proves that if M is a 3-connected matroid other than a wheel or a whirl, then M has a 3-connected minor N such that |E(M) | − |E(N) | = 1. Geelen and...

Magnus Bordewich, Charles Semple, Mike Steel

Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree T, there is a set of four characters that define T. Here we deal with the general case, where T is an...

FORK-DECOMPOSITIONS OF MATROIDS (2008)

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. One of the central problems in matroid theory is Rota’s conjecture that, for all prime powers q, the class of GF(q)–representable matroids has a finite set of excluded minors. This...

The structure of the 3-separations of 3-connected matroids (2008)

MAINTAINING 3-CONNECTIVITY RELATIVE TO A FIXED BASIS (2008)

Tutte defined a k–separation of a matroid M to be a partition (A, B) of the ground set of M such that |A|, |B | ≥ k and r(A) + r(B) − r(M) < k. If, for all m < n, the matroid M has no...

Abstract. A standard matrix representation A of a matroid M represents M relative to a fixed basis B. Deleting rows and columns of A correspond to contracting elements of B and deleting elements of...

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. For all positive integers k, the class Bk of matroids of branch-width at most k is minor-closed. When k is 1 or 2, the class Bk is, respectively, the class of direct sums of loops and...

The structure of equivalent 3-separations in a 3-connected matroid (2008)

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. For all positive integers k, the class Bk of matroids of branch-width at most k is minor-closed. When k ∈ {1, 2}, the class Bk is, respectively, the class of direct sums of loops and...

Rhiannon Hall, James Oxley, Charles Semple

Abstract. Let M be a matroid. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. This result was extended by Oxley, Semple, and...

The structure of the 3-separations of 3connected matroids (2008)

FORK-DECOMPOSITIONS OF MATROIDS (2008)

Abstract. The authors showed in an earlier paper that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid. The purpose of this paper is...

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. One of the central problems in matroid theory is Rota’s conjecture that, for all prime powers q, theclassofGF (q)–representable matroids has a finite set of excluded minors. This...

The structure of the 3-separations of 3connected matroids (2008)

The structure of the 3-separations of 3connected matroids (2008)

Abstract. Tutte defined a k–separation of a matroid M to be a partition (A, B) of the ground set of M such that |A|, |B | ≥ k and r(A) + r(B) − r(M) < k. If M has no (n − 1)–separations,...

Abstract. Tutte defined a k–separation of a matroid M to be a partition (A, B) of the ground set of M such that |A|, |B | ≥ k and r(A) + r(B) − r(M) < k. If M has no (n − 1)–separations,...

Whitianga, New Zealand Whitianga ‘08 NEW ZEALAND PHYLOGENETICS CONFERENCE Participants (2008)

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

Abstract. For all positive integers k, the class Bk of matroids of branch-width at most k is minor-closed. When k is 1 or 2, the class Bk is, respectively, the class of direct sums of loops and...

John Beck, David Bryant, Michael Charleston, Alan Cooper, Beata Faller, Mareike Fischer, ...

revisited

Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution (2008)

Bordewich, Magnus, Rodrigo, Allen G., Semple, Charles

Three desirable properties for any method of selecting a subset of evolutionary units (EUs) for conservation or for genomic sequencing are discussed. These properties are spread, stability, and...

1 2 CHARLES SEMPLE AND MIKE STEEL Running Head: Group-valued tree proximities (2007)

Charles Semple, Mike Steel, Correspondence Charles Semple

Key words and phrases. Trees, groups, four-point condition, symbolic ultrametric. This work was supported by the New Zealand Marsden Fund (UOC-MIS-003).

INFINITE ANTICHAINS OF MATROIDS WITH CHARACTERISTIC SET fpg (2007)

James Oxley, Charles Semple, Dirk Vertigan, Geoff Whittle

Abstract. For each prime p, we construct an infinite antichain of matroids in which each matroid has characteristic set fpg. For p = 2, each of the matroids in our antichain is an excluded minor for...

A Reduction Algorithm for Computing The Hybridization Number of Two Trees (2007)

Magnus Bordewich, Simone Linz, Katherine St. John, Charles Semple

Hybridization is an important evolutionary process for many groups of species. Thus, conflicting signals in a data set may not be the result of sampling or modeling errors, but due to the fact that...

•Noah’s Ark problem (2007)

Charles Semple, Klaas Hartmann, Arne Mooers, Vince Moulton, Fabio Pardi, Beata Faller

uPD ( W)

Wild triangles in 3-connected matroids (2007)

Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa (2006)

Let {a, b, c} be a triangle in a 3-connected matroid M. In this paper, we describe the structure of M relative to {a, b, c} when, for all t in {a, b, c}, either M\t is not 3-connected, or M\t has a...

Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa (2006)

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying...

Fast Computation of Supertrees for Compatible (2006)

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying...

Phylogenies With Nested, Vincent Berry, Charles Semple

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaflabelled.

Fast Computation of Supertrees for Compatible Phylogenies with (2006)

Nested Taxa Vincent, Vincent Berry, Charles Semple

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying...

Hybrids in Real Time (2006)

Baroni, Mihaela, Semple, Charles, Steel, Mike

We describe some new and recent results that allow for the analysis and representation of reticulate evolution by nontree networks. In particular, we (1) present a simple result to show that, despite...

Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa (2006)

Extending the limits of supertree methods (2006)

Typically, supertree methods combine a collection of source trees in which just the leaves are labeled by taxa. In such methods the resulting supertree is also leaf labeled. An underlying assumption...

Bordewich, Magnus, Evans, Gareth, Semple, Charles

Recently, two exact polynomial-time supertree methods have been developed in which the traditional input of rooted leaf-labelled trees has been extended in two separate ways. The rst method, called...

Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa (2006)

Fast Computation of Supertrees for Compatible Phylogenies with Nested Taxa (2006)

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying...

C.: Identifying phylogenetic trees (2005)

Typically, supertree methods combine a collection of source trees in which just the leaves are labelled by taxa. In such methods the resulting supertree is also leaf-labelled. An underlying...

Magnus Bordewich, Katharina T. Huber, Charles Semple

Abstract. A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X....

Extending the Limits of Supertree Methods c ○ Birkhäuser Verlag, Basel, 2006 Annals of Combinatorics (2004)

Magnus Bordewich Gareth Evans, Charles Semple

AMS Subject Classification: 05C05; 92D15 Abstract. Recently, two exact polynomial-time supertree methods have been developed in which the traditional input of rooted leaf-labelled trees has been...

Supertree algorithms for ancestral divergence dates and nested taxa. Bioinformatics (2004)

Charles Semple, Philip Daniel, Wim Hordijk, Mike Steel

Abstract. Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the `Tree of Life'. However, a limitation of such methods is that, typically,...

Cyclic Permutations and Evolutionary Trees (2004)

Extending the Limits of Supertree Methods c ○ Birkhäuser Verlag, Basel, 2006 Annals of Combinatorics (2004)

Given a tree T with leaf set X, there are certain ways of arranging the elements of X in a circular order so that T can be embedded in the plane and `preserve' this ordering. We investigate some...

Magnus Bordewich Gareth Evans, Charles Semple

Abstract. Recently, two exact polynomial-time supertree methods have been developed in which the traditional input of rooted leaf-labelled trees has been extended in two separate ways. The first...

Supertree algorithms for ancestral divergence dates and nested taxa. Bioinformatics (2004)

Charles Semple, Philip Daniel, Wim Hordijk, Mike Steel

Abstract. Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the ‘Tree of Life’. However, a limitation of such methods is that, typically,...

Supertree algorithms for ancestral divergence dates and nested taxa. Bioinformatics (2004)

Charles Semple, Philip Daniel, Wim Hordijk, Mike Steel

Abstract. Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the ‘Tree of Life’. However, a limitation of such methods is that, typically,...

Supertree methods for ancestral divergence dates and other applications (2004)

David Bryant, Charles Semple, Mike Steel

Abstract: There are many ways to combine rooted phylogenetic trees with overlapping leaf sets into a single “supertree”. The most widely used method is MRP (matrix representation with parsimony...

Supertree algorithms for ancestral divergence dates and nested taxa (2004)

Semple, Charles, Daniel, Philip, Hordijk, Wim, Page, Roderic D. M., Steel, Mike

Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the ‘Tree of Life’. However, a limitation of such methods is that, typically, they use...

Supertree algorithms for ancestral divergence dates and nested taxa (2004)

Semple, Charles, Daniel, Philip, Hordijk, Wim, Page, Roderic D.M., Steel, Mike

Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the ‘Tree of Life’. However, a limitation of such methods is that, typically, they use...

Supertree algorithms for ancestral divergence dates and nested taxa (2004)

Semple, Charles, Daniel, Philip, Hordijk, Wim, Page, Roderic D. M., Steel, Mike

Motivation: Supertree methods have been often identified as a possible approach to the reconstruction of the ‘Tree of Life’. However, a limitation of such methods is that, typically, they use...

Annals of Combinatorics A Framework for Representing Reticulate Evolution ∗ (2003)

Mihaela Baroni, Charles Semple, Mike Steel

Abstract. Acyclic directed graphs (ADGs) are increasingly being viewed as more appropriate for representing certain evolutionary relationships, particularly in biology, than rooted trees. In this...

Tree reconstruction from multi-state characters (2002)

A characterization for a set of partial partitions to define an X–tree, Discrete Mathematics (2002)

Abstract. In evolutionary biology, a character is a function χ from a set X of present-day species into a finite set of states. Suppose the species in X have evolved according to a bifurcating tree...

Fork-Decompositions of Matroids (2002)

Abstract. Trees whose vertices are partially labelled by elements of a finite set X provide a natural way to represent partitions of subsets of X. The condition under which a given collection of such...

Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle

One of the central problems in matroid theory is Rota's conjecture that, for all prime powers q, the class of GF(q)-representable matroids has a finite set of excluded minors. This conjecture...

Tree reconstruction via a closure operation on partial splits (2001)

Tree reconstruction via a closure operation on partial splits (2001)

Abstract. A fundamental problem in biological classification is the reconstruction of phylogenetic trees for a set X of species from a collection of either subtrees or qualitative characters. This...

A supertree method for rooted trees (2000)

Abstract. A fundamental problem in biological classification is the reconstruction of phylogenetic trees for a set X of species from a collection of either subtrees or qualitative characters. This...

A supertree method for rooted trees (2000)

Abstract. The amalgamation of leaf-labelled (phylogenetic) trees on overlapping leaf sets into one (super)tree is a central problem in several areas of classification, particularly evolutionary...