Who is Who in Phylogenetic Networks

Publications related to 'polynomial'   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network agreement-forest approximation APX-hard bound branch-length cactus-graph characterization circular-split-system cluster-containment compressed-network compression counting distance-between-networks diversity duplication dynamic-programming evaluation explicit-network exponential-algorithm FPT from-binary-characters from-binets from-clusters from-distances from-multilabeled-tree from-multistate-characters from-network from-quartets from-rooted-trees from-sequences from-species-tree from-splits from-subnetworks from-trees from-trinets from-triplets from-unrooted-trees galled-network galled-tree genetically-stable-network heuristic hybridization integer-linear-programming isomorphism k-reticulated kth-order-reduced-network labeling lateral-gene-transfer level-k-phylogenetic-network LGT-network loss MASN minimum-number mu-distance nearly-stable-network NeighborNet nested-network normal-network NP-complete optimal-realization orientation outerplanar parental-hybridization parsimony partly-reduced-networks perfect phylogenetic-network phylogeny planar polynomial Program-ARTNET Program-CMPT Program-Dendroscope Program-ecceTERA Program-Fylogenetica Program-GraphDTL Program-Hybroscale Program-Level2 Program-Marlon Program-McKiTscH Program-Mowgli Program-MPNet Program-PhyloSketch Program-QuasiDec Program-RANGER-DTL Program-SAGE Program-Simplistic Program-SplitsTree Program-SPNet Program-T-REX Program-TriLoNet Program-Xscape quasi-median-network quasi-reticulation-visible-network recombination reconstruction reduced-networks regular-network reticulation-visible-network site-consistency software split split-network SPR-distance spread survey time-consistent-network tree-containment tree-sibling-network tree-based-network tree-child-network tree-child-sequence tripartition-distance triplet-distance uniqueness visualization weakly-compatible weakly-displaying

Article (Journal)

1 Mihaela Baroni, Charles Semple and Mike Steel. Hybrids in Real Time. In Systematic Biology, Vol. 55(1):46-56, 2006. Keywords: agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network. Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf.         Toggle abstract "We describe some new and recent results that allow for the analysis and representation of reticulate evolution by nontree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. Copyright © Society of Systematic Biologists." 2 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." 3 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." 4 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." 5 John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In DAM, Pages 239-260, 1998. Keywords: from sequences, NP complete, polynomial, recombination, reconstruction. Note: http://citeseer.ist.psu.edu/76600.html.         6 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.         7 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved." 8 Stephen J. Willson. Reconstruction of certain phylogenetic networks from the genomes at their leaves. In JTB, Vol. 252(2):185-376, 2008. Keywords: labeling, polynomial. Note: http://www.public.iastate.edu/~swillson/ReconstructNormalHomopap6.pdf.         Toggle abstract "A network N is a rooted acyclic digraph. A base-set X for N is a subset of vertices including the root (or outgroup), all leaves, and all vertices of outdegree 1. A simple model of evolution is considered in which all characters are binary and in which back-mutations occur only at hybrid vertices. It is assumed that the genome is known for each member of the base-set X. If the network is known and is assumed to be "normal," then it is proved that the genome of every vertex is uniquely determined and can be explicitly reconstructed. Under additional hypotheses involving time-consistency and separation of the hybrid vertices, the network itself can also be reconstructed from the genomes of all members of X. An explicit polynomial-time procedure is described for performing the reconstruction. © 2008 Elsevier Ltd. All rights reserved." 9 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.         10 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks. In BIO, Vol. 24(13):1481-1488, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network. Note: http://dx.doi.org/10.1093/bioinformatics/btn231.         Toggle abstract "Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this articlea distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)." 11 Johannes Fischer and Daniel H. Huson. New Common Ancestor Problems in Trees and Directed Acyclic Graphs. In IPL, Vol. 110(8-9):331-335, 2010. Keywords: explicit network, phylogenetic network, polynomial. Note: http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf.         Toggle abstract "We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes. We also consider a "fuzzy" variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This "fuzzy" algorithm is also applicable to LCAs in trees, with the same complexities. © 2010 Elsevier B.V. All rights reserved." 12 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)." 13 Leo van Iersel and Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245-255, 2011. Keywords: APX hard, explicit network, from clusters, from rooted trees, from sequences, from triplets, level k phylogenetic network, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1004.5332.         Toggle abstract "Rooted phylogenetic networks are used to model non-treelike evolutionary histories. Such networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some well-defined sense simultaneously represents them all. We review these four models and investigate how they are related. Motivated by the parsimony principle, one often aims to construct a network that contains as few reticulations (non-treelike evolutionary events) as possible. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary (i.e. fully resolved) trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several computational complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge. © 2010 Elsevier Ltd." 14 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." 15 Mihaela Baroni and Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.         Toggle abstract "We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg." 16 Lavanya Kannan, Hua Li and Arcady Mushegian. A Polynomial-Time Algorithm Computing Lower and Upper Bounds of the Rooted Subtree Prune and Regraft Distance. In JCB, Vol. 18(5):743-757, 2011. Keywords: bound, minimum number, polynomial, SPR distance. Note: http://dx.doi.org/10.1089/cmb.2010.0045.         Toggle abstract "Rooted, leaf-labeled trees are used in biology to represent hierarchical relationships of various entities, most notably the evolutionary history of molecules and organisms. Rooted Subtree Prune and Regraft (rSPR) operation is a tree rearrangement operation that is used to transform a tree into another tree that has the same set of leaf labels. The minimum number of rSPR operations that transform one tree into another is denoted by drSPR and gives a measure of dissimilarity between the trees, which can be used to compare trees obtained by different approaches, or, in the context of phylogenetic analysis, to detect horizontal gene transfer events by finding incongruences between trees of different evolving characters. The problem of computing the exact d rSPR measure is NP-hard, and most algorithms resort to finding sequences of rSPR operations that are sufficient for transforming one tree into another, thereby giving upper bound heuristics for the distance. In this article, we present an O(n4) recursive algorithm D-Clust that gives both lower bound and upper bound heuristics for the distance between trees with n shared leaves and also gives a sequence of operations that transforms one tree into another. Our experiments on simulated pairs of trees containing up to 100 leaves showed that the two bounds are almost equal for small distances, thereby giving the nearly-precise actual value, and that the upper bound tends to be close to the upper bounds given by other approaches for all pairs of trees. © Copyright 2011, Mary Ann Liebert, Inc. 2011." 17 Bui Quang Minh, Fabio Pardi, Steffen Klaere and Arndt von Haeseler. Budgeted Phylogenetic Diversity on Circular Split Systems. In TCBB, Vol. 6(1):22-29, 2009. Keywords: abstract network, circular split system, dynamic programming, from network, phylogenetic network, polynomial, split, split network. Note: http://dx.doi.org/10.1109/TCBB.2008.54.         Toggle abstract "In the last 15 years, Phylogenetic Diversity (PD) has gained interest in the community of conservation biologists as a surrogate measure for assessing biodiversity. We have recently proposed two approaches to select taxa for maximizing PD, namely PD with budget constraints and PD on split systems. In this paper, we will unify these two strategies and present a dynamic programming algorithm to solve the unified framework of selecting taxa with maximal PD under budget constraints on circular split systems. An improved algorithm will also be given if the underlying split system is a tree. © 2006 IEEE." 18 Magnus Bordewich and Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):69-85, 2012. Keywords: abstract network, approximation, diversity, phylogenetic network, polynomial, split network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS11.pdf.         Toggle abstract "Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1-1/e)-approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1-1/e)-approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al. © 2011 Springer-Verlag." 19 Mukul S. Bansal, Guy Banay, J. Peter Gogarten and Ron Shamir. Detecting Highways of Horizontal Gene Transfer. In JCB, Vol. 18(9):1087-1114, 2011. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://people.csail.mit.edu/mukul/HighwayFull_preprint.pdf.         Toggle abstract "In a horizontal gene transfer (HGT) event, a gene is transferred between two species that do not have an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species and m input quartet trees, we give an efficient O(m+n 2)-time algorithm for detecting highways, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method. © 2011, Mary Ann Liebert, Inc." 20 Philippe Gambette, Vincent Berry and Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012. Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, orientation, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network. Note: http://hal.archives-ouvertes.fr/hal-00678046/en/.         Toggle abstract "Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press." 21 Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara and Gabriel Valiente. Faster computation of the Robinson–Foulds distance between phylogenetic networks. In Information Sciences, Vol. 197:77-90, 2012. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread.         Toggle abstract "The Robinson-Foulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N 1, N 2 with n leaf labels and at most m nodes and e edges each, the Robinson-Foulds distance measures the number of clusters of descendant leaves not shared by N 1 and N 2. The fastest known algorithm for computing the Robinson-Foulds distance between N 1 and N 2 runs in O(me) time. In this paper, we improve the time complexity to O(ne/log n) for general phylogenetic networks and O(nm/log n) for general phylogenetic networks with bounded degree (assuming the word RAM model with a word length of ⌈logn⌉ bits), and to optimal O(m) time for leaf-outerplanar networks as well as optimal O(n) time for level-1 phylogenetic networks (that is, galled-trees). We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k network is at most k + 1, which implies that for one level-1 and one level-k phylogenetic network, our algorithm runs in O((k + 1)e) time. © 2012 Elsevier Inc. All rights reserved." 22 Michel Habib and Thu-Hien To. Constructing a Minimum Phylogenetic Network from a Dense Triplet Set. In JBCB, Vol. 10(5):1250013, 2012. Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1103.2266.         Toggle abstract "For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with T, if there is any, in time O(|T| k+1 n⌊4k/3⌋+1). © 2012 Imperial College Press." 23 Sven Herrmann and Vincent Moulton. Computing the blocks of a quasi-median graph. In DAM, Vol. 179:129-138, 2014. Keywords: abstract network, from sequences, phylogenetic network, phylogeny, polynomial, Program QuasiDec, quasi-median network, reconstruction. Note: http://arxiv.org/abs/1206.6135.         24 Mareike Fischer, Leo van Iersel, Steven Kelk and Celine Scornavacca. On Computing The Maximum Parsimony Score Of A Phylogenetic Network. In SIDMA, Vol. 29(1):559-585, 2015. Keywords: APX hard, cluster containment, explicit network, FPT, from network, from sequences, integer linear programming, level k phylogenetic network, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, Program MPNet, reconstruction, software. Note: http://arxiv.org/abs/1302.2430.         25 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.         26 Thi-Hau Nguyen, Vincent Ranwez, Vincent Berry and Celine Scornavacca. Support Measures to Estimate the Reliability of Evolutionary Events Predicted by Reconciliation Methods. In PLoS ONE, Vol. 8(10):e73667, 2013. Keywords: duplication, from rooted trees, from species tree, phylogenetic network, phylogeny, polynomial, Program GraphDTL, reconstruction. Note: http://dx.doi.org/10.1371/journal.pone.0073667.         Toggle abstract "The genome content of extant species is derived from that of ancestral genomes, distorted by evolutionary events such as gene duplications, transfers and losses. Reconciliation methods aim at recovering such events and at localizing them in the species history, by comparing gene family trees to species trees. These methods play an important role in studying genome evolution as well as in inferring orthology relationships. A major issue with reconciliation methods is that the reliability of predicted evolutionary events may be questioned for various reasons: Firstly, there may be multiple equally optimal reconciliations for a given species tree-gene tree pair. Secondly, reconciliation methods can be misled by inaccurate gene or species trees. Thirdly, predicted events may fluctuate with method parameters such as the cost or rate of elementary events. For all of these reasons, confidence values for predicted evolutionary events are sorely needed. It was recently suggested that the frequency of each event in the set of all optimal reconciliations could be used as a support measure. We put this proposition to the test here and also consider a variant where the support measure is obtained by additionally accounting for suboptimal reconciliations. Experiments on simulated data show the relevance of event supports computed by both methods, while resorting to suboptimal sampling was shown to be more effective. Unfortunately, we also show that, unlike the majority-rule consensus tree for phylogenies, there is no guarantee that a single reconciliation can contain all events having above 50% support. In this paper, we detail how to rely on the reconciliation graph to efficiently identify the median reconciliation. Such median reconciliation can be found in polynomial time within the potentially exponential set of most parsimonious reconciliations. © 2013 Nguyen et al." 27 Jesper Jansson and Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In Journal of Discrete Algorithms, Vol. 25:66-78, 2014. Keywords: distance between networks, explicit network, from network, galled network, phylogenetic network, phylogeny, polynomial, triplet distance.         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(n2.687) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance between two galled trees 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 algorithmic results that may be of independent interest: (i) the number of triangles in a connected, undirected, uncolored graph with m edges can be computed in o(m1.408) time; (ii) if G is a connected, undirected, edge-colored graph with n vertices and C is a subset of the set of edge colors then the number of monochromatic triangles of G with colors in C can be computed in o(n2.687) time; and (iii) if G is a connected, undirected, edge-colored graph with n vertices and R is a binary relation on the colors that is computable in O(1) time then the number of R-chromatic triangles in G can be computed in o(n2.687) time. © 2013 Elsevier B.V. All rights reserved." 28 Sarah Bastkowski, Andreas Spillner and Vincent Moulton. Fishing for minimum evolution trees with Neighbor-Nets. In IPL, Vol. 114(1-2):3-18, 2014. Keywords: circular split system, from distances, NeighborNet, phylogeny, polynomial.         Toggle abstract "In evolutionary biology, biologists commonly use a phylogenetic tree to represent the evolutionary history of some set of species. A common approach taken to construct such a tree is to search through the space of all possible phylogenetic trees on the set so as to find one that optimizes some score function, such as the minimum evolution criterion. However, this is hampered by the fact that the space of phylogenetic trees is extremely large in general. Interestingly, an alternative approach, which has received somewhat less attention in the literature, is to instead search for trees within some set of bipartitions or splits of the set of species in question. Here we consider the problem of searching through a set of splits that is circular. Such sets can, for example, be generated by the NeighborNet algorithm for constructing phylogenetic networks. More specifically, we present an O(n4) time algorithm for finding an optimal minimum evolution tree in a circular set of splits on a set of species of size n. In addition, using simulations, we compare the performance of this algorithm when applied to NeighborNet output with that of FastME, a leading method for searching for minimum evolution trees in tree space. We find that, even though a circular set of splits represents just a tiny fraction of the total number of possible splits of a set, the trees obtained from circular sets compare quite favorably with those obtained with FastME, suggesting that the approach could warrant further investigation. © 2013 Elsevier B.V." 29 Andrew R. Francis and Mike Steel. Which phylogenetic networks are merely trees with additional arcs? In Systematic Biology, Vol. 64(5):768-777, 2015. Keywords: explicit network, phylogenetic network, phylogeny, polynomial, tree-based network. Note: http://arxiv.org/abs/1502.07045.         30 Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca and Taoyang Wu. Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. In ALG, Vol. 77(1):173-200, 2017. Keywords: explicit network, FPT, from binets, from subnetworks, from trinets, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1411.6804.         31 Magnus Bordewich and Charles Semple. Reticulation-visible networks. In Advances in Applied Mathematics, Vol. 78:114-141, 2016. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS16.pdf.         32 Marc Thuillard and Didier Fraix-Burnet. Phylogenetic Trees and Networks Reduce to Phylogenies on Binary States: Does It Furnish an Explanation to the Robustness of Phylogenetic Trees against Lateral Transfers? In Evolutionary Bioinformatics, Vol. 11:213-221, 2015. [Abstract] Keywords: circular split system, explicit network, from multistate characters, outerplanar, perfect, phylogenetic network, phylogeny, planar, polynomial, reconstruction, split. Note: http://dx.doi.org/10.4137%2FEBO.S28158.         33 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.         34 Juan Wang. A Metric on the Space of Partly Reduced Phylogenetic Networks. In BMRI, Vol. 2016(7534258):1-9, 2016. Keywords: distance between networks, partly reduced networks, phylogenetic network, phylogeny, polynomial, reduced networks. Note: http://downloads.hindawi.com/journals/bmri/aip/7534258.pdf.         35 Andreas Gunawan, Bhaskar DasGupta and Louxin Zhang. A decomposition theorem and two algorithms for reticulation-visible networks. In Information and Computation, Vol. 252:161-175, 2017. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: https://www.cs.uic.edu/~dasgupta/resume/publ/papers/Infor_Comput_IC4848_final.pdf.         36 Vincent Moulton, James Oldman and Taoyang Wu. A cubic-time algorithm for computing the trinet distance between level-1 networks. In IPL, Vol. 123:36-41, 2017. Keywords: distance between networks, explicit network, from network, phylogenetic network, phylogeny, polynomial, Program TriLoNet. Note: https://doi.org/10.1016/j.ipl.2017.03.002.         37 Magnus Bordewich, Charles Semple and Nihan Tokac. Constructing tree-child networks from distance matrices. In Algorithmica, Vol. 80(8):2240-2259, 2018. Keywords: compressed network, explicit network, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, tree-child network, uniqueness. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSN17.pdf.         38 Celine Scornavacca, Joan Carles Pons and Gabriel Cardona. Fast algorithm for the reconciliation of gene trees and LGT networks. In JTB, Vol. 418:129-137, 2017. Keywords: duplication, explicit network, from network, from rooted trees, lateral gene transfer, LGT network, loss, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.         39 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Solving the Tree Containment Problem in Linear Time for Nearly Stable Phylogenetic Networks. In DAM, Vol. 246:62-79, 2018. Keywords: explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01575001/en/.         40 Juan Wang and Maozu Guo. A Metric on the Space of kth-order reduced Phylogenetic Networks. In Scientific Reports, Vol. 7(3189):1-10, 2017. Keywords: distance between networks, explicit network, from network, kth-order reduced network, phylogenetic network, phylogeny, polynomial. Note: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5466651/.         41 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.         42 Edwin Jacox, Cédric Chauve, Gergely J. Szöllösi, Yann Ponty and Celine Scornavacca. EcceTERA: comprehensive gene tree-species tree reconciliation using parsimony. In BIO, Vol. 32(13):2056-2058, 2016. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, parsimony, phylogenetic network, phylogeny, polynomial, Program ecceTERA. Note: https://doi.org/10.1093/bioinformatics/btw105.         43 Andreas Gunawan, Hongwei Yan and Louxin Zhang. Compression of Phylogenetic Networks and Algorithm for the Tree Containment Problem. In JCB, Vol. 25(3), 2019. Keywords: explicit network, phylogenetic network, phylogeny, polynomial, quasi-reticulation-visible network, reticulation-visible network, tree containment, tree-child network. Note: https://arxiv.org/abs/1806.07625.         44 Momoko Hayamizu, Katharina Huber, Vincent Moulton and Yukihiro Murakami. Recognizing and realizing cactus metrics. In IPL, Vol. 157(105916):1-5, 2020. Keywords: cactus graph, from distances, level k phylogenetic network, optimal realization, polynomial. Note: https://doi.org/10.1016/j.ipl.2020.105916.

InProceedings

45 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." 46 Dan Gusfield and Vikas Bansal. A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In RECOMB05, Vol. 3500:217-232 of LNCS, springer, 2005. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, polynomial, recombination, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/gusfieldrecomb.pdf.         47 Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. In RECOMB01, Pages 141-148, 2001. Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, Program McKiTscH, reconstruction. Note: http://dx.doi.org/10.1145/369133.369188.         48 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.         49 Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 of LNCS, springer, 2008. Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction. Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.         Toggle abstract "Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE." 50 Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In ISAAC04, Vol. 3341:581-593 of LNCS, springer, 2005. Keywords: dynamic programming, MASN, nested network, NP complete, phylogenetic network, phylogeny, polynomial. Note: http://www.df.lth.se/~jj/Publications/nested7_ISAAC2004.pdf.         51 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.         52 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.         53 John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In SODA94, Pages 471-480, 1994. Keywords: from sequences, NP complete, polynomial, recombination, reconstruction. Note: http://portal.acm.org/citation.cfm?id=314626#.         54 Luay Nakhleh and Li-San Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919-926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.         55 Luay Nakhleh and Li-San Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:82-99 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.         56 Luay Nakhleh, Jerry Sun, Tandy Warnow, C. Randal Linder, Bernard M. E. Moret and Anna Tholse. Towards the Development of Computational Tools for Evaluating Phylogenetic Network Reconstruction Methods. In PSB03, 2003. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, polynomial, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/psb03.pdf.         57 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.         58 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.         59 Mike Hallett, Jens Lagergren and Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347-356, 2004. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.nada.kth.se/~jensl/p164-hallett.pdf.         60 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.         61 Daniel H. Huson and Regula Rupp. Summarizing Multiple Gene Trees Using Cluster Networks. In WABI08, Vol. 5251:296-305 of LNCS, springer, 2008. Keywords: abstract network, from clusters, from rooted trees, phylogenetic network, phylogeny, polynomial, Program Dendroscope. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_25, slides from the MIEP Conference available at http://www.lirmm.fr/MIEP08/slides/11_13_rupp.pdf.         Toggle abstract "The result of a multiple gene tree analysis is usually a number of different tree topologies that are each supported by a significant proportion of the genes. We introduce the concept of a cluster network that can be used to combine such trees into a single rooted network, which can be drawn either as a cladogram or phylogram. In contrast to split networks, which can grow exponentially in the size of the input, cluster networks grow only quadratically. A cluster network is easily computed using a modification of the tree-popping algorithm, which we call network-popping. The approach has been implemented as part of the Dendroscope tree-drawing program and its application is illustrated using data and results from three recent studies on large numbers of gene trees. © 2008 Springer-Verlag Berlin Heidelberg." 62 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Phylogenetic Networks: Justification, Models, Distances and Algorithms. In VI Jornadas de Matemática Discreta y Algorítmica (JMDA'08), 2008. Keywords: distance between networks, mu distance, phylogenetic network, phylogeny, polynomial, survey, time consistent network, tree-child network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_61-1.pdf.         63 Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316-325, 2004. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.pdf.         64 Pawel Górecki. Single step reconciliation algorithm for duplication, loss and horizontal gene transfer model. In ECCB03, 2003. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inra.fr/eccb2003/posters/pdf/short/S_gorecki.ps.         65 Thu-Hien To and Michel Habib. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time. In CPM09, (5577):275-288, springer, 2009. Keywords: explicit network, from triplets, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/0901.1657.         Toggle abstract "For a given dense triplet set Τ there exist two natural questions [7]: Does there exist any phylogenetic network consistent with Τ? In case such networks exist, can we find an effective algorithm to construct one? For cases of networks of levels k = 0, 1 or 2, these questions were answered in [1,6,7,8,10] with effective polynomial algorithms. For higher levels k, partial answers were recently obtained in [11] with an O(/Τ/k+1)time algorithm for simple networks. In this paper, we give a complete answer to the general case, solving a problem proposed in [7]. The main idea of our proof is to use a special property of SN-sets in a level-k network. As a consequence, for any fixed k, we can also find a level-k network with the minimum number of reticulations, if one exists, in polynomial time. © 2009 Springer Berlin Heidelberg." 66 Daniel H. Huson, Regula Rupp, Vincent Berry, Philippe Gambette and Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009. Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.         Toggle abstract "Motivation: Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. Results: In this article, we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves successively solving instances of two different NP-complete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. © 2009 The Author(s)." 67 Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara and Gabriel Valiente. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks. In CPM10, Vol. 6129:190-201 of LNCS, springer, 2010. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread. Note: http://hdl.handle.net/10119/9859, slides available at http://cs.nyu.edu/parida/CPM2010/MainPage_files/18.pdf.         Toggle abstract "The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2 with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time. © Springer-Verlag Berlin Heidelberg 2010." 68 Jean-Philippe Doyon, Celine Scornavacca, Konstantin Yu Gorbunov, Gergely J. Szöllösi, Vincent Ranwez and Vincent Berry. An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications, and transfers. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'10), Vol. 6398:93-108 of LNCS, springer, 2011. Keywords: branch length, duplication, dynamic programming, explicit network, from multilabeled tree, from species tree, from unrooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Mowgli, reconstruction. Note: http://www.lirmm.fr/~vberry/Publis/MPR-DoyonEtAl.pdf, software available at http://www.atgc-montpellier.fr/MPR/.         Toggle abstract "Tree reconciliation methods aim at estimating the evolutionary events that cause discrepancy between gene trees and species trees. We provide a discrete computational model that considers duplications, transfers and losses of genes. The model yields a fast and exact algorithm to infer time consistent and most parsimonious reconciliations. Then we study the conditions under which parsimony is able to accurately infer such events. Overall, it performs well even under realistic rates, transfers being in general less accurately recovered than duplications. An implementation is freely available at http://www.atgc- montpellier.fr/MPR. © 2010 Springer-Verlag." 69 Mukul S. Bansal, J. Peter Gogarten and Ron Shamir. Detecting Highways of Horizontal Gene Transfer. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'10), Vol. 6398:109-120 of LNCS, springer, 2011. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.cs.iastate.edu/~bansal/Highways_RCG10.pdf.         Toggle abstract "In a horizontal gene transfer (HGT) event a gene is transferred between two species that do not share an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species, our method requires O(n 4) time, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method. © 2010 Springer-Verlag." 70 Vincent Berry and David Bryant. Faster reliable phylogenetic analysis. In RECOMB99, Pages 59-68, 1999. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, polynomial, Program SplitsTree, reconstruction, split network, weakly compatible. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9151.         71 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." 72 Mukul S. Bansal, Eric J. Alm and Manolis Kellis. Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss. In RECOMB13, Vol. 7821:1-13 of LNCS, springer, 2013. Keywords: duplication, from rooted trees, from species tree, loss, phylogenetic network, phylogeny, polynomial, Program RANGER-DTL, reconstruction. Note: http://people.csail.mit.edu/mukul/Bansal_RECOMB2013.pdf.         Toggle abstract "Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While Duplication-Loss (DL) reconciliation leads to a unique maximum-parsimony solution, Duplication-Transfer-Loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult the infer the true evolutionary history of the gene family. Here, we present an effective, efficient, and scalable method for dealing with this fundamental problem in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn 2) time, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mapping and event assignments, and to investigate the impact of varying event costs. © 2013 Springer-Verlag." 73 Hoa Vu, Francis Chin, Wing-Kai Hon, Henry Leung, Kunihiko Sadakane, Wing-Kin Sung and Siu-Ming Yiu. Reconstructing k-Reticulated Phylogenetic Network from a Set of Gene Trees. In ISBRA13, Vol. 7875:112-124 of LNCS, springer, 2013. Keywords: from rooted trees, k-reticulated, phylogenetic network, phylogeny, polynomial, Program ARTNET, Program CMPT, reconstruction. Note: http://grid.cs.gsu.edu/~xguo9/publications/2013_Cloud%20computing%20for%20de%20novo%20metagenomic%20sequence%20assembly.pdf#page=123.         Toggle abstract "The time complexity of existing algorithms for reconstructing a level-x phylogenetic network increases exponentially in x. In this paper, we propose a new classification of phylogenetic networks called k-reticulated network. A k-reticulated network can model all level-k networks and some level-x networks with x > k. We design algorithms for reconstructing k-reticulated network (k = 1 or 2) with minimum number of hybrid nodes from a set of m binary trees, each with n leaves in O(mn 2) time. The implication is that some level-x networks with x > k can now be reconstructed in a faster way. We implemented our algorithm (ARTNET) and compared it with CMPT. We show that ARTNET outperforms CMPT in terms of running time and accuracy. We also consider the case when there does not exist a 2-reticulated network for the input trees. We present an algorithm computing a maximum subset of the species set so that a new set of subtrees can be combined into a 2-reticulated network. © 2013 Springer-Verlag." 74 Ran Libeskind-Hadas, Yi-Chieh Wu, Mukul S. Bansal and Manolis Kellis. Pareto-optimal phylogenetic tree reconciliation. In ISMB14, Vol. 30:i87-i95 of BIO, 2014. Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Xscape, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btu289.         Toggle abstract "Motivation: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem. Results: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies. © 2014 The Author. Published by Oxford University Press. All rights reserved." 75 Louxin Zhang, Yen Kaow Ng, Taoyang Wu and Yu Zheng. Network model and efficient method for detecting relative duplications or horizontal gene transfers. In ICCABS11, Pages 214-219, 2011. Keywords: dynamic programming, explicit network, from network, from rooted trees, from species tree, phylogenetic network, phylogeny, polynomial, reconstruction.         Toggle abstract "Background: Horizontal gene transfer and gene duplication are two significant forces behind genome evolution. As more and more well-supported examples of HGTs are being revealed, there is a growing awareness that HGT is more widespread than previously thought, occurring often not only within bacteria, but also between species remotely related such as bacteria and plants or plants and animals. Although a substantial number of genomic sequences are known, HGT inference remains challenging. Parsimony-based inferences of HGT events are typically NP-hard under the framework of gene tree and species tree comparison; it is even more timeconsuming if the maximum likelihood approach is used. The fact that gene tree and species tree incongruence can be further confounded by gene duplication and gene loss events motivates us to incorporate considerations for these events into our inference of HGT events. Similarly, it will be beneficial if known HGT events are considered in the inference of gene duplications and gene losses. © 2011 IEEE." 76 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Locating a Tree in A Phylogenetic Network in Quadratic Time. In RECOMB15, Vol. 9029:96-107 of LNCS, Springer, 2015. Keywords: evaluation, explicit network, from network, from rooted trees, genetically stable network, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal.archives-ouvertes.fr/hal-01116231/en.         77 Jittat Fakcharoenphol, Tanee Kumpijit and Attakorn Putwattana. A Faster Algorithm for the Tree Containment Problem for Binary Nearly Stable Phylogenetic Networks. In Proceedings of the The 12th International Joint Conference on Computer Science and Software Engineering (JCSSE'15), Pages 337-342, IEEE, 2015. Keywords: dynamic programming, explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment.         78 Andreas Gunawan, Bhaskar DasGupta and Louxin Zhang. Locating a Tree in a Reticulation-Visible Network in Cubic Time. In RECOMB16, Vol. 9649:266 of LNBI, Springer, 2016. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: http://arxiv.org/abs/1507.02119.         79 Philippe Gambette, Andreas Gunawan, Anthony Labarre, Stéphane Vialette and Louxin Zhang. Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. In IWOCA15, Vol. 9538:197-208 of LNCS, springer, 2016. Keywords: explicit network, from network, from rooted trees, genetically stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01226035 .         80 Thu-Hien To and Celine Scornavacca. Efficient algorithms for reconciling gene trees and species networks via duplication and loss events. In RECOMB-CG15, Vol. 16(Suppl 10)(S6):1-14 of BMC Genomics, BioMed Central, 2015. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://dx.doi.org/10.1186/1471-2164-16-S10-S6.         81 Mathias Weller. Linear-Time Tree Containment in Phylogenetic Networks. In RECOMB-CG18, Vol. 11183:309-323 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, reconstruction, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.06364.         82 Jesper Jansson, Ramesh Rajaby and Wing-Kin Sung. An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees. In AlCoB17, Vol. 10252:115-126 of LNCS, Springer, 2017. Keywords: distance between networks, from network, phylogenetic network, phylogeny, polynomial, reconstruction, triplet distance. Note: .         83 Andreas Gunawan. Solving the Tree Containment Problem for Reticulation-visible Networks in Linear Time. In AlCoB18, Vol. 10849:24-36 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.04088.         84 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.         85 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.         86 Leo van Iersel, Remie Janssen, Mark Jones, Yukihiro Murakami and Norbert Zeh. Polynomial-Time Algorithms for Phylogenetic Inference Problems. In AlCoB18, Vol. 10849:37-49 of LNCS, Springer, 2018. Keywords: hybridization, minimum number, parental hybridization, phylogenetic network, phylogeny, polynomial, reconstruction, weakly displaying. Note: https://research.tudelft.nl/files/53686721/10.1007_978_3_319_91938_6_4.pdf.         87 Remie Janssen and Yukihiro Murakami. Linear Time Algorithm for Tree-Child Network Containment. In AlCoB20, Vol. 12099:93-107 of LNCS, Springer, 2020. Keywords: explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, reconstruction, tree-child network, tree-child sequence. Note: https://doi.org/10.1007/978-3-030-42266-0_8.         88 Jesper Jansson, Konstantinos Mampentzidis, Ramesh Rajaby and Wing-Kin Sung. Computing the Rooted Triplet Distance Between Phylogenetic Networks. In IWOCA19, Vol. 11638:290-303 of LNCS, Springer, 2019. Keywords: distance between networks, from network, phylogenetic network, phylogeny, polynomial, triplet distance.

InBook

89 Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In Oleg N. Terikhovsky and William N. Burton editors, New Topics in Theoretical Computer Science, Pages 119-141, Nova Publishers, 2008. Keywords: dynamic programming, MASN, nested network, phylogenetic network, phylogeny, polynomial. Note: http://www.df.lth.se/~jj/Publications/nested12_NTTCS2008_corrected.pdf.         90 Louxin Zhang. Clusters, Trees, and Phylogenetic Network Classes. In Tandy Warnow editor, Bioinformatics and Phylogenetics. Seminal Contributions of Bernard Moret, Vol. 29:277-315 of Computational Biology, Springer, 2019. Keywords: cluster containment, explicit network, phylogenetic network, phylogeny, polynomial, tree containment.

MastersThesis

91 Derek Ruths. Applications of phylogenetic incongruence to detecting and reconstructing interspecific recombination and horizontal gene transfer. Master's thesis, Rice University, U.S.A., 2005. Keywords: explicit network, from rooted trees, from species tree, heuristic, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://hdl.handle.net/1911/17912.         92 Adrià Alcalà Mena. Trivalent Graph isomorphism in polynomial time. Master's thesis, Universidad de Cantabria, Spain, 2012. Keywords: distance between networks, explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, Program SAGE. Note: http://arxiv.org/abs/1209.1040.         93 Julia Matsieva. A Static Formulation of the History Bound Problem. Master's thesis, UC Davis, 2014. Keywords: bound, dynamic programming, explicit network, from binary characters, from clusters, phylogenetic network, phylogeny, polynomial. Note: https://escholarship.org/uc/item/3741t064.

PhdThesis

94 Pawel Górecki. Detection of horizontal gene transfer. PhD thesis, Warsaw University, Poland, 2006. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.         95 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.         96 Thu-Hien To. On some graph problems in phylogenetics. PhD thesis, Université Paris Diderot - Paris 7, France, 2011. Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.liafa.jussieu.fr/~toth/thesis.pdf.         97 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.         98 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.         99 Konstantinos Mampentzidis. Comparison and Construction of Phylogenetic Trees and Networks. PhD thesis, Aarhus University, Denmark, 2019. Keywords: distance between networks, explicit network, from network, phylogenetic network, phylogeny, polynomial, triplet distance. Note: https://pure.au.dk/ws/files/172250681/thesis_Konstantinos_Mampentzidis.pdf.

Misc

100 Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. 2004. Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, reconstruction. Note: submitted to SIAM Journal on Computing, http://www.mcb.mcgill.ca/~hallett/Lateral.pdf.         101 Leo van Iersel and Steven Kelk. A short note on the tractability of constructing phylogenetic networks from clusters. 2009. Keywords: from clusters, from triplets, level k phylogenetic network, phylogenetic network, polynomial, reconstruction. Note: http://arxiv.org/abs/0912.4502.         102 Adrià Alcalà Mena and Francesc Rosselló. Ternary graph isomorphism in polynomial time, after Luks. 2012. Keywords: distance between networks, explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, Program SAGE. Note: http://arxiv.org/abs/1209.0871.         103 Willem Sonke. Reconstructing a level-1-network from quartets. 2013. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, polynomial, Program Fylogenetica, reconstruction, software, visualization. Note: http://alexandria.tue.nl/extra1/afstversl/wsk-i/sonke2013.pdf.         104 Benjamin Albrecht. Computing Hybridization Networks for Multiple Rooted Binary Phylogenetic Trees by Maximum Acyclic Agreement Forests. 2014. Keywords: agreement forest, from rooted trees, minimum number, phylogenetic network, phylogeny, polynomial, Program Hybroscale, reconstruction. Note: http://arxiv.org/abs/1408.3044.         105 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.         106 Jonathan Klawitter and Peter Stumpf. Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings. 2020. Keywords: explicit network, FPT, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, visualization. Note: https://arxiv.org/abs/2008.08960.