
Leo van Iersel,
Remie Janssen,
Mark Jones,
Yukihiro Murakami and
Norbert Zeh. PolynomialTime Algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation. In TCBB, Vol. 17(1):1426, 2020. Keywords: hybridization, minimum number, parental hybridization, phylogenetic network, phylogeny, reconstruction, weakly displaying. Note: http://pure.tudelft.nl/ws/portalfiles/portal/71270795/08798653.pdf.









Julia Matsieva,
Steven Kelk,
Celine Scornavacca,
Chris Whidden and
Dan Gusfield. A Resolution of the Static Formulation Question for the Problem of Computing the History Bound. In TCBB, Vol. 14(2):404417, 2017. Keywords: ARG, explicit network, from sequences, minimum number, phylogenetic network, phylogeny.



Misagh Kordi and
Mukul S. Bansal. On the Complexity of DuplicationTransferLoss Reconciliation with NonBinary Gene Trees. In TCBB, Vol. 14(3):587599, 2017. Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://compbio.engr.uconn.edu/papers/Kordi_DTLreconciliationPreprint2015.pdf.



Sajad Mirzaei and
Yufeng Wu. Fast Construction of Near Parsimonious Hybridization Networks for Multiple Phylogenetic Trees. In TCBB, Vol. 13(3):565570, 2016. Keywords: bound, explicit network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program PIRN, reconstruction, software. Note: http://www.engr.uconn.edu/~ywu/Papers/PIRNspreprint.pdf.



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. The comparison of treesibling time consistent phylogenetic networks is graphisomorphism complete. In The Scientific World Journal, Vol. 2014(254279):16, 2014. Keywords: abstract network, distance between networks, from network, isomorphism, phylogenetic network, tree sibling network. Note: http://arxiv.org/abs/0902.4640.
Toggle abstract
"Several polynomial time computable metrics on the class of semibinary treesibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic treesibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all treesibling time consistent phylogenetic networks that can be computed in polynomial time. © 2014 Gabriel Cardona et al."



Anthony Labarre and
Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. In TCBB, Vol. 11(2):389397, 2014. Keywords: abstract network, from unrooted trees, heuristic, NP complete, phylogenetic network, phylogeny, reconstruction. Note: https://halupecupem.archivesouvertes.fr/hal00855669.
Toggle abstract
"Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of t partially labelled trees. Although algorithms have been proposed for solving that problem on two graphs, the complexity of the general problem on trees remains unknown. In this paper, we show that the corresponding decision problem is NPcomplete for t=3. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the idpsystem, and assess the performance of both methods on randomly generated data. © 20042012 IEEE."





Adrià Alcalà Mena,
Mercè Llabrés,
Francesc Rosselló and
Pau Rullan. TreeChild Cluster Networks. In Fundamenta Informaticae, Vol. 134(12):115, 2014. Keywords: explicit network, from clusters, phylogenetic network, phylogeny, Program PhyloNetwork, reconstruction, treechild network.



Stefan Grünewald,
Andreas Spillner,
Sarah Bastkowski,
Anja Bögershausen and
Vincent Moulton. SuperQ: Computing Supernetworks from Quartets. In TCBB, Vol. 10(1):151160, 2013. Keywords: abstract network, circular split system, from quartets, heuristic, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, Program SuperQ, software, split network.
Toggle abstract
"Supertrees are a commonly used tool in phylogenetics to summarize collections of partial phylogenetic trees. As a generalization of supertrees, phylogenetic supernetworks allow, in addition, the visual representation of conflict between the trees that is not possible to observe with a single tree. Here, we introduce SuperQ, a new method for constructing such supernetworks (SuperQ is freely available at >www.uea.ac.uk/computing/superq.). It works by first breaking the input trees into quartet trees, and then stitching these together to form a special kind of phylogenetic network, called a split network. This stitching process is performed using an adaptation of the QNet method for split network reconstruction employing a novel approach to use the branch lengths from the input trees to estimate the branch lengths in the resulting network. Compared with previous supernetwork methods, SuperQ has the advantage of producing a planar network. We compare the performance of SuperQ to the Zclosure and Qimputation supernetwork methods, and also present an analysis of some published data sets as an illustration of its applicability. © 20042012 IEEE."



Teresa Piovesan and
Steven Kelk. A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees. In TCBB, Vol. 10(1):1825, 2013. Keywords: FPT, from rooted trees, phylogenetic network, phylogeny, Program TerminusEst, reconstruction. Note: http://arxiv.org/abs/1207.6090.
Toggle abstract
"Here, we present a new fixed parameter tractable algorithm to compute the hybridization number (r) of two rooted, not necessarily binary phylogenetic trees on taxon set (X) in time ((6r r) · poly(n)), where (n= X). The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on (X), and several insights from the softwired clusters literature. This yields a surprisingly simple and practical boundedsearch algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem. © 20042012 IEEE."



Hoa Vu,
Francis Chin,
WingKai Hon,
Henry Leung,
Kunihiko Sadakane,
WingKin Sung and
SiuMing Yiu. Reconstructing kReticulated Phylogenetic Network from a Set of Gene Trees. In ISBRA13, Vol. 7875:112124 of LNCS, springer, 2013. Keywords: from rooted trees, kreticulated, 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 levelx phylogenetic network increases exponentially in x. In this paper, we propose a new classification of phylogenetic networks called kreticulated network. A kreticulated network can model all levelk networks and some levelx networks with x > k. We design algorithms for reconstructing kreticulated 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 levelx 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 2reticulated 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 2reticulated network. © 2013 SpringerVerlag."





Stephen J. Willson. CSD Homomorphisms Between Phylogenetic Networks. In TCBB, Vol. 9(4), 2012. Keywords: explicit network, from network, from quartets, phylogenetic network. Note: http://www.public.iastate.edu/~swillson/Relationships11IEEE.pdf, preliminary version entitled Relationships Among Phylogenetic Networks.
Toggle abstract
"Since Darwin, species trees have been used as a simplified description of the relationships which summarize the complicated network N of reality. Recent evidence of hybridization and lateral gene transfer, however, suggest that there are situations where trees are inadequate. Consequently it is important to determine properties that characterize networks closely related to N and possibly more complicated than trees but lacking the full complexity of N. A connected surjective digraph map (CSD) is a map f from one network N to another network M such that every arc is either collapsed to a single vertex or is taken to an arc, such that f is surjective, and such that the inverse image of a vertex is always connected. CSD maps are shown to behave well under composition. It is proved that if there is a CSD map from N to M, then there is a way to lift an undirected version of M into N, often with added resolution. A CSD map from N to M puts strong constraints on N. In general, it may be useful to study classes of networks such that, for any N, there exists a CSD map from N to some standard member of that class. © 2012 IEEE."



Steven Kelk,
Celine Scornavacca and
Leo van Iersel. On the elusiveness of clusters. In TCBB, Vol. 9(2):517534, 2012. Keywords: explicit network, from clusters, from rooted trees, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, Program Clustistic, reconstruction, software. Note: http://arxiv.org/abs/1103.1834.



Andreas Spillner,
Binh T. Nguyen and
Vincent Moulton. Constructing and Drawing Regular Planar Split Networks. In TCBB, Vol. 9(2):395407, 2012. Keywords: abstract network, from splits, phylogenetic network, phylogeny, reconstruction, visualization. Note: slides and presentation available at http://www.newton.ac.uk/programmes/PLG/seminars/062111501.html.
Toggle abstract
"Split networks are commonly used to visualize collections of bipartitions, also called splits, of a finite set. Such collections arise, for example, in evolutionary studies. Split networks can be viewed as a generalization of phylogenetic trees and may be generated using the SplitsTree package. Recently, the NeighborNet method for generating split networks has become rather popular, in part because it is guaranteed to always generate a circular split system, which can always be displayed by a planar split network. Even so, labels must be placed on the "outside" of the network, which might be problematic in some applications. To help circumvent this problem, it can be helpful to consider socalled flat split systems, which can be displayed by planar split networks where labels are allowed on the inside of the network too. Here, we present a new algorithm that is guaranteed to compute a minimal planar split network displaying a flat split system in polynomial time, provided the split system is given in a certain format. We will also briefly discuss two heuristics that could be useful for analyzing phylogeographic data and that allow the computation of flat split systems in this format in polynomial time. © 2006 IEEE."



Paul Phipps and
Sergey Bereg. Optimizing Phylogenetic Networks for Circular Split Systems. In TCBB, Vol. 9(2):535547, 2012. Keywords: abstract network, from distances, from splits, phylogenetic network, phylogeny, Program PhippsNetwork, reconstruction, software.
Toggle abstract
"We address the problem of realizing a given distance matrix by a planar phylogenetic network with a minimum number of faces. With the help of the popular software SplitsTree4, we start by approximating the distance matrix with a distance metric that is a linear combination of circular splits. The main results of this paper are the necessary and sufficient conditions for the existence of a network with a single face. We show how such a network can be constructed, and we present a heuristic for constructing a network with few faces using the first algorithm as the base case. Experimental results on biological data show that this heuristic algorithm can produce phylogenetic networks with far fewer faces than the ones computed by SplitsTree4, without affecting the approximation of the distance matrix. © 2012 IEEE."



ZhiZhong Chen and
Lusheng Wang. Algorithms for Reticulate Networks of Multiple Phylogenetic Trees. In TCBB, Vol. 9(2):372384, 2012. Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program CMPT, Program MaafB, reconstruction, software. Note: http://rnc.r.dendai.ac.jp/~chen/papers/rMaaf.pdf.
Toggle abstract
"A reticulate network N of multiple phylogenetic trees may have nodes with two or more parents (called reticulation nodes). There are two ways to define the reticulation number of N. One way is to define it as the number of reticulation nodes in N in this case, a reticulate network with the smallest reticulation number is called an optimal typeI reticulate network of the trees. The better way is to define it as the total number of parents of reticulation nodes in N minus the number of reticulation nodes in N ; in this case, a reticulate network with the smallest reticulation number is called an optimal typeII reticulate network of the trees. In this paper, we first present a fast fixedparameter algorithm for constructing one or all optimal typeI reticulate networks of multiple phylogenetic trees. We then use the algorithm together with other ideas to obtain an algorithm for estimating a lower bound on the reticulation number of an optimal typeII reticulate network of the input trees. To our knowledge, these are the first fixedparameter algorithms for the problems. We have implemented the algorithms in ANSI C, obtaining programs CMPT and MaafB. Our experimental data show that CMPT can construct optimal typeI reticulate networks rapidly and MaafB can compute better lower bounds for optimal typeII reticulate networks within shorter time than the previously best program PIRN designed by Wu. © 2006 IEEE."



ZhiZhong Chen,
Fei Deng and
Lusheng Wang. Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers. In TCBB, Vol. 9(5):15151528, 2012. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.cityu.edu.hk/~lwang/research/tcbb2012c.pdf.
Toggle abstract
"We give a fixedparameter algorithm for the problem of enumerating all minimumcost LCAreconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m+3 k/c n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCAreconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m+2.78 k/cn). © 20042012 IEEE."



Ali Tofigh,
Mike Hallett and
Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.
Toggle abstract
"The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where socalled DTLscenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTLscenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTLscenarios is NPhard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixedparameter tractable algorithm for finding most parsimonious DTLscenarios. © 2011 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Comparison of Galled Trees. In TCBB, Vol. 8(2):410427, 2011. Note: http://arxiv.org/abs/0906.1166.
Toggle abstract
"Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomialtime algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods. © 2011 IEEE."



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



Luay Nakhleh. A Metric on the Space of Reduced Phylogenetic Networks. In TCBB, Vol. 7(2), 2010. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbbMetric.pdf.
Toggle abstract
"Phylogenetic networks are leaflabeled, rooted, acyclic, and directed graphs that are used to model reticulate evolutionary histories. Several measures for quantifying the topological dissimilarity between two phylogenetic networks have been devised, each of which was proven to be a metric on certain restricted classes of phylogenetic networks. A biologically motivated class of phylogenetic networks, namely, reduced phylogenetic networks, was recently introduced. None of the existing measures is a metric on the space of reduced phylogenetic networks. In this paper, we provide a metric on the space of reduced phylogenetic networks that is computable in time polynomial in the size of the networks. © 2006 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Path lengths in treechild time consistent hybridization networks. In Information Sciences, Vol. 180(3):366383, 2010. Keywords: distance between networks, phylogenetic network, phylogeny, time consistent network, treechild network. Note: http://arxiv.org/abs/0807.0087?context=cs.CE.
Toggle abstract
"Hybridization networks are representations of evolutionary histories that allow for the inclusion of reticulate events like recombinations, hybridizations, or lateral gene transfers. The recent growth in the number of hybridization network reconstruction algorithms has led to an increasing interest in the definition of metrics for their comparison that can be used to assess the accuracy or robustness of these methods. In this paper we establish some basic results that make it possible the generalization to treechild time consistent (TCTC) hybridization networks of some of the oldest known metrics for phylogenetic trees: those based on the comparison of the vectors of path lengths between leaves. More specifically, we associate to each hybridization network a suitably defined vector of 'splitted' path lengths between its leaves, and we prove that if two TCTC hybridization networks have the same such vectors, then they must be isomorphic. Thus, comparing these vectors by means of a metric for realvalued vectors defines a metric for TCTC hybridization networks. We also consider the case of fully resolved hybridization networks, where we prove that simpler, 'nonsplitted' vectors can be used. © 2009 Elsevier Inc. All rights reserved."



Stephen J. Willson. Regular Networks Can Be Uniquely Constructed from Their Trees. In TCBB, Vol. 8(3):785796, 2010. Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction, regular network. Note: http://www.public.iastate.edu/~swillson/RegularNetsFromTrees5.pdf.
Toggle abstract
"A rooted acyclic digraph N with labeled leaves displays a tree T when there exists a way to select a unique parent of each hybrid vertex resulting in the tree T. Let Tr(N) denote the set of all trees displayed by the network N. In general, there may be many other networks M, such that Tr(M) = Tr(N). A network is regular if it is isomorphic with its cover digraph. If N is regular and D is a collection of trees displayed by N, this paper studies some procedures to try to reconstruct N given D. If the input is D=Tr(N), one procedure is described, which will reconstruct N. Hence, if N and M are regular networks and Tr(N) = Tr(M), it follows that N = M, proving that a regular network is uniquely determined by its displayed trees. If D is a (usually very much smaller) collection of displayed trees that satisfies certain hypotheses, modifications of the procedure will still reconstruct N given D. © 2011 IEEE."









Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. Comparison of treechild phylogenetic networks. In TCBB, Vol. 6(4):552569, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Bio PhyloNetwork, Program PhyloNetwork, tree sibling network, treechild network. Note: http://arxiv.org/abs/0708.3499.
Toggle abstract
"Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a wellfounded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called treechild phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the wellknown RobinsonFoulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a treechild phylogenetic network from its path multiplicity vectors, for computing the distance between two treechild phylogenetic networks and for aligning a pair of treechild phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/ phylonetworks/mudistance/. © 2009 IEEE."



Daniel H. Huson. Drawing Rooted Phylogenetic Networks. In TCBB, Vol. 6(1):103109, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, visualization. Note: http://dx.doi.org/10.1109/TCBB.2008.58.
Toggle abstract
"The evolutionary history of a collection of species is usually represented by a phylogenetic tree. Sometimes, phylogenetic networks are used as a means of representing reticulate evolution or of showing uncertainty and incompatibilities in evolutionary datasets. This is often done using unrooted phylogenetic networks such as split networks, due in part, to the availability of software (SplitsTree) for their computation and visualization. In this paper we discuss the problem of drawing rooted phylogenetic networks as cladograms or phylograms in a number of different views that are commonly used for rooted trees. Implementations of the algorithms are available in new releases of the Dendroscope and SplitsTree programs. © 2006 IEEE."





Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Metrics for phylogenetic networks I: Generalizations of the RobinsonFoulds metric. In TCBB, Vol. 6(1):4661, 2009. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, time consistent network, treechild network, tripartition distance. Note: http://dx.doi.org/10.1109/TCBB.2008.70.
Toggle abstract
"The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the first in a series of papers devoted to the analysis and comparison of metrics for treechild time consistent phylogenetic networks on the same set of taxa. In this paper, we study three metrics that have already been introduced in the literature: the RobinsonFoulds distance, the tripartitions distance and the $mu$distance. They generalize to networks the classical RobinsonFoulds or partition distance for phylogenetic trees. We analyze the behavior of these metrics by studying their least and largest values and when they achieve them. As a byproduct of this study, we obtain tight bounds on the size of a treechild time consistent phylogenetic network. © 2006 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Metrics for phylogenetic networks II: Nodal and triplets metrics. In TCBB, Vol. 6(3):454469, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1109/TCBB.2008.127.
Toggle abstract
"The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second in a series of papers devoted to the analysis and comparison of metrics for treechild time consistent phylogenetic networks on the same set of taxa. In this paper, we generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of treechild time consistent phylogenetic networks by induction, but also to generate all treechild time consistent phylogenetic networks with a given number of leaves. © 2009 IEEE."



Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. On Nakhleh's metric for reduced phylogenetic networks. In TCBB, Vol. 6(4):629638, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: Preliminary versions: http://arxiv.org/abs/0809.0110 and http://arxiv.org/abs/0801.2354v1.
Toggle abstract
"We prove that Nakhleh's metric for reduced phylogenetic networks is also a metric on the classes of treechild phylogenetic networks, semibinary treesibling time consistent phylogenetic networks, and multilabeled phylogenetic trees. We also prove that it separates distinguishable phylogenetic networks. In this way, it becomes the strongest dissimilarity measure for phylogenetic networks available so far. Furthermore, we propose a generalization of that metric that separates arbitrary phylogenetic networks. © 2009 IEEE."







Bui Quang Minh,
Fabio Pardi,
Steffen Klaere and
Arndt von Haeseler. Budgeted Phylogenetic Diversity on Circular Split Systems. In TCBB, Vol. 6(1):2229, 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."



Philippe Gambette and
Daniel H. Huson. Improved Layout of Phylogenetic Networks. In TCBB, Vol. 5(3):472479, 2008. Keywords: abstract network, heuristic, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://hallirmm.ccsd.cnrs.fr/lirmm00309694/en/.
Toggle abstract
"Split networks are increasingly being used in phylogenetic analysis. Usually, a simple equalangle algorithm is used to draw such networks, producing layouts that leave much room for improvement. Addressing the problem of producing better layouts of split networks, this paper presents an algorithm for maximizing the area covered by the network, describes an extension of the equaldaylight algorithm to networks, looks into using a spring embedder, and discusses how to construct rooted split networks. © 2008 IEEE."



Leo van Iersel,
Judith Keijsper,
Steven Kelk,
Leen Stougie,
Ferry Hagen and
Teun Boekhout. Constructing level2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450462 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 level1 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 level2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontreelike. This further strengthens the case for the use of tripletbased methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE."



Andreas Spillner,
Binh T. Nguyen and
Vincent Moulton. Computing phylogenetic diversity for split systems. In TCBB, Vol. 5(2):235244, 2008. Keywords: abstract network, diversity, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1109/TCBB.2007.70260, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0906/spillner/.
Toggle abstract
"In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size $n$. We show that for general split systems this problem is NPhard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal $O(n)$ time algorithm for phylogenetic trees and an $O(nlog n + n k)$ time algorithm for choosing an optimal subset of size $k$ relative to a circular split system. © 2006 IEEE."





Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. A Distance Metric for a Class of TreeSibling Phylogenetic Networks. In BIO, Vol. 24(13):14811488, 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 nonextant 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 semibinary treesibling time consistent phylogenetic networks, which generalize treechild time consistent phylogenetic networks, and thus also galledtrees. The practical interest of this distance measure is 2fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomialtime algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)."



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, treechild network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_611.pdf.





Cam Thach Nguyen,
Nguyen Bao Nguyen,
WingKin Sung and
Louxin Zhang. Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem. In TCBB, Vol. 4(3):394402, 2007. Keywords: explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.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.



Sergey Bereg and
Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In TCBB, Vol. 3(4), 2006. Note: http://www.utdallas.edu/~yzhang/Homepage/Papers/preptcbb.pdf.
Toggle abstract
A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The ultrametric condition is very restrictive. In this paper we study phylogenetic networks that can be constructed assuming the molecular clock hypothesis. We characterize distance matrices that admit such networks for 3 and 4 taxa. We also design two algorithms for constructing networks optimizing the leastsquares fit.











Vineet Bafna and
Vikas Bansal. The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds. In TCBB, Vol. 1(2):7890, 2004. Keywords: ARG, bound, minimum number, phylogeny, recombination. Note: http://wwwcse.ucsd.edu/users/vbafna/pub/tcbb04.pdf.
Toggle abstract
"We consider the following problem: Given a set of binary sequences, determine lower bounds on the minimum number of recombinations required to explain the history of the sample, under the infinitesites model of mutation. The problem has implications for finding recombination hotspots and for the Ancestral Recombination Graph reconstruction problem. Hudson and Kaplan gave a lower bound based on the fourgamete test. In practice, their bound R m often greatly underestimates the minimum number of recombinations. The problem was recently revisited by Myers and Griffiths, who introduced two new lower bounds R h and R s which are provably better, and also yield good bounds in practice. However, the worstcase complexities of their procedures for computing R h and R s are exponential and superexponential, respectively. In this paper, we show that the number of nontrivial connected components, Rc, in the conflict graph for a given set of sequences, computable in time O(nm 2), is also a lower bound on the minimum number of recombination events. We show that in many cases, R c is a better bound than R h. The conflict graph was used by Gusfield et al. to obtain a polynomial time algorithm for the galled tree problem, which is a special case of the Ancestral Recombination Graph (ARG) reconstruction problem. Our results also offer some insight into the structural properties of this graph and are of interest for the general Ancestral Recombination Graph reconstruction problem."



Andreas W. M. Dress and
Daniel H. Huson. Constructing splits graphs. In TCBB, Vol. 1(3):109115, 2004. Keywords: abstract network, circular split system, from trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization. Note: http://scilib.kiev.ua/ieee/tcbb/2004/03/n3/n0109.pdf.
Toggle abstract
"Phylogenetic trees correspond onetoone to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetlc algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, NeighborNet, consensus networks, and the Zclosure method. A more general split system of this kind can be represented graphically by a socalled splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4. © 2004 IEEE."



Daniel H. Huson,
Tobias Dezulian,
Tobias Kloepper and
Mike Steel. Phylogenetic SuperNetworks from Partial Trees. In TCBB, Vol. 1(4):151158, 2004. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, supernetwork. Note: http://hdl.handle.net/10092/3177.
Toggle abstract
"In practice, one is often faced with incomplete phylogenetic data, such as a collection of partial trees or partial splits. This paper poses the problem of Inferring a phylogenetic supernetwork from such data and provides an efficient algorithm for doing so, called the Zclosure method. Additionally, the questions of assigning lengths to the edges of the network and how to restrict the "dimensionality" of the network are addressed. Applications to a set of five published partial gene trees relating different fungal species and to six published partial gene trees relating different grasses illustrate the usefulness of the method and an experimental study confirms Its potential. The method Is implemented as a plugin for the program SplitsTree4. © 2004 IEEE."



Bernard M. E. Moret,
Luay Nakhleh,
Tandy Warnow,
C. Randal Linder,
Anna Tholse,
Anneke Padolina,
Jerry Sun and
Ruth Timme. Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy. In TCBB, Vol. 1(1):1323, 2004. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, time consistent network, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb04.pdf.


