Who is Who in Phylogenetic Networks

Publications related to 'normal network' : A phylogenetic network is normal if from any node we can reach at least one leaf going only through tree nodes (i.e. going through no reticulation node).   Order by:   Type | Year

Only And Or     related to:

Associated keywords

cluster-containment compressed-network counting display-set distance-between-networks distinct-cluster-network diversity enumeration explicit-network from-distances from-network from-rooted-trees from-trees from-triplets galled-network galled-tree hybridization labeling level-k-phylogenetic-network nested-network normal-network NP-complete phylogenetic-network phylogeny polynomial Program-PhyloSketch reconstruction regular-network SPR-distance spread time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network unicyclic-network uniqueness

Article (Journal)

1 Stephen J. Willson. Unique determination of some homoplasies at hybridization events. In BMB, Vol. 69(5):1709-1725, 2007. Keywords: explicit network, from network, hybridization, labeling, normal network, phylogenetic network, tree-child network. Note: http://www.public.iastate.edu/~swillson/unique.det.pdf.         2 Stephen J. Willson. Reconstruction of Some Hybrid Phylogenetic Networks with Homoplasies from Distances. In BMB, Vol. 69(8):2561-2590, 2007. Keywords: explicit network, from distances, normal network, phylogenetic network, phylogeny, reconstruction. Note: http://www.public.iastate.edu/~swillson/BMB06-97.willson.pdf.         3 Stephen J. Willson. Properties of normal phylogenetic networks. In BMB, Vol. 72(2):340-358, 2010. Keywords: normal network, phylogenetic network, phylogeny, regular network. Note: http://www.public.iastate.edu/~swillson/RestrictionsOnNetworkspap9.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/willson/.         Toggle abstract "A phylogenetic network is a rooted acyclic digraph with vertices corresponding to taxa. Let X denote a set of vertices containing the root, the leaves, and all vertices of outdegree 1. Regard X as the set of vertices on which measurements such as DNA can be made. A vertex is called normal if it has one parent, and hybrid if it has more than one parent. The network is called normal if it has no redundant arcs and also from every vertex there is a directed path to a member of X such that all vertices after the first are normal. This paper studies properties of normal networks. Under a simple model of inheritance that allows homoplasies only at hybrid vertices, there is essentially unique determination of the genomes at all vertices by the genomes at members of X if and only if the network is normal. This model is a limiting case of more standard models of inheritance when the substitution rate is sufficiently low. Various mathematical properties of normal networks are described. These properties include that the number of vertices grows at most quadratically with the number of leaves and that the number of hybrid vertices grows at most linearly with the number of leaves. © 2009 Society for Mathematical Biology." 4 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." 5 Stephen J. Willson. Tree-average distances on certain phylogenetic networks have their weights uniquely determined. In ALMOB, Vol. 7(13), 2012. Keywords: from distances, from network, normal network, phylogenetic network, phylogeny, reconstruction, tree-child network. Note: hhttp://www.public.iastate.edu/~swillson/Tree-AverageDis10All.pdf.         Toggle abstract "A phylogenetic network N has vertices corresponding to species and arcs corresponding to direct genetic inheritance from the species at the tail to the species at the head. Measurements of DNA are often made on species in the leaf set, and one seeks to infer properties of the network, possibly including the graph itself. In the case of phylogenetic trees, distances between extant species are frequently used to infer the phylogenetic trees by methods such as neighbor-joining.This paper proposes a tree-average distance for networks more general than trees. The notion requires a weight on each arc measuring the genetic change along the arc. For each displayed tree the distance between two leaves is the sum of the weights along the path joining them. At a hybrid vertex, each character is inherited from one of its parents. We will assume that for each hybrid there is a probability that the inheritance of a character is from a specified parent. Assume that the inheritance events at different hybrids are independent. Then for each displayed tree there will be a probability that the inheritance of a given character follows the tree; this probability may be interpreted as the probability of the tree. The tree-average distance between the leaves is defined to be the expected value of their distance in the displayed trees.For a class of rooted networks that includes rooted trees, it is shown that the weights and the probabilities at each hybrid vertex can be calculated given the network and the tree-average distances between the leaves. Hence these weights and probabilities are uniquely determined. The hypotheses on the networks include that hybrid vertices have indegree exactly 2 and that vertices that are not leaves have a tree-child. © 2012 Willson; licensee BioMed Central Ltd." 6 Stephen J. Willson. Reconstruction of certain phylogenetic networks from their tree-average distances. In BMB, Vol. 75(10):1840-1878, 2013. Keywords: explicit network, from distances, galled tree, normal network, phylogenetic network, phylogeny, unicyclic network. Note: http://www.public.iastate.edu/~swillson/Tree-AverageReconPaper9.pdf.         Toggle abstract "Trees are commonly utilized to describe the evolutionary history of a collection of biological species, in which case the trees are called phylogenetic trees. Often these are reconstructed from data by making use of distances between extant species corresponding to the leaves of the tree. Because of increased recognition of the possibility of hybridization events, more attention is being given to the use of phylogenetic networks that are not necessarily trees. This paper describes the reconstruction of certain such networks from the tree-average distances between the leaves. For a certain class of phylogenetic networks, a polynomial-time method is presented to reconstruct the network from the tree-average distances. The method is proved to work if there is a single reticulation cycle. © 2013 Society for Mathematical Biology." 7 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.         8 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." 9 Kristina Wicke and Mareike Fischer. Phylogenetic diversity and biodiversity indices on phylogenetic networks. In MB, Vol. 298:80-90, 2018. Keywords: diversity, explicit network, from network, normal network, phylogenetic network, phylogeny. Note: https://arxiv.org/abs/1706.05279.         10 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.         11 Michael Fuchs, Bernhard Gittenberger and Marefatollah Mansouri. Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks. In Australasian Journal of Combinatorics, Vol. 73(2):385-423, 2019. Keywords: counting, explicit network, normal network, phylogenetic network, phylogeny. Note: https://arxiv.org/abs/1803.11325, see also erratum at https://arxiv.org/abs/2006.15784.         12 Gabriel Cardona and Louxin Zhang. Counting and Enumerating Tree-Child Networks and Their Subclasses. In JCSS, Vol. 114:84-104, 2020. Keywords: counting, enumeration, explicit network, galled network, galled tree, normal network, phylogenetic network, phylogeny, tree-child network.         13 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.         14 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.

MastersThesis

15 Maxime Morgado. Propriétés structurelles et relations des classes de réseaux phylogénétiques. Master's thesis, ENS Cachan, 2015. Keywords: compressed network, distinct-cluster network, explicit network, galled network, galled tree, level k phylogenetic network, nested network, normal network, phylogenetic network, phylogeny, regular network, spread, tree containment, tree sibling network, tree-based network, tree-child network, unicyclic network.         16 Kristina Wicke. Extending the concept of phylogenetic diversity and its measures from trees to networks. Master's thesis, Ernst-Moritz-Arndt-Universität Greifswald, 2016. Keywords: diversity, explicit network, from network, normal network, phylogenetic network, phylogeny. Note: https://math-inf.uni-greifswald.de/fileadmin/uni-greifswald/fakultaet/mnf/mathinf/wicke/MasterThesis_KristinaWicke.pdf.

PhdThesis

17 Devin Robert Bickner. On normal networks. PhD thesis, Iowa State University, U.S.A., 2012. Keywords: distance between networks, explicit network, from network, from trees, normal network, phylogenetic network, phylogeny, polynomial, reconstruction, SPR distance. Note: http://gradworks.umi.com/3511361.pdf.         18 Marefatollah Mansouri. Combinatorial properties of phylogenetic networks. PhD thesis, Vienna University of Technology (Austria), Institute of Discrete Mathematics and Geometry, 2020. Keywords: counting, explicit network, galled tree, level k phylogenetic network, normal network, phylogenetic network, phylogeny. Note: https://dmg.tuwien.ac.at/bgitten/Theses/mansouri.pdf.

Misc

19 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.