Who is Who in Phylogenetic Networks

Publications of Charles Semple     Order by:   Type | Year
Associated keywords
abstract-network agreement-forest approximation APX-hard bound characterization cherry-picking cluster-containment compressed-network counting display-set distance-between-networks diversity explicit-network FPT from-clusters from-distances from-network from-quarnets from-quartets from-rooted-trees from-sequences from-subnetworks from-triplets galled-tree hybridization inapproximability lateral-gene-transfer level-k-phylogenetic-network likelihood minimum-number normal-network NP-complete number-of-vertices orchard-network orientation parsimony phylogenetic-network phylogeny polynomial Program-HybridInterleave Program-HybridNumber recombination reconstruction regular-network reticulation-visible-network software split-network SPR-distance stack-free-network time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network unicyclic-network uniqueness valid-network weak-hierarchy
2020
1 Simone Linz and Charles Semple. Caterpillars on three and four leaves are sufficient to reconstruct binary normal networks. In JOMB, 2020. Keywords: explicit network, from rooted trees, from triplets, normal network, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: https://arxiv.org/abs/2002.00483, to appear.
2019
2 Joan Carles Pons, Charles Semple and Mike Steel. Tree-based networks: characterisations, metrics, and support trees. In JOMB, Vol. 78(4):899-918, 2019. Keywords: characterization, explicit network, from network, phylogenetic network, phylogeny, time consistent network, tree-based network. Note: https://arxiv.org/abs/1710.07836.         3 Simone Linz and Charles Semple. Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies. In AAM, Vol. 105:102-129, 2019. Keywords: agreement forest, cherry-picking, explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction, tree-child network. Note: https://doi.org/10.1016/j.aam.2019.01.004.         4 Janosch Döcker, Simone Linz and Charles Semple. Displaying trees across two phylogenetic networks. In TCS, Vol. 796:129-146, 2019. Keywords: display set, explicit network, normal network, phylogenetic network, phylogeny, time consistent network, tree-child network. Note: https://arxiv.org/abs/1901.06612.         5 Katharina Huber, Leo van Iersel, Remie Janssen, Mark Jones, Vincent Moulton, Yukihiro Murakami and Charles Semple. Rooting for phylogenetic networks. 2019. Keywords: explicit network, from network, level k phylogenetic network, orchard network, orientation, phylogenetic network, phylogeny, reconstruction, stack-free network, tree-based network, tree-child network, valid network. Note: https://arxiv.org/abs/1906.07430.
2018
6 Andrew R. Francis, Charles Semple and Mike Steel. New characterisations of tree-based networks and proximity measures. In Advances in Applied Mathematics, Vol. 93:93-107, 2018. Keywords: characterization, explicit network, phylogenetic network, phylogeny, time consistent network, tree-based network. Note: https://arxiv.org/abs/1611.04225.         7 Magnus Bordewich, Charles Semple and Nihan Tokac. Constructing tree-child networks from distance matrices. In Algorithmica, Vol. 80(8):2240-2259, 2018. Keywords: compressed network, explicit network, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, tree-child network, uniqueness. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSN17.pdf.         8 Katharina Huber, Vincent Moulton, Charles Semple and Taoyang Wu. Quarnet inference rules for level-1 networks. In BMB, Vol. 80:2137-2153, 2018. Keywords: explicit network, from quarnets, from subnetworks, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: https://arxiv.org/abs/1711.06720.         9 Magnus Bordewich and Charles Semple. A universal tree-based network with the minimum number of reticulations. In DAM, Vol. 250:357-362, 2018. Keywords: explicit network, phylogenetic network, phylogeny, tree-based network. Note: https://arxiv.org/abs/1707.08274.         10 Charles Semple and Jack Simpson. When is a phylogenetic network simply an amalgamation of two trees? In BMB, Vol. 80(9):2338-2348, 2018. Keywords: characterization, phylogenetic network, phylogeny, reticulation-visible network, stack-free network, tree-based network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/SS18.pdf.         11 Magnus Bordewich, Katharina Huber, Vincent Moulton and Charles Semple. Recovering normal networks from shortest inter-taxa distance information. In JOMB, Vol. 77(3):571-594, 2018. Keywords: explicit network, from distances, normal network, phylogenetic network, phylogeny, polynomial, reconstruction, uniqueness. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BHMS18.pdf.
2017
12 Charles Semple. Size of a phylogenetic network. In DAM, Vol. 217(2):362-367, 2017. Keywords: compressed network, number of vertices, phylogenetic network, phylogeny, stack-free network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/S16.pdf.         13 Christopher Bryant, Mareike Fischer, Simone Linz and Charles Semple. On the Quirks of Maximum Parsimony and Likelihood on Phylogenetic Networks. In JTB, Vol. 417:100-108, 2017. Keywords: explicit network, from sequences, likelihood, parsimony, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/1505.06898.         14 Magnus Bordewich, Simone Linz and Charles Semple. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. In JTB, Vol. 423:1-12, 2017. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, reticulation-visible network, SPR distance, tree-based network, tree-child network. Note: https://simonelinz.files.wordpress.com/2017/04/bls171.pdf.
2016
15 Magnus Bordewich and Charles Semple. Reticulation-visible networks. In Advances in Applied Mathematics, Vol. 78:114-141, 2016. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS16.pdf.         16 Charles Semple. Phylogenetic Networks with Every Embedded Phylogenetic Tree a Base Tree. In BMB, Vol. 78(1):132-137, 2016. Keywords: characterization, explicit network, phylogenetic network, phylogeny, tree-based network, tree-child network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/S15.pdf.         17 Magnus Bordewich and Charles Semple. Determining phylogenetic networks from inter-taxa distances. In JOMB, Vol. 73(2):283-303, 2016. Keywords: from distances, phylogenetic network, phylogeny, reconstruction, reticulation-visible network, time consistent network, tree-child network, uniqueness. Note: http://132.181.26.35/~c.semple/papers/BS15b.pdf.
2015
18 Colin McDiarmid, Charles Semple and Dominic Welsh. Counting phylogenetic networks. In Annals of Combinatorics, Vol. 19(1):205-224, 2015. Keywords: counting, explicit network, normal network, phylogenetic network, phylogeny, tree-child network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/MSW13.pdf.
2014
19 Paul Cordue, Simone Linz and Charles Semple. Phylogenetic Networks that Display a Tree Twice. In BMB, Vol. 76(10):2664-2679, 2014. Keywords: from rooted trees, normal network, phylogenetic network, phylogeny, reconstruction, tree-child network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/CLS14.pdf.         Toggle abstract "In the last decade, the use of phylogenetic networks to analyze the evolution of species whose past is likely to include reticulation events, such as horizontal gene transfer or hybridization, has gained popularity among evolutionary biologists. Nevertheless, the evolution of a particular gene can generally be described without reticulation events and therefore be represented by a phylogenetic tree. While this is not in contrast to each other, it places emphasis on the necessity of algorithms that analyze and summarize the tree-like information that is contained in a phylogenetic network. We contribute to the toolbox of such algorithms by investigating the question of whether or not a phylogenetic network embeds a tree twice and give a quadratic-time algorithm to solve this problem for a class of networks that is more general than tree-child networks. © 2014, Society for Mathematical Biology."
2013
20 Peter J. Humphries, Simone Linz and Charles Semple. On the complexity of computing the temporal hybridization number for two phylogenies. In DAM, Vol. 161:871-880, 2013. Keywords: agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/TAFapx.pdf.         Toggle abstract "Phylogenetic networks are now frequently used to explain the evolutionary history of a set of species for which a collection of gene trees, reconstructed from genetic material of different parts of the species' genomes, reveal inconsistencies. However, in the context of hybridization, the reconstructed networks are often not temporal. If a hybridization network is temporal, then it satisfies the time constraint of instantaneously occurring hybridization events; i.e. all species that are involved in such an event coexist in time. Furthermore, although a collection of phylogenetic trees can often be merged into a hybridization network that is temporal, many algorithms do not necessarily find such a network since their primary optimization objective is to minimize the number of hybridization events. In this paper, we present a characterization for when two rooted binary phylogenetic trees admit a temporal hybridization network. Furthermore, we show that the underlying optimization problem is APX-hard and, therefore, NP-hard. Thus, unless P=NP, it is unlikely that there are efficient algorithms for either computing an exact solution or approximating it within a ratio arbitrarily close to one. © 2012 Elsevier B.V. All rights reserved." 21 Simone Linz, Katherine St. John and Charles Semple. Counting trees in a phylogenetic network is #P-complete. In SICOMP, Vol. 42(4):1768-1776, 2013. Keywords: counting, from network, phylogenetic network, phylogeny. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/counting.pdf.         22 Peter J. Humphries, Simone Linz and Charles Semple. Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. In BMB, Vol. 75(10):1879-1890, 2013. Keywords: characterization, cherry-picking, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/CPSpaper.pdf.         Toggle abstract "Recently, we have shown that calculating the minimum-temporal-hybridization number for a set P of rooted binary phylogenetic trees is NP-hard and have characterized this minimum number when P consists of exactly two trees. In this paper, we give the first characterization of the problem for P being arbitrarily large. The characterization is in terms of cherries and the existence of a particular type of sequence. Furthermore, in an online appendix to the paper, we show that this new characterization can be used to show that computing the minimum-temporal hybridization number for two trees is fixed-parameter tractable. © 2013 Society for Mathematical Biology."
2012
23 Magnus Bordewich and Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):69-85, 2012. Keywords: abstract network, approximation, diversity, phylogenetic network, polynomial, split network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS11.pdf.         Toggle abstract "Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1-1/e)-approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1-1/e)-approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al. © 2011 Springer-Verlag."
2011
24 Josh Voorkamp né Collins, Simone Linz and Charles Semple. Quantifying hybridization in realistic time. In JCB, Vol. 18(10):1305-1318, 2011. Keywords: explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, software. Note: http://wwwcsif.cs.ucdavis.edu/~linzs/CLS10_interleave.pdf, software available at http://www.math.canterbury.ac.nz/~c.semple/software.shtml.         Toggle abstract "Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulation-for example, horizontal gene transfer, hybridization, or recombination-has influenced the evolution for a set of present-day species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NP-hard and also fixed-parameter tractable problem. In this article, we give a new fixed-parameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleaving-a technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixed-parameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm that has previously been implemented. © 2011, Mary Ann Liebert, Inc."
2010
25 Leo van Iersel, Charles Semple and Mike Steel. Quantifying the Extent of Lateral Gene Transfer Required to Avert a 'Genome of Eden'. In BMB, Vol. 72:1783–1798, 2010. Note: http://www.win.tue.nl/~liersel/LGT.pdf.         Toggle abstract "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 transfer (LGT). The extent of LGT, particularly in prokaryotes, and its implications for creating a 'network of life' rather than a 'tree of life' is controversial. In this paper, we formally model the problem of quantifying LGT, and provide exact mathematical bounds, and new computational results. In particular, we investigate the computational complexity of quantifying the extent of LGT under the simple models of gene genesis, loss, and transfer on which a recent heuristic analysis of biological data relied. Our approach takes advantage of a relationship between LGT optimization and graph-theoretical concepts such as tree width and network flow. © 2010 Society for Mathematical Biology." 26 Simone Linz, Charles Semple and Tanja Stadler. Analyzing and reconstructing reticulation networks under timing constraints. In JOMB, Vol. 61(5):715-737, 2010. Keywords: explicit network, from rooted trees, hybridization, lateral gene transfer, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://dx.doi.org/10.1007/s00285-009-0319-y..         Toggle abstract "Reticulation networks are now frequently used to model the history of life for various groups of species whose evolutionary past is likely to include reticulation events such as horizontal gene transfer or hybridization. However, the reconstructed networks are rarely guaranteed to be temporal. If a reticulation network is temporal, then it satisfies the two biologically motivated timing constraints of instantaneously occurring reticulation events and successively occurring speciation events. On the other hand, if a reticulation network is not temporal, it is always possible to make it temporal by adding a number of additional unsampled or extinct taxa. In the first half of the paper, we show that deciding whether a given number of additional taxa is sufficient to transform a non-temporal reticulation network into a temporal one is an NP-complete problem. As one is often given a set of gene trees instead of a network in the context of hybridization, this motivates the second half of the paper which provides an algorithm, called TemporalHybrid, for reconstructing a temporal hybridization network that simultaneously explains the ancestral history of two trees or indicates that no such network exists. We further derive two methods to decide whether or not a temporal hybridization network exists for two given trees and illustrate one of the methods on a grass data set. © 2009 The Author(s)." 27 Leo van Iersel, Charles Semple and Mike Steel. Locating a tree in a phylogenetic network. In IPL, Vol. 110(23), 2010. Keywords: cluster containment, explicit network, from network, level k phylogenetic network, normal network, NP complete, phylogenetic network, polynomial, regular network, time consistent network, tree containment, tree sibling network, tree-child network. Note: http://arxiv.org/abs/1006.3122.         Toggle abstract "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. © 2010 Elsevier B.V. All rights reserved."
2009
28 Simone Linz and Charles Semple. Hybridization in non-binary trees. In TCBB, Vol. 6(1):30-45, 2009. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/LS08.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw03/1220/linz/.         29 Stefan Grünewald, Katharina Huber, Vincent Moulton, Charles Semple and Andreas Spillner. Characterizing weak compatibility in terms of weighted quartets. In Advances in Applied Mathematics, Vol. 42(3):329-341, 2009. Keywords: abstract network, characterization, from quartets, split network, weak hierarchy. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/GHMSS08.pdf, slides at http://www.lirmm.fr/miep08/slides/12_02_huber.pdf.         30 Peter J. Humphries and Charles Semple. Note on the hybridization number and subtree distance in phylogenetics. In Applied Mathematics Letters, Vol. 22(4):611-615, 2009. Keywords: explicit network, minimum number, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/HS08.pdf.
2007
31 Magnus Bordewich and Charles Semple. Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. In TCBB, Vol. 4(3):458-466, 2007. Keywords: FPT, hybridization. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06b.pdf.         32 Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914-918, 2007. Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.         33 Magnus Bordewich, Simone Linz, Katherine St. John and Charles Semple. A reduction algorithm for computing the hybridization number of two trees. In EBIO, Vol. 3:86-98, 2007. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNumber. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BLSS07.pdf.         34 Charles Semple. Hybridization Networks. In Olivier Gascuel and Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 277-314, Oxford University Press, 2007. Keywords: hybridization, phylogenetic network, phylogeny, recombination. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/S06.pdf.
2006
35 Mihaela Baroni, Charles Semple and Mike Steel. Hybrids in Real Time. In Systematic Biology, Vol. 55(1):46-56, 2006. Keywords: agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network. Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf.         Toggle abstract "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 the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. Copyright © Society of Systematic Biologists." 36 Charles Semple and Mike Steel. Unicyclic networks: compatibility and enumeration. In TCBB, Vol. 3(1):84-91, 2006. Keywords: counting, explicit network, galled tree, unicyclic network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/SS06.pdf.
2005
37 Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005. Keywords: agreement forest, from rooted trees, NP complete, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.         Toggle abstract "The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees." 38 Mihaela Baroni, Stefan Grünewald, Vincent Moulton and Charles Semple. Bounding the number of hybridization events for a consistent evolutionary history. In JOMB, Vol. 51(2):171-182, 2005. Keywords: agreement forest, bound, explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BGMS05.pdf.         Toggle abstract "Evolutionary processes such as hybridisation, lateral gene transfer, and recombination are all key factors in shaping the structure of genes and genomes. However, since such processes are not always best represented by trees, there is now considerable interest in using more general networks instead. For example, in recent studies it has been shown that networks can be used to provide lower bounds on the number of recombination events and also for the number of lateral gene transfers that took place in the evolutionary history of a set of molecular sequences. In this paper we describe the theoretical performance of some related bounds that result when merging pairs of trees into networks. © Springer-Verlag 2005."
2004
39 Mihaela Baroni, Charles Semple and Mike Steel. A framework for representing reticulate evolution. In ACOM, Vol. 8:398-401, 2004. Keywords: explicit network, from clusters, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSS04.pdf.         Toggle 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 paper, we develop a framework for the analysis of these graphs which we call hybrid phylogenies. We are particularly interested in the problem whereby one is given a set of phylogenetic trees and wishes to determine a hybrid phylogeny that 'embeds' each of these trees and which requires the smallest number of hybridisation events. We show that this quantity can be greatly reduced if additional species are involved, and investigate other combinatorial aspects of this and related questions." 40 Katharina Huber, Vincent Moulton and Charles Semple. Replacing cliques by stars in quasi-median graphs. In DAM, Vol. 143(1-3), 2004. Note: http://dx.doi.org/10.1016/j.dam.2004.03.002.         Toggle 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 several results pertaining to the Buneman graph extend to the multi-split graph. In addition, in case Σ is derived from a set ℛ of partitions of X by taking parts together with their complements, we show that the extremal instances where ℛ is either strongly compatible or strongly incompatible are equivalent to G(Σ) being either a tree or a Cartesian product of star trees, respectively. © 2004 Elsevier B.V. All rights reserved."