Who is Who in Phylogenetic Networks

Publications related to 'galled tree' : A galled tree is a phylogenetic network where reticulation cycles do not overlap. This can be seen as a blobbed tree where each blob is a cycle. Galled trees are also referred to as gt-networks, nested phylogenetic networks of nesting depth 1, level-1 phylogenetic networks. They are generalized by level-f phylogenetic networks, galled networks and tree-child phylogenetic networks.   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network approximation cactus-graph characterization circular-split-system cluster-containment coalescent compressed-network compression consensus counting distance-between-networks distinct-cluster-network distinguishability enumeration evaluation explicit-network exponential-algorithm FPT from-binary-characters from-binets from-clusters from-distances from-network from-quarnets from-quartets from-rooted-trees from-sequences from-splits from-subnetworks from-trinets from-triplets from-unrooted-trees galled-network galled-tree generation heuristic hybridization identifiability inapproximability integer-linear-programming level-k-phylogenetic-network minimum-number mu-distance nearly-stable-network nested-network normal-network NP-complete perfect phylogenetic-network phylogeny planar polynomial population-genetics Program-Beagle Program-GalledTree Program-LEV1ATHAN Program-Lev1Generator Program-Level2 Program-Marlon Program-NetTest Program-Recodon Program-Simplistic Program-Spectronet Program-SplitsTree Program-SPNet Program-T-REX Program-TriLoNet recombination reconstruction regular-network reticulation-visible-network semidirected-network simulation site-consistency software split-network spread statistical-model survey time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network triplet-distance unicyclic-network uniqueness visualization weak-hierarchy

2020

1 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.         2 Louxin Zhang. Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks. In WALCOM20, Vol. 12049:22-27 of LNCS, Springer, 2020. Keywords: cluster containment, galled network, galled tree, nearly-stable network, phylogenetic network, phylogeny, polynomial, reticulation-visible network, survey, time consistent network, tree containment, tree-based network, tree-child network.         3 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.         4 Elizabeth Gross, Leo van Iersel, Remie Janssen, Mark Jones, Colby Long and Yukihiro Murakami. Distinguishing level-1 phylogenetic networks on the basis of data generated by Markov processes. 2020. Keywords: characterization, distinguishability, explicit network, galled tree, phylogenetic network, population genetics, semidirected network, statistical model, uniqueness. Note: https://arxiv.org/abs/2007.08782.         5 Leo van Iersel, Vincent Moulton and Yukihiro Murakami. Reconstructibility of unrooted level-k phylogenetic networks from distances. In AAM, Vol. 120(102075):1-30, 2020. Keywords: from distances, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: https://doi.org/10.1016/j.aam.2020.102075.         6 Cassandra Durell and Stefan Forcey. Level-1 phylogenetic networks and their balanced minimum evolution polytopes. In JOMB, Vol. 80:1235-1263, 2020. Keywords: from distances, galled tree, phylogenetic network, phylogeny, reconstruction, split network. Note: https://arxiv.org/pdf/1905.09160.pdf.         7 Stefan Forcey and Drew Scalzo. Galois connections for phylogenetic networks and their polytopes. 2020. Keywords: characterization, from distances, galled tree, planar, reconstruction, split network. Note: https://arxiv.org/abs/2004.11944.

2018

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 Guillaume Scholz. New algorithms and mathematical tools for phylogenetics beyond trees. PhD thesis, University of East Anglia, 2018. Keywords: circular split system, explicit network, explicit network, from splits, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction, split network, uniqueness. Note: https://ueaeprints.uea.ac.uk/id/eprint/66952.         10 Kuang-Yu Chang, Wing-Kai Hon and Sharma V. Thankachan. Compact Encoding for Galled-Trees and its Applications. In 2018 Data Compression Conference, Pages 297-306, 2018. Keywords: compression, counting, explicit network, galled tree, phylogenetic network, polynomial.

2017

11 Philippe Gambette, Katharina Huber and Steven Kelk. On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters. In JOMB, Vol. 74(7):1729-1751, 2017. Keywords: from clusters, from triplets, galled tree, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://dx.doi.org/10.1007/s00285-016-1068-3.         12 Philippe Gambette, Katharina Huber and Guillaume Scholz. Uprooted Phylogenetic Networks. In BMB, Vol. 79(9):2022-2048, 2017. Keywords: circular split system, explicit network, from splits, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction, split network, uniqueness. Note: http://arxiv.org/abs/1511.08387.         13 Leo van Iersel, Vincent Moulton, Eveline De Swart and Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):1135-1154, 2017. Keywords: approximation, explicit network, from binets, from subnetworks, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/s11538-017-0275-4.

2016

14 Nikita Alexeev and Max A. Alekseyev. Combinatorial Scoring of Phylogenetic Networks. In COCOON16, Vol. 9797:560-572 of LNCS, Springer, 2016. Keywords: cactus graph, counting, explicit network, galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/1602.02841.         15 James Oldman, Taoyang Wu, Leo van Iersel and Vincent Moulton. TriLoNet: Piecing together small networks to reconstruct reticulate evolutionary histories. In MBE, Vol. 33(8):2151-2162, 2016. Keywords: explicit network, from subnetworks, from trinets, galled tree, phylogenetic network, phylogeny, Program LEV1ATHAN, Program TriLoNet, reconstruction.         16 Ioannis G. Tollis and Konstantinos G. Kakoulis. Algorithms for Visualizing Phylogenetic Networks. In GD16, Vol. 9801:183-195 of LNCS, springer, 2016. Keywords: explicit network, galled network, galled tree, NP complete, planar, visualization. Note: http://arxiv.org/abs/1609.00755.

2015

17 Dan Gusfield. Persistent Phylogeny: A Galled-Tree and Integer Linear Programming Approach. In BCB15, Pages 443-451, 2015. Keywords: explicit network, from binary characters, galled tree, integer linear programming, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1506.00678.         18 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.

2014

19 Judith Keijsper and Rudi Pendavingh. Reconstructing a phylogenetic level-1 network from quartets. In BMB, Vol. 76(10):2517-2541, 2014. Keywords: explicit network, from quartets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1308.5206.

2013

20 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."

2012

21 Philippe Gambette and Katharina Huber. On Encodings of Phylogenetic Networks of Bounded Level. In JOMB, Vol. 65(1):157-180, 2012. Keywords: characterization, explicit network, from clusters, from rooted trees, from triplets, galled tree, identifiability, level k phylogenetic network, phylogenetic network, uniqueness, weak hierarchy. Note: http://hal.archives-ouvertes.fr/hal-00609130/en/.         Toggle abstract "Phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Like phylogenetic trees, such networks canonically induce collections of phylogenetic trees, clusters, and triplets, respectively. Thus it is not surprising that many network approaches aim to reconstruct a phylogenetic network from such collections. Related to the well-studied perfect phylogeny problem, the following question is of fundamental importance in this context: When does one of the above collections encode (i. e. uniquely describe) the network that induces it? For the large class of level-1 (phylogenetic) networks we characterize those level-1 networks for which an encoding in terms of one (or equivalently all) of the above collections exists. In addition, we show that three known distance measures for comparing phylogenetic networks are in fact metrics on the resulting subclass and give the diameter for two of them. Finally, we investigate the related concept of indistinguishability and also show that many properties enjoyed by level-1 networks are not satisfied by networks of higher level. © 2011 Springer-Verlag." 22 Jesper Jansson and Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In CPM12, Vol. 7354:385-398 of LNCS, springer, 2012. Keywords: distance between networks, explicit network, from network, galled tree, phylogenetic network, phylogeny, polynomial, triplet distance. Note: http://www.df.lth.se/~jj/Publications/d_rt_for_Galled_Trees5_CPM_2012.pdf.         Toggle abstract "We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n leaves then the rooted triplet distance can be computed in o(n 2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost- monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new related results that may be of independent interest. © 2012 Springer-Verlag."

2011

23 Shlomo Moran, Sagi Snir and Wing-Kin Sung. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds. In ACM Transactions on Algorithms, Vol. 7(4), 2011. Keywords: evaluation, galled tree, phylogenetic network. Note: http://www.cs.technion.ac.il/~moran/r/PS/gnets-TOA-7Feb2007.pdf.         Toggle abstract "A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as convex recoloring (CR).While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest. © 2011 ACM." 24 Katharina Huber, Leo van Iersel, Steven Kelk and Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks. In TCBB, Vol. 8(3):607-620, 2011. Keywords: explicit network, from triplets, galled tree, generation, heuristic, phylogenetic network, phylogeny, Program LEV1ATHAN, Program Lev1Generator, reconstruction, software. Note: http://arxiv.org/abs/0910.4067.         Toggle abstract "Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks-a type of network slightly more general than a phylogenetic tree-from triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of Lev1athan is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that Lev1athan is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise. © 2011 IEEE." 25 Leo van Iersel and Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ALG, Vol. 60(2):207-235, 2011. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic. Note: http://dx.doi.org/10.1007/s00453-009-9333-0.         Toggle abstract "A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T| k+1), if k is a fixed upper bound on the level of the network. © 2009 The Author(s)."

2010

26 Jaroslaw Byrka, Pawel Gawrychowski, Katharina Huber and Steven Kelk. Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. In Journal of Discrete Algorithms, Vol. 8(1):65-75, 2010. Keywords: approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/0710.3258.         Toggle abstract "The study of phylogenetic networks is of great interest to computational evolutionary biology and numerous different types of such structures are known. This article addresses the following question concerning rooted versions of phylogenetic networks. What is the maximum value of p ∈ [0, 1] such that for every input set T of rooted triplets, there exists some network N such that at least p | T | of the triplets are consistent with N? We call an algorithm that computes such a network (where p is maximum) worst-case optimal. Here we prove that the set containing all triplets (the full triplet set) in some sense defines p. Moreover, given a network N that obtains a fraction p′ for the full triplet set (for any p′), we show how to efficiently modify N to obtain a fraction ≥ p′ for any given triplet set T. We demonstrate the power of this insight by presenting a worst-case optimal result for level-1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p ≥ 0.61. We emphasize that, because we are taking | T | as a (trivial) upper bound on the size of an optimal solution for each specific input T, the results in this article do not exclude the existence of approximation algorithms that achieve approximation ratio better than p. Finally, we note that all the results in this article also apply to weighted triplet sets. © 2009 Elsevier B.V. All rights reserved." 27 Miguel Arenas, Mateus Patricio, David Posada and Gabriel Valiente. Characterization of Phylogenetic Networks with NetTest. In BMCB, Vol. 11:268, 2010. Keywords: explicit network, galled tree, phylogenetic network, Program NetTest, software, time consistent network, tree sibling network, tree-child network, visualization. Note: http://dx.doi.org/10.1186/1471-2105-11-268, software available at http://darwin.uvigo.es/software/nettest/.         Toggle abstract "Background: Typical evolutionary events like recombination, hybridization or gene transfer make necessary the use of phylogenetic networks to properly depict the evolution of DNA and protein sequences. Although several theoretical classes have been proposed to characterize these networks, they make stringent assumptions that will likely not be met by the evolutionary process. We have recently shown that the complexity of simulated networks is a function of the population recombination rate, and that at moderate and large recombination rates the resulting networks cannot be categorized. However, we do not know whether these results extend to networks estimated from real data.Results: We introduce a web server for the categorization of explicit phylogenetic networks, including the most relevant theoretical classes developed so far. Using this tool, we analyzed statistical parsimony phylogenetic networks estimated from ~5,000 DNA alignments, obtained from the NCBI PopSet and Polymorphix databases. The level of characterization was correlated to nucleotide diversity, and a high proportion of the networks derived from these data sets could be formally characterized.Conclusions: We have developed a public web server, NetTest (freely available from the software section at http://darwin.uvigo.es), to formally characterize the complexity of phylogenetic networks. Using NetTest we found that most statistical parsimony networks estimated with the program TCS could be assigned to a known network class. The level of network characterization was correlated to nucleotide diversity and dependent upon the intra/interspecific levels, although no significant differences were detected among genes. More research on the properties of phylogenetic networks is clearly needed. © 2010 Arenas et al; licensee BioMed Central Ltd."

2009

28 Leo van Iersel, Steven Kelk and Matthias Mnich. Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. In JBCB, Vol. 7(4):597-623, 2009. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://arxiv.org/pdf/0712.2932v2.         29 Leo van Iersel. Algorithms, Haplotypes and Phylogenetic Networks. PhD thesis, Eindhoven University of Technology, The Netherlands, 2009. Keywords: evaluation, explicit network, exponential algorithm, FPT, from triplets, galled tree, level k phylogenetic network, mu distance, phylogenetic network, phylogeny, polynomial, Program Level2, Program Marlon, Program Simplistic, Program T REX, reconstruction. Note: http://www.win.tue.nl/~liersel/thesis_vaniersel_viewing.pdf.         30 Philippe Gambette, Vincent Berry and Christophe Paul. The structure of level-k phylogenetic networks. In CPM09, Vol. 5577:289-300 of LNCS, springer, 2009. Keywords: coalescent, explicit network, galled tree, level k phylogenetic network, phylogenetic network, Program Recodon. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485/en/.         Toggle abstract "Evolution is usually described as a phylogenetic tree, but due to some exchange of genetic material, it can be represented as a phylogenetic network which has an underlying tree structure. The notion of level was recently introduced as a parameter on realistic kinds of phylogenetic networks to express their complexity and tree-likeness. We study the structure of level-k networks, and how they can be decomposed into level-k generators. We also provide a polynomial time algorithm which takes as input the set of level-k generators and builds the set of level-(k + 1) generators. Finally, with a simulation study, we evaluate the proportion of level-k phylogenetic networks among networks generated according to the coalescent model with recombination. © 2009 Springer Berlin Heidelberg." 31 Francesc Rosselló and Gabriel Valiente. All that Glisters is not Galled. In MBIO, Vol. 221(1):54-59, 2009. Keywords: galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/0904.2448.         Toggle abstract "Galled trees, evolutionary networks with isolated reticulation cycles, have appeared under several slightly different definitions in the literature. In this paper, we establish the actual relationships between the main four such alternative definitions: namely, the original galled trees, level-1 networks, nested networks with nesting depth 1, and evolutionary networks with arc-disjoint reticulation cycles. © 2009 Elsevier Inc. All rights reserved." 32 Gabriel Valiente. Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R. Pages 184-208, Taylor & Francis/CRC Press, 2009. Keywords: counting, distance between networks, galled tree, generation, phylogenetic network, phylogeny, survey, time consistent network, tree sibling network, tree-child network. Note: http://books.google.fr/books?id=F4YIIUWb7yMC.

2008

33 Leo van Iersel and Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ISAAC08, Vol. 5369:472-483 of LNCS, springer, 2008. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic. Note: http://arxiv.org/abs/0805.1859.         34 Wing-Kin Sung. Constructing a Galled Phylogenetic Network. In Ming-Yang Kao editor, Encyclopedia of Algorithms, Springer Reference, 2008. Keywords: explicit network, from triplets, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/978-0-387-30162-4_92.         35 Miguel Arenas, Gabriel Valiente and David Posada. Characterization of reticulate networks based on the coalescent with recombination. In MBE, Vol. 25(12):2517-2520, 2008. Keywords: coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree sibling network, tree-child network. Note: http://dx.doi.org/10.1093/molbev/msn219.         Toggle abstract "Phylogenetic networks aim to represent the evolutionary history of taxa. Within these, reticulate networks are explicitly able to accommodate evolutionary events like recombination, hybridization, or lateral gene transfer. Although several metrics exist to compare phylogenetic networks, they make several assumptions regarding the nature of the networks that are not likely to be fulfilled by the evolutionary process. In order to characterize the potential disagreement between the algorithms and the biology, we have used the coalescent with recombination to build the type of networks produced by reticulate evolution and classified them as regular, tree sibling, tree child, or galled trees. We show that, as expected, the complexity of these reticulate networks is a function of the population recombination rate. At small recombination rates, most of the networks produced are already more complex than regular or tree sibling networks, whereas with moderate and large recombination rates, no network fit into any of the standard classes. We conclude that new metrics still need to be devised in order to properly compare two phylogenetic networks that have arisen from reticulating evolutionary process. © 2008 The Authors."

2007

36 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.         37 Dan Gusfield, Vikas Bansal, Vineet Bafna and Yun S. Song. A Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In JCB, Vol. 14(10):1247-1272, 2007. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, Program Beagle, Program GalledTree, recombination, reconstruction, software. Note: http://www.eecs.berkeley.edu/~yss/Pub/decomposition.pdf.

2006

38 Ho-Leung Chan, Jesper Jansson, Tak-Wah Lam and Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807-832, 2006. Keywords: explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf.         Toggle abstract "Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press." 39 Jesper Jansson and Wing-Kin Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In TCS, Vol. 363(1):60-68, 2006. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt8_TCS2006.pdf.         Toggle abstract "We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O (| T |2) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O (| T |5 / 3)-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets. © 2006 Elsevier B.V. All rights reserved." 40 Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):1098-1121, 2006. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf.         Toggle abstract "This paper considers the problem of determining whether a given set Τ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input Τ is dense, we solve the problem in O(|Τ|) time, which is optimal since the size of the input is Θ(|Τ|). In comparison, the previously fastest algorithm for this problem runs in O(|Τ|2) time. We also develop an optimal O(|Τ|)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with Τ, where L is the set of leaf labels in Τ, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set Τ of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 ·|Τ| of the rooted triplets in Τ. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in Τ. © 2006 Society for Industrial and Applied Mathematics." 41 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.         42 Arvind Gupta, Ján Manuch, Xiaohong Zhao and Ladislav Stacho. Characterization of the existence of galled-tree networks. In JBCB, Vol. 4(6):1309-1328, 2006. Keywords: characterization, galled tree. Note: http://www.pims.math.ca/~manuch/papers/characterization_JBCB2006.pdf.         43 Yun S. Song. A Concise Necessary and Sufficient Condition for the Existence of a Galled-Tree. In TCBB, Vol. 3(2):186-191, 2006. Keywords: characterization, from sequences, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.eecs.berkeley.edu/~yss/Pub/nasc4gall.pdf.         44 Guillaume Bourque and Louxin Zhang. Models and Methods in Comparative Genomics. In Chau-Wen Tseng editor, Advances in Computers, Special Volume: Computational Biology, Vol. 68, Elsevier, 2006. Keywords: from distances, from rooted trees, from sequences, galled tree, phylogenetic network, phylogeny, survey. Note: http://www.math.nus.edu.sg/~matzlx/papers/CompGen_ZLX.pdf.

2005

45 Ho-Leung Chan, Jesper Jansson, Tak-Wah Lam and Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In MFCS05, Vol. 3618:224-235 of LNCS, springer, 2005. Keywords: from distances, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/11549345_20.         46 Elena Dubrova. Phylogenetic networks with edge-disjoint recombination cycles. In Proceedings of SPIE Bioengineered and Bioinspired Systems II (SPIE-BBS II), Vol. 5839:381-388, 2005. Keywords: galled tree, phylogenetic network, polynomial, site consistency. Note: http://dx.doi.org/10.1117/12.607910.         Toggle abstract "Phylogenetic analysis is a branch of biology that establishes the evolutionary relationships between living organisms. The goal of phylogenetic analysis is to determine the order and approximate timing of speciation events in the evolution of a given set of species. Phylogenetic networks allow to represent evolutionary histories that include events like recombination and hybridization. In this paper, we introduce a class of phylogenetic networks called extended galled-trees in which recombination cycles share no edge. We show that the site consistency problem, which is NP-hard in general, can be solved in polynomial time for this class of phylogenetic networks." 47 Trinh N. D. Huynh, Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265-280 of LNCS, springer, 2005. Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction. Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.         48 Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SODA05, Pages 349-358, 2005. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://portal.acm.org/citation.cfm?id=1070481.         49 Luay Nakhleh, Tandy Warnow, C. Randal Linder and Katherine St. John. Reconstructing reticulate evolution in species - theory and practice. In JCB, Vol. 12(6):796-811, 2005. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/NWLSjcb.pdf.

2004

50 Dan Gusfield, Satish Eddhu and Charles Langley. Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. In JBCB, Vol. 2(1):173-213, 2004. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, recombination, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/exfinalrec.pdf.         Toggle abstract "A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not tree-like. In a seminal paper, Wang et al.1 studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a "galled-tree". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.1 is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree minimizing the number of recombinations is "essentially unique" . We. also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NP-hard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree. Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in general phylogenetic networks. This paper greatly extends the conference version that appears in an earlier work.8 PowerPoint slides of the conference talk can be found at our website. © Imperial College Press." 51 Dan Gusfield, Satish Eddhu and Charles Langley. The fine structure of galls in phylogenetic networks. In INCOMP, Vol. 16(4):459-469, 2004. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/informs.pdf.         Toggle abstract "A phylogenetic network is a generalization of a phylogenetic tree, allowing properties that are not tree-like. With the growth of genomic data, much of which does not fit ideal tree models, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks (Posada and Crandall 2001, Schierup and Hein 2000). Wang et al. (2001) studied the problem of constructing a phylogenetic network for a set of n binary sequences derived from the all-zero ancestral sequence, when each site in the sequence can mutate from zero to one at most once in the network, and recombination between sequences is allowed. They showed that the problem of minimizing the number of recombinations in such networks is NP-hard, but introduced a special case of the problem, i.e., to determine whether the sequences could be derived on a phylogenetic network where the recombination cycles are node-disjoint. Wang et al. (2001) provide a sufficient, but not a necessary test, for such solutions. Gusfield et al. (2003, 2004) gave a polynomial-time algorithm that is both a necessary and sufficient test. In this paper, we study in much more detail the fine combinatorial structure of node-disjoint cycles in phylogenetic networks, both for purposes of insight into phylogenetic networks and to speed up parts of the previous algorithm. We explicitly characterize all the ways in which mutations can be arranged on a disjoint cycle, and prove a strong necessary condition for a set of mutations to be on a disjoint cycle. The main contribution here is to show how structure in the phylogenetic network is reflected in the structure of an efficiently-computable graph, called the conflict graph. The success of this approach suggests that additional insight into the structure of phylogenetic networks can be obtained by exploring structural properties of the conflict graph." 52 Jesper Jansson and Wing-Kin Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In COCOON04, Vol. 3106:462-471 of LNCS, springer, 2004. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt6_COCOON2004.pdf.         53 Luay Nakhleh, Tandy Warnow and C. Randal Linder. Reconstructing reticulate evolution in species - theory and practice. In RECOMB04, Pages 337-346, 2004. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/144-nakhleh.pdf.         54 Mihaela Baroni. Hybrid phylogenies : a graph-based approach to represent reticulate evolution. PhD thesis, University of Canterbury, New Zealand, 2004. Keywords: explicit network, from rooted trees, galled tree, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network. Note: http://ir.canterbury.ac.nz/bitstream/10092/4803/1/baroni_thesis.pdf.

2003

55 Dan Gusfield, Satish Eddhu and Charles Langley. Efficient reconstruction of phylogenetic networks with constrained recombination. In CSB03, Pages 363-374, 2003. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, recombination, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/ieeefinal.pdf.

2001

56 Lusheng Wang, Kaizhong Zhang and Louxin Zhang. Perfect phylogenetic networks with recombination. In SAC01, Pages 46-50, 2001. Keywords: from sequences, galled tree, NP complete, perfect, phylogenetic network, phylogeny, polynomial, recombination, reconstruction. Note: http://dx.doi.org/10.1145/372202.372271.

2000

57 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In DAM, Vol. 104:281-300, 2000. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759.         Toggle abstract "Background: Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. Even for binary trees, exact solvers struggle to solve instances with reticulation number larger than 40-50.Results: Here we present CycleKiller and NonbinaryCycleKiller, the first methods to produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations.Conclusions: Using simulations, we demonstrate that these algorithms run quickly for large and difficult instances, producing solutions that are very close to optimality. As a spin-off from our simulations we also present TerminusEst, which is the fastest exact method currently available that can handle nonbinary trees: this is used to measure the accuracy of the NonbinaryCycleKiller algorithm. All three methods are based on extensions of previous theoretical work (SIDMA 26(4):1635-1656, TCBB 10(1):18-25, SIDMA 28(1):49-66) and are publicly available. We also apply our methods to real data. © 2014 van Iersel et al.; licensee BioMed Central Ltd."

1998

58 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In CPM98, Vol. 1448:174-188 of LNCS, springer, 1998. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1007/BFb0030789.