Who is Who in Phylogenetic Networks

Publications of Mike Steel     Order by:   Type | Year

Associated keywords

abstract-network agreement-forest characterization cluster-containment compressed-network consensus counting explicit-network from-clusters from-distances from-network from-rooted-trees from-sequences from-splits from-unrooted-trees FU-stable-network galled-tree generation hybridization level-k-phylogenetic-network minimum-number normal-network NP-complete phylogenetic-network phylogeny polynomial Program-Beagle Program-PhyloSketch Program-Spectronet Program-SplitsTree Program-SPNet recombination reconstruction regular-network split split-network SPR-distance statistical-model supernetwork survey time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network unicyclic-network visualization

Article (Journal)

1 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.         2 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.         3 Katharina Huber, Vincent Moulton, Mike Steel and Taoyang Wu. Folding and unfolding phylogenetic trees and networks. In JOMB, Vol. 73(6):1761-1780, 2016. Keywords: compressed network, explicit network, FU-stable network, NP complete, phylogenetic network, phylogeny, tree containment, tree sibling network. Note: http://arxiv.org/abs/1506.04438.         4 Andrew R. Francis and Mike Steel. Tree-like Reticulation Networks - When Do Tree-like Distances Also Support Reticulate Evolution? In MBIO, Vol. 259:12-19, 2015. Keywords: from distances, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/1405.2965.         5 Andrew R. Francis and Mike Steel. Which phylogenetic networks are merely trees with additional arcs? In Systematic Biology, Vol. 64(5):768-777, 2015. Keywords: explicit network, phylogenetic network, phylogeny, polynomial, tree-based network. Note: http://arxiv.org/abs/1502.07045.         6 Eric Bapteste, Leo van Iersel, Axel Janke, Scott Kelchner, Steven Kelk, James O. McInerney, David A. Morrison, Luay Nakhleh, Mike Steel, Leen Stougie and James B. Whitfield. Networks: expanding evolutionary thinking. In Trends in Genetics, Vol. 29(8):439-441, 2013. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction. Note: http://bioinf.nuim.ie/wp-content/uploads/2013/06/Bapteste-TiG-2013.pdf.         Toggle abstract "Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes. © 2013 Elsevier Ltd." 7 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." 8 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." 9 James B. Whitfield, Sydney A. Cameron, Daniel H. Huson and Mike Steel. Filtered Z-Closure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees. In Systematic Biology, Vol. 57(6):939-947, 2008. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, split, split network, supernetwork. Note: http://www.life.uiuc.edu/scameron/pdfs/Filtered%20Z-closure%20SystBiol.pdf.         10 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." 11 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.         12 Mihaela Baroni and Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.         Toggle abstract "We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg." 13 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." 14 Daniel H. Huson, Tobias Dezulian, Tobias Kloepper and Mike Steel. Phylogenetic Super-Networks from Partial Trees. In TCBB, Vol. 1(4):151-158, 2004. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, supernetwork. Note: http://hdl.handle.net/10092/3177.         Toggle abstract "In practice, one is often faced with incomplete phylogenetic data, such as a collection of partial trees or partial splits. This paper poses the problem of Inferring a phylogenetic super-network from such data and provides an efficient algorithm for doing so, called the Z-closure method. Additionally, the questions of assigning lengths to the edges of the network and how to restrict the "dimensionality" of the network are addressed. Applications to a set of five published partial gene trees relating different fungal species and to six published partial gene trees relating different grasses illustrate the usefulness of the method and an experimental study confirms Its potential. The method Is implemented as a plug-in for the program SplitsTree4. © 2004 IEEE."

InProceedings

15 Daniel H. Huson, Mike Steel and James B. Whitfield. Reducing Distortion in Phylogenetic Networks. In WABI06, Vol. 4175:150-161 of LNCS, springer, 2006. Keywords: phylogenetic network, reconstruction. Note: http://www.math.canterbury.ac.nz/~m.steel/research/Non_UC/files/distortion.pdf.         16 Daniel H. Huson, Tobias Kloepper, Peter J. Lockhart and Mike Steel. Reconstruction of Reticulate Networks from Gene Trees. In RECOMB05, Vol. 3500:233-249 of LNCS, springer, 2005. Keywords: from rooted trees, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://dx.doi.org/10.1007/11415770_18.         17 Tobias Dezulian and Mike Steel. Phylogenetic closure operations and homoplasy-free evolution. In IFCS04, Pages 395-416, springer, 2004. Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/closure_ops.pdf.

InBook

18 Mike Steel. Introduction to phylogenetic networks. In Phylogeny: Discrete and Random Processes in Evolution, Vol. 89 of CBMS-NSF Regional Conference Series in Applied Mathematics, Chapter 10, SIAM, 2016. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, survey. Note: http://bookstore.siam.org/cb89/.         19 Daniel H. Huson. Split networks and Reticulate Networks. In Olivier Gascuel and Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 247-276, Oxford University Press, 2007. Keywords: abstract network, consensus, from rooted trees, from sequences, from splits, from unrooted trees, galled tree, hybridization, phylogenetic network, phylogeny, Program Beagle, Program Spectronet, Program SplitsTree, Program SPNet, recombination, reconstruction, split network, survey. Note: similar to http://www-ab.informatik.uni-tuebingen.de/research/phylonets/GCB2006.pdf.         20 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.

Misc

21 Andrew R. Francis, Daniel H. Huson and Mike Steel. Normalising phylogenetic networks. 2020. Keywords: explicit network, from network, normal network, phylogenetic network, phylogeny, polynomial, Program PhyloSketch, reconstruction, tree-child network. Note: https://arxiv.org/abs/2008.07797.         22 Sha Zhu, James H. Degnan and Mike Steel. Probabilistic modeling of gene trees given species networks. 2011. Keywords: from network, generation, phylogenetic network, phylogeny, statistical model. Note: Poster, http://www.newton.ac.uk/programmes/PLG/Zhu.pdf.