







Philippe Gambette,
Katharina Huber and
Guillaume Scholz. Uprooted Phylogenetic Networks. In BMB, Vol. 79(9):20222048, 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.



Leo van Iersel,
Vincent Moulton,
Eveline De Swart and
Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):11351154, 2017. Keywords: approximation, explicit network, from binets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/s1153801702754.










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):21512162, 2016. Keywords: explicit network, from trinets, galled tree, phylogenetic network, phylogeny, Program LEV1ATHAN, Program TriLoNet, reconstruction.










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, distinctcluster network, explicit network, galled network, galled tree, level k phylogenetic network, nested network, normal network, phylogenetic network, phylogeny, regular network, spread, tree child network, tree containment, tree sibling network, treebased network, unicyclic network.








Stephen J. Willson. Reconstruction of certain phylogenetic networks from their treeaverage distances. In BMB, Vol. 75(10):18401878, 2013. Keywords: explicit network, from distances, galled tree, normal network, phylogenetic network, phylogeny, unicyclic network. Note: http://www.public.iastate.edu/~swillson/TreeAverageReconPaper9.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 treeaverage distances between the leaves. For a certain class of phylogenetic networks, a polynomialtime method is presented to reconstruct the network from the treeaverage distances. The method is proved to work if there is a single reticulation cycle. © 2013 Society for Mathematical Biology."






Philippe Gambette and
Katharina Huber. On Encodings of Phylogenetic Networks of Bounded Level. In JOMB, Vol. 65(1):157180, 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.archivesouvertes.fr/hal00609130/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 wellstudied 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 level1 (phylogenetic) networks we characterize those level1 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 level1 networks are not satisfied by networks of higher level. © 2011 SpringerVerlag."



Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In CPM12, Vol. 7354:385398 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 socalled 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, edgecolored 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 SpringerVerlag."






Shlomo Moran,
Sagi Snir and
WingKin 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/gnetsTOA7Feb2007.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."



Katharina Huber,
Leo van Iersel,
Steven Kelk and
Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level1 Phylogenetic Networks. In TCBB, Vol. 8(3):607620, 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 level1 phylogenetic networksa type of network slightly more general than a phylogenetic treefrom 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 exponentialtime exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level1 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 level1 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."



Leo van Iersel and
Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ALG, Vol. 60(2):207235, 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/s0045300993330.
Toggle abstract
"A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing socalled 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 polynomialtime algorithms for constructing a level1 respectively a level2 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)."






Jaroslaw Byrka,
Pawel Gawrychowski,
Katharina Huber and
Steven Kelk. Worstcase optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. In Journal of Discrete Algorithms, Vol. 8(1):6575, 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) worstcase 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 worstcase optimal result for level1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level2 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."



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 child network, tree sibling network, visualization. Note: http://dx.doi.org/10.1186/1471210511268, 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."






Leo van Iersel,
Steven Kelk and
Matthias Mnich. Uniqueness, intractability and exact algorithms: reflections on levelk phylogenetic networks. In JBCB, Vol. 7(4):597623, 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.



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.



Philippe Gambette,
Vincent Berry and
Christophe Paul. The structure of levelk phylogenetic networks. In CPM09, Vol. 5577:289300 of LNCS, springer, 2009. Keywords: coalescent, explicit network, galled tree, level k phylogenetic network, phylogenetic network, Program Recodon. Note: http://hallirmm.ccsd.cnrs.fr/lirmm00371485/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 treelikeness. We study the structure of levelk networks, and how they can be decomposed into levelk generators. We also provide a polynomial time algorithm which takes as input the set of levelk generators and builds the set of level(k + 1) generators. Finally, with a simulation study, we evaluate the proportion of levelk phylogenetic networks among networks generated according to the coalescent model with recombination. © 2009 Springer Berlin Heidelberg."



Francesc Rosselló and
Gabriel Valiente. All that Glisters is not Galled. In MBIO, Vol. 221(1):5459, 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, level1 networks, nested networks with nesting depth 1, and evolutionary networks with arcdisjoint reticulation cycles. © 2009 Elsevier Inc. All rights reserved."



Gabriel Valiente. Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R. Pages 184208, Taylor & Francis/CRC Press, 2009. Keywords: counting, distance between networks, galled tree, generation, phylogenetic network, phylogeny, survey, time consistent network, tree child network, tree sibling network. Note: http://books.google.fr/books?id=F4YIIUWb7yMC.






Leo van Iersel and
Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ISAAC08, Vol. 5369:472483 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.





Miguel Arenas,
Gabriel Valiente and
David Posada. Characterization of reticulate networks based on the coalescent with recombination. In MBE, Vol. 25(12):25172520, 2008. Keywords: coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree child network, tree sibling 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."






Daniel H. Huson. Split networks and Reticulate Networks. In
Olivier Gascuel and
Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 247276, 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://wwwab.informatik.unituebingen.de/research/phylonets/GCB2006.pdf.



Dan Gusfield,
Vikas Bansal,
Vineet Bafna and
Yun S. Song. A Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In JCB, Vol. 14(10):12471272, 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.






HoLeung Chan,
Jesper Jansson,
TakWah Lam and
SiuMing Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807832, 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 edgeweighted 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 NPhard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NPhard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press."



Jesper Jansson and
WingKin Sung. Inferring a level1 phylogenetic network from a dense set of rooted triplets. In TCS, Vol. 363(1):6068, 2006. 1 comment 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 networkbased construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level1 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."



Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):10981121, 2006. 1 comment 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 leaflabeled 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 NPhard 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 polynomialtime 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."









Guillaume Bourque and
Louxin Zhang. Models and Methods in Comparative Genomics. In
ChauWen 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.








Elena Dubrova. Phylogenetic networks with edgedisjoint recombination cycles. In Proceedings of SPIE Bioengineered and Bioinspired Systems II (SPIEBBS II), Vol. 5839:381388, 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 galledtrees in which recombination cycles share no edge. We show that the site consistency problem, which is NPhard in general, can be solved in polynomial time for this class of phylogenetic networks."



Trinh N. D. Huynh,
Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265280 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.



Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SODA05, Pages 349358, 2005. 1 comment Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://portal.acm.org/citation.cfm?id=1070481.



Luay Nakhleh,
Tandy Warnow,
C. Randal Linder and
Katherine St. John. Reconstructing reticulate evolution in species  theory and practice. In JCB, Vol. 12(6):796811, 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.






Dan Gusfield,
Satish Eddhu and
Charles Langley. Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. In JBCB, Vol. 2(1):173213, 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 treelike. 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 "galledtree". They gave a polynomialtime algorithm that was intended to determine whether or not a set of sequences could be generated on galledtree. Unfortunately, the algorithm by Wang et al.1 is incomplete and does not constitute a necessary test for the existence of a galledtree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galledtree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiplecrossover recombinations. We also prove that when there is a galledtree for the data, the galledtree 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 NPhard 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 galledtrees, 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."



Dan Gusfield,
Satish Eddhu and
Charles Langley. The fine structure of galls in phylogenetic networks. In INCOMP, Vol. 16(4):459469, 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 treelike. 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 allzero 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 NPhard, 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 nodedisjoint. Wang et al. (2001) provide a sufficient, but not a necessary test, for such solutions. Gusfield et al. (2003, 2004) gave a polynomialtime algorithm that is both a necessary and sufficient test. In this paper, we study in much more detail the fine combinatorial structure of nodedisjoint 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 efficientlycomputable 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."



Jesper Jansson and
WingKin Sung. Inferring a level1 phylogenetic network from a dense set of rooted triplets. In COCOON04, Vol. 3106:462471 of LNCS, springer, 2004. 1 comment 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.



Luay Nakhleh,
Tandy Warnow and
C. Randal Linder. Reconstructing reticulate evolution in species  theory and practice. In RECOMB04, Pages 337346, 2004. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/144nakhleh.pdf.



Mihaela Baroni. Hybrid phylogenies : a graphbased 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.








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






Bin Ma,
Lusheng Wang and
Ming Li. Fixed topology alignment with recombination. In DAM, Vol. 104:281300, 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 4050.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 spinoff 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):16351656, TCBB 10(1):1825, SIDMA 28(1):4966) and are publicly available. We also apply our methods to real data. © 2014 van Iersel et al.; licensee BioMed Central Ltd."






Bin Ma,
Lusheng Wang and
Ming Li. Fixed topology alignment with recombination. In CPM98, Vol. 1448:174188 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.



