


R. A. Leo Elworth,
Huw A. Ogilvie,
Jiafan Zhu and
Luay Nakhleh. Advances in Computational Methods for Phylogenetic Networks in the Presence of Hybridization. In
Tandy Warnow editor, Bioinformatics and Phylogenetics. Seminal Contributions of Bernard Moret, Vol. 29 of Computational Biology, Springer, 2019. Keywords: explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program PhyloNet, Program PhyloNetworks SNaQ, Program PIRN, Program SplitsTree, reconstruction, survey. Note: https://bioinfocs.rice.edu/sites/g/files/bxs266/f/ElworthZhuOgilvieNakhleh.pdf



Juan Wang and
Maozu Guo. IGNet: Constructing Rooted Phylogenetic Networks Based on Incompatible Graphs. In ICNCFSKD19, Vol. 1075:894900 of Advances in Intelligent Systems and Computing, Springer, 2019. Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, Program BIMLR, Program IGNet, Program LNetwork, reconstruction, software.





Jesper Jansson,
Konstantinos Mampentzidis,
Ramesh Rajaby and
WingKin Sung. Computing the Rooted Triplet Distance Between Phylogenetic Networks. In IWOCA19, Vol. 11638:290303 of LNCS, Springer, 2019. Keywords: distance between networks, from network, phylogenetic network, phylogeny, polynomial, triplet distance.



Gabriel Cardona,
Joan Carles Pons and
Celine Scornavacca. Generation of Binary TreeChild phylogenetic networks. In PLoS Computational Biology, Vol. 15(10):e1007440.129, 2019. Keywords: enumeration, explicit network, generation, phylogenetic network, phylogeny, Program PhyloNetwork, Program TCGenerators, software, treechild network. Note: https://doi.org/10.1371/journal.pcbi.1007440.



Sarah Bastkowski,
Daniel Mapleson,
Andreas Spillner,
Taoyang Wu,
Monika Balvociute and
Vincent Moulton. SPECTRE: a Suite of PhylogEnetiC Tools for Reticulate Evolution. In BIO, Vol. 34(6):10571058, 2018. Keywords: abstract network, NeighborNet, phylogenetic network, phylogeny, Program FlatNJ, Program QNet, Program SplitsTree, reconstruction, software, split network. Note: https://doi.org/10.1101/169177.



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.



Philippe Gambette,
Katharina Huber and
Guillaume Scholz. Uprooted Phylogenetic Networks. In BMB, Vol. 79(9):20222048, 2017. Keywords: circular split system, explicit network, from splits, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction, split network, uniqueness. Note: http://arxiv.org/abs/1511.08387.



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.







James Oldman,
Taoyang Wu,
Leo van Iersel and
Vincent Moulton. TriLoNet: Piecing together small networks to reconstruct reticulate evolutionary histories. In MBE, Vol. 33(8):21512162, 2016. Keywords: explicit network, from subnetworks, from trinets, galled tree, phylogenetic network, phylogeny, Program LEV1ATHAN, Program TriLoNet, reconstruction.



Monika Balvociute. Flat Embeddings of Genetic and Distance Data. PhD thesis, University of Otago, 2016. Keywords: abstract network, flat, phylogenetic network, phylogeny, planar, Program FlatNJ, Program SplitsTree, split, split network. Note: http://hdl.handle.net/10523/6286.



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):559585, 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.



Benjamin Albrecht. Computing all hybridization networks for multiple binary phylogenetic input trees. In BMCB, Vol. 16(236):115, 2015. Keywords: agreement forest, explicit network, exponential algorithm, FPT, from rooted trees, phylogenetic network, phylogeny, Program Hybroscale, Program PIRN, reconstruction. Note: http://dx.doi.org/10.1186/s1285901506607.







Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In Journal of Discrete Algorithms, Vol. 25:6678, 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 socalled 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 almostmonochromatic triangles in an undirected, edgecolored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new 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, edgecolored 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, edgecolored graph with n vertices and R is a binary relation on the colors that is computable in O(1) time then the number of Rchromatic triangles in G can be computed in o(n2.687) time. © 2013 Elsevier B.V. All rights reserved."



Lavanya Kannan and
Ward C Wheeler. Exactly Computing the Parsimony Scores on Phylogenetic Networks Using Dynamic Programming. In JCB, Vol. 21(4):303319, 2014. Keywords: explicit network, exponential algorithm, from network, from sequences, parsimony, phylogenetic network, phylogeny, reconstruction.
Toggle abstract
"Scoring a given phylogenetic network is the first step that is required in searching for the best evolutionary framework for a given dataset. Using the principle of maximum parsimony, we can score phylogenetic networks based on the minimum number of state changes across a subset of edges of the network for each character that are required for a given set of characters to realize the input states at the leaves of the networks. Two such subsets of edges of networks are interesting in light of studying evolutionary histories of datasets: (i) the set of all edges of the network, and (ii) the set of all edges of a spanning tree that minimizes the score. The problems of finding the parsimony scores under these two criteria define slightly different mathematical problems that are both NPhard. In this article, we show that both problems, with scores generalized to adding substitution costs between states on the endpoints of the edges, can be solved exactly using dynamic programming. We show that our algorithms require O(mpk) storage at each vertex (per character), where k is the number of states the character can take, p is the number of reticulate vertices in the network, m = k for the problem with edge set (i), and m = 2 for the problem with edge set (ii). This establishes an O(nmpk2) algorithm for both the problems (n is the number of leaves in the network), which are extensions of Sankoff's algorithm for finding the parsimony scores for phylogenetic trees. We will discuss improvements in the complexities and show that for phylogenetic networks whose underlying undirected graphs have disjoint cycles, the storage at each vertex can be reduced to O(mk), thus making the algorithm polynomial for this class of networks. We will present some properties of the two approaches and guidance on choosing between the criteria, as well as traverse through the network space using either of the definitions. We show that our methodology provides an effective means to study a wide variety of datasets. © Copyright 2014, Mary Ann Liebert, Inc. 2014."



Jialiang Yang,
Stefan Grünewald,
Yifei Xu and
XiuFeng Wan. Quartetbased methods to reconstruct phylogenetic networks. In BMC Systems Biology, Vol. 80(21), 2014. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program QuartetMethods, Program QuartetNet, Program SplitsTree, reconstruction. Note: http://dx.doi.org/10.1186/17520509821
.
Toggle abstract
"Background: Phylogenetic networks are employed to visualize evolutionary relationships among a group of nucleotide sequences, genes or species when reticulate events like hybridization, recombination, reassortant and horizontal gene transfer are believed to be involved. In comparison to traditional distancebased methods, quartetbased methods consider more information in the reconstruction process and thus have the potential to be more accurate.Results: We introduce QuartetSuite, which includes a set of new quartetbased methods, namely QuartetS, QuartetA, and QuartetM, to reconstruct phylogenetic networks from nucleotide sequences. We tested their performances and compared them with other popular methods on two simulated nucleotide sequence data sets: one generated from a tree topology and the other from a complicated evolutionary history containing three reticulate events. We further validated these methods to two real data sets: a bacterial data set consisting of seven concatenated genes of 36 bacterial species and an influenza data set related to recently emerging H7N9 low pathogenic avian influenza viruses in China.Conclusion: QuartetS, QuartetA, and QuartetM have the potential to accurately reconstruct evolutionary scenarios from simple branching trees to complicated networks containing many reticulate events. These methods could provide insights into the understanding of complicated biological evolutionary processes such as bacterial taxonomy and reassortant of influenza viruses. © 2014 Yang et al.; licensee BioMed Central Ltd."





Monika Balvociute,
Andreas Spillner and
Vincent Moulton. FlatNJ: A Novel NetworkBased Approach to Visualize Evolutionary and Biogeographical Relationships. In Systematic Biology, Vol. 63(3):383396, 2014. Keywords: abstract network, flat, phylogenetic network, phylogeny, Program FlatNJ, Program SplitsTree, split network. Note: http://dx.doi.org/10.1093/sysbio/syu001.
Toggle abstract
"Split networks are a type of phylogenetic network that allow visualization of conflict in evolutionary data. We present a new method for constructing such networks called FlatNetJoining (FlatNJ). A key feature of FlatNJ is that it produces networks that can be drawn in the plane in which labels may appear inside of the network. For complex data sets that involve, for example, nonneutral molecular markers, this can allow additional detail to be visualized as compared to previous methods such as split decomposition and NeighborNet. We illustrate the application of FlatNJ by applying it to whole HIV genome sequences, where recombination has taken place, fluorescent proteins in corals, where ancestral sequences are present, and mitochondrial DNA sequences from gall wasps, where biogeographical relationships are of interest. We find that the networks generated by FlatNJ can facilitate the study of genetic variation in the underlying molecular sequence data and, in particular, may help to investigate processes such as intralocus recombination. FlatNJ has been implemented in Java and is freely available at www.uea.ac.uk/computing/software/ flatnj. [flat split system; NeighborNet; Phylogenetic network; QNet; split; split network.] © The Author(s) 2014."





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.



Leo van Iersel and
Simone Linz. A quadratic kernel for computing the hybridization number of multiple trees. In IPL, Vol. 113:318323, 2013. Keywords: explicit network, FPT, from rooted trees, kernelization, minimum number, phylogenetic network, phylogeny, Program Clustistic, Program MaafB, Program PIRN, reconstruction. Note: http://arxiv.org/abs/1203.4067, poster.
Toggle abstract
"It has recently been shown that the NPhard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixedparameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixedparameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel. © 2013 Elsevier B.V."



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



Peter J. Humphries,
Simone Linz and
Charles Semple. On the complexity of computing the temporal hybridization number for two phylogenies. In DAM, Vol. 161:871880, 2013. Keywords: agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.unituebingen.de/people/linz/publications/TAFapx.pdf.
Toggle abstract
"Phylogenetic networks are now frequently used to explain the evolutionary history of a set of species for which a collection of gene trees, reconstructed from genetic material of different parts of the species' genomes, reveal inconsistencies. However, in the context of hybridization, the reconstructed networks are often not temporal. If a hybridization network is temporal, then it satisfies the time constraint of instantaneously occurring hybridization events; i.e. all species that are involved in such an event coexist in time. Furthermore, although a collection of phylogenetic trees can often be merged into a hybridization network that is temporal, many algorithms do not necessarily find such a network since their primary optimization objective is to minimize the number of hybridization events. In this paper, we present a characterization for when two rooted binary phylogenetic trees admit a temporal hybridization network. Furthermore, we show that the underlying optimization problem is APXhard and, therefore, NPhard. Thus, unless P=NP, it is unlikely that there are efficient algorithms for either computing an exact solution or approximating it within a ratio arbitrarily close to one. © 2012 Elsevier B.V. All rights reserved."



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



Alexey A. Morozov,
Yuri P. Galachyants and
Yelena V. Likhoshway. Inferring Phylogenetic Networks from Gene Order Data. In BMRI, Vol. 2013(503193):17, 2013. Keywords: abstract network, from distances, from gene order, NeighborNet, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split decomposition, split network.
Toggle abstract
"Existing algorithms allow us to infer phylogenetic networks from sequences (DNA, protein or binary), sets of trees, and distance matrices, but there are no methods to build them using the gene order data as an input. Here we describe several methods to build split networks from the gene order data, perform simulation studies, and use our methods for analyzing and interpreting different real gene order datasets. All proposed methods are based on intermediate data, which can be generated from genome structures under study and used as an input for network construction algorithms. Three intermediates are used: set of jackknife trees, distance matrix, and binary encoding. According to simulations and case studies, the best intermediates are jackknife trees and distance matrix (when used with NeighborNet algorithm). Binary encoding can also be useful, but only when the methods mentioned above cannot be used. © 2013 Alexey Anatolievich Morozov et al."



Sarah Bastkowski. From Trees to Networks and Back. PhD thesis, University of East Anglia, 2013. Keywords: abstract network, NeighborNet, phylogenetic network, phylogeny, Program FlatNJ, Program QNet, Program SplitsTree, reconstruction, software, split network. Note: http://spectresuiteofphylogenetictoolsforreticulateevolution.readthedocs.io/en/latest/_downloads/spectre_bastkowskis_thesis.pdf.



Andreas Spillner and
Vincent Moulton. Optimal algorithms for computing edge weights in planar splitnetworks. In Journal of Applied Mathematics and Computing, Vol. 39(12):113, 2012. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://dx.doi.org/10.1007/s121900110506z.
Toggle abstract
"In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graphtheoretical structures represent collections of weighted bipartitions or splits of a finite set, and provide a means to display conflicting evolutionary signals. The weights associated to the splits are used to scale the edges in the network and are often computed using some distance matrix associated with the data. In this paper we present optimal polynomial time algorithms for three basic problems that arise in this context when computing split weights for planar splitnetworks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outerlabeled planar networks). As part of our analysis, we also derive a Crofton formula for full flat split systems, structures that naturally arise when constructing planar splitnetworks. © 2011 Korean Society for Computational and Applied Mathematics."



Celine Scornavacca,
Simone Linz and
Benjamin Albrecht. A first step towards computing all hybridization networks for two rooted binary phylogenetic trees. In JCB, Vol. 19:12271242, 2012. Keywords: agreement forest, explicit network, FPT, from rooted trees, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction. Note: http://arxiv.org/abs/1109.3268.
Toggle abstract
"Recently, considerable effort has been put into developing fast algorithms to reconstruct a rooted phylogenetic network that explains two rooted phylogenetic trees and has a minimum number of hybridization vertices. With the standard app1235roach to tackle this problem being combinatorial, the reconstructed network is rarely unique. From a biological point of view, it is therefore of importance to not only compute one network, but all possible networks. In this article, we make a first step toward approaching this goal by presenting the first algorithmcalled allMAAFsthat calculates all maximumacyclicagreement forests for two rooted binary phylogenetic trees on the same set of taxa. © Copyright 2012, Mary Ann Liebert, Inc. 2012."



Changiz Eslahchi,
Reza Hassanzadeh,
Ehsan Mottaghi,
Mahnaz Habibi,
Hamid Pezeshk and
Mehdi Sadeghi. Constructing circular phylogenetic networks from weighted quartets using simulated annealing. In MBIO, Vol. 235(2):123127, 2012. Keywords: abstract network, from quartets, heuristic, phylogenetic network, phylogeny, Program SAQNet, Program SplitsTree, reconstruction, simulated annealing, software, split network. Note: http://dx.doi.org/10.1016/j.mbs.2011.11.003.
Toggle abstract
"In this paper, we present a heuristic algorithm based on the simulated annealing, SAQNet, as a method for constructing phylogenetic networks from weighted quartets. Similar to QNet algorithm, SAQNet constructs a collection of circular weighted splits of the taxa set. This collection is represented by a split network. In order to show that SAQNet performs better than QNet, we apply these algorithm to both the simulated and actual data sets containing salmonella, Bees, Primates and Rubber data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree4 and compare the results. We find that SAQNet produces a better circular ordering and phylogenetic networks than QNet in most cases. SAQNet has been implemented in Matlab and is available for download at http://bioinf.cs.ipm.ac.ir/softwares/saq.net. © 2011 Elsevier Inc."





Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In CPM12, Vol. 7354:385398 of LNCS, springer, 2012. Keywords: distance between networks, explicit network, from network, galled tree, phylogenetic network, phylogeny, polynomial, triplet distance. Note: http://www.df.lth.se/~jj/Publications/d_rt_for_Galled_Trees5_CPM_2012.pdf.
Toggle abstract
"We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a socalled galled tree with n leaves then the rooted triplet distance can be computed in o(n 2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost monochromatic triangles in an undirected, edgecolored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new related results that may be of independent interest. © 2012 SpringerVerlag."



Katharina Huber,
Vincent Moulton,
Andreas Spillner,
Sabine Storandt and
Radoslaw Suchecki. Computing a consensus of multilabeled trees. In ALENEX12, Pages 8492, 2012. Keywords: duplication, explicit network, exponential algorithm, phylogenetic network, phylogeny. Note: http://siam.omnibooksonline.com/2012ALENEX/data/papers/020.pdf.
Toggle abstract
In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential runtime in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.



Lavanya Kannan,
Hua Li and
Arcady Mushegian. A PolynomialTime Algorithm Computing Lower and Upper Bounds of the Rooted Subtree Prune and Regraft Distance. In JCB, Vol. 18(5):743757, 2011. Keywords: bound, minimum number, polynomial, SPR distance. Note: http://dx.doi.org/10.1089/cmb.2010.0045.
Toggle abstract
"Rooted, leaflabeled 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 NPhard, 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 DClust 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 nearlyprecise 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."



Changiz Eslahchi,
Mahnaz Habibi,
Reza Hassanzadeh and
Ehsan Mottaghi. MCNet: a method for the construction of phylogenetic networks based on the MonteCarlo method. In BMCEB, Vol. 10:254, 2010. Keywords: abstract network, circular split system, from distances, heuristic, phylogenetic network, Program MCNet, Program SplitsTree, software, split, split network. Note: http://dx.doi.org/10.1186/1471214810254.
Toggle abstract
"Background. A phylogenetic network is a generalization of phylogenetic trees that allows the representation of conflicting signals or alternative evolutionary histories in a single diagram. There are several methods for constructing these networks. Some of these methods are based on distances among taxa. In practice, the methods which are based on distance perform faster in comparison with other methods. The NeighborNet (NNet) is a distancebased method. The NNet produces a circular ordering from a distance matrix, then constructs a collection of weighted splits using circular ordering. The SplitsTree which is a program using these weighted splits makes a phylogenetic network. In general, finding an optimal circular ordering is an NPhard problem. The NNet is a heuristic algorithm to find the optimal circular ordering which is based on neighborjoining algorithm. Results. In this paper, we present a heuristic algorithm to find an optimal circular ordering based on the MonteCarlo method, called MCNet algorithm. In order to show that MCNet performs better than NNet, we apply both algorithms on different data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree and compare the results. Conclusions. We find that the circular ordering produced by the MCNet is closer to optimal circular ordering than the NNet. Furthermore, the networks corresponding to outputs of MCNet made by SplitsTree are simpler than NNet. © 2010 Eslahchi et al; licensee BioMed Central Ltd."



David A. Morrison. Using datadisplay networks for exploratory data analysis in phylogenetic studies. In MBE, Vol. 27(5):10441057, 2010. Keywords: abstract network, hybridization, NeighborNet, Program SplitsTree, recombination, split decomposition. Note: http://dx.doi.org/10.1093/molbev/msp309.
Toggle abstract
"Exploratory data analysis (EDA) is a frequently undervalued part of data analysis in biology. It involves evaluating the characteristics of the data "before" proceeding to the definitive analysis in relation to the scientific question at hand. For phylogenetic analyses, a useful tool for EDA is a datadisplay network. This type of network is designed to display any character (or tree) conflict in a data set, without prior assumptions about the causes of those conflicts. The conflicts might be caused by 1) methodological issues in data collection or analysis, 2) homoplasy, or 3) horizontal gene flow of some sort. Here, I explore 13 published data sets using splits networks, as examples of using datadisplay networks for EDA. In each case, I performed an original EDA on the data provided, to highlight the aspects of the resulting network that will be important for an interpretation of the phylogeny. In each case, there is at least one important point (possibly missed by the original authors) that might affect the phylogenetic analysis. I conclude that EDA should play a greater role in phylogenetic analyses than it has done. © 2010 The Author. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved."



Robert G. Beiko. Gene sharing and genome evolution: networks in trees and trees in networks. In Biology and Philosophy, Vol. 25(4):659673, 2010. Keywords: abstract network, explicit network, from rooted trees, galled network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, reconstruction, split network, survey. Note: http://dx.doi.org/10.1007/s1053901092173.
Toggle abstract
"Frequent lateral genetic transfer undermines the existence of a unique "tree of life" that relates all organisms. Vertical inheritance is nonetheless of vital interest in the study of microbial evolution, and knowing the "tree of cells" can yield insights into ecological continuity, the rates of change of different cellular characters, and the evolutionary plasticity of genomes. Notwithstanding withinspecies recombination, the relationships most frequently recovered from genomic data at shallow to moderate taxonomic depths are likely to reflect cellular inheritance. At the same time, it is clear that several types of 'average signals' from whole genomes can be highly misleading, and the existence of a central tendency must not be taken as prima facie evidence of vertical descent. Phylogenetic networks offer an attractive solution, since they can be formulated in ways that mitigate the misleading aspects of hybrid evolutionary signals in genomes. But the connections in a network typically show genetic relatedness without distinguishing between vertical and lateral inheritance of genetic material. The solution may lie in a compromise between strict treethinking and network paradigms: build a phylogenetic network, but identify the set of connections in the network that are potentially due to vertical descent. Even if a single tree cannot be unambiguously identified, choosing a subnetwork of putative vertical connections can still lead to drastic reductions in the set of candidate vertical hypotheses. © 2010 Springer Science+Business Media B.V."



Chris Whidden,
Robert G. Beiko and
Norbert Zeh. Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments. In Proceedings of the ninth International Symposium on Experimental Algorithms (SEA'10), Vol. 6049:141153 of LNCS, springer, 2010. Keywords: agreement forest, explicit network, FPT, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program HybridInterleave, reconstruction, SPR distance. Note: https://www.cs.dal.ca/sites/default/files/technical_reports/CS201003.pdf.
Toggle abstract
"We improve on earlier FPT algorithms for computing a rooted maximum agreement forest (MAF) or a maximum acyclic agreement forest (MAAF) of a pair of phylogenetic trees. Their sizes give the subtreepruneandregraft (SPR) distance and the hybridization number of the trees, respectively. We introduce new branching rules that reduce the running time of the algorithms from O(3 kn) and O(3 kn log n) to O(2.42 kn) and O(2.42 kn log n), respectively. In practice, the speed up may be much more than predicted by the worstcase analysis.We confirm this intuition experimentally by computing MAFs for simulated trees and trees inferred from protein sequence data. We show that our algorithm is orders of magnitude faster and can handle much larger trees and SPR distances than the best previous methods, treeSAT and sprdist. © SpringerVerlag Berlin Heidelberg 2010."





Binh T. Nguyen. Novel SplitBased Approaches to Computing Phylogenetic Diversity and Planar Split Networks. PhD thesis, University of East Anglia, U.K., 2010. Keywords: abstract network, diversity, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: https://ueaeprints.uea.ac.uk/id/eprint/34218.



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



Daniel H. Huson,
Regula Rupp,
Vincent Berry,
Philippe Gambette and
Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85i93 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://hallirmm.ccsd.cnrs.fr/lirmm00368545/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 levelk networks, that are more tractable, but have the practical drawback 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 tradeoff 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 NPcomplete 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)."





Simon Joly,
Patricia A. McLenachan and
Peter J. Lockhart. A Statistical Approach for Distinguishing Hybridization and Incomplete Lineage Sorting. In The American Naturalist, Vol. 174(2):E54E70, 2009. Keywords: hybridization, lineage sorting, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://www.plantevolution.org/pdf/Joly&al_2009_AmNat.pdf.
Toggle abstract
"The extent and evolutionary significance of hybridization is difficult to evaluate because of the difficulty in distinguishing hybridization from incomplete lineage sorting. Here we present a novel parametric approach for statistically distinguishing hybridization from incomplete lineage sorting based on minimum genetic distances of a nonrecombining locus. It is based on the idea that the expected minimum genetic distance between sequences from two species is smaller for some hybridization events than for incomplete lineage sorting scenarios. When applied to empirical data sets, distributions can be generated for the minimum interspecies distances expected under incomplete lineage sorting using coalescent simulations. If the observed distance between sequences from two species is smaller than its predicted distribution, incomplete lineage sorting can be rejected and hybridization inferred. We demonstrate the power of the method using simulations and illustrate its application on New Zealand alpine buttercups (Ranunculus). The method is robust and complements existing approaches. Thus it should allow biologists to assess with greater accuracy the importance of hybridization in evolution. © 2009 by The University of Chicago."





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



Stefan Grünewald,
Katharina Huber and
Qiong Wu. Two novel closure rules for constructing phylogenetic supernetworks. In BMB, Vol. 70(7):19061924, 2008. Keywords: abstract network, from splits, from unrooted trees, phylogenetic network, phylogeny, Program MY CLOSURE, reconstruction, supernetwork. Note: http://arxiv.org/abs/0709.0283, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/huber/.
Toggle abstract
"A contemporary and fundamental problem faced by many evolutionary biologists is how to puzzle together a collection P of partial trees (leaflabeled trees whose leaves are bijectively labeled by species or, more generally, taxa, each supported by, e.g., a gene) into an overall parental structure that displays all trees in P. This already difficult problem is complicated by the fact that the trees in P regularly support conflicting phylogenetic relationships and are not on the same but only overlapping taxa sets. A desirable requirement on the sought after parental structure, therefore, is that it can accommodate the observed conflicts. Phylogenetic networks are a popular tool capable of doing precisely this. However, not much is known about how to construct such networks from partial trees, a notable exception being the Zclosure supernetwork approach, which is based on the Zclosure rule, and the Qimputation approach. Although attractive approaches, they both suffer from the fact that the generated networks tend to be multidimensional making it necessary to apply some kind of filter to reduce their complexity. To avoid having to resort to a filter, we follow a different line of attack in this paper and develop closure rules for generating circular phylogenetic networks which have the attractive property that they can be represented in the plane. In particular, we introduce the novel Y(closure) rule and show that this rule on its own or in combination with one of Meacham's closure rules (which we call the Mrule) has some very desirable theoretical properties. In addition, we present a case study based on Rivera et al. "ring of life" to explore the reconstructive power of the M and Yrule and also reanalyze an Arabidopsis thaliana data set. © 2008 Society for Mathematical Biology."



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



Tobias Kloepper and
Daniel H. Huson. Drawing explicit phylogenetic networks and their integration into SplitsTree. In BMCEB, Vol. 8(22), 2008. Keywords: explicit network, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://dx.doi.org/10.1186/14712148822.
Toggle abstract
"Background. SplitsTree provides a framework for the calculation of phylogenetic trees and networks. It contains a wide variety of methods for the import/export, calculation and visualization of phylogenetic information. The software is developed in Java and implements a command line tool as well as a graphical user interface. Results. In this article, we present solutions to two important problems in the field of phylogenetic networks. The first problem is the visualization of explicit phylogenetic networks. To solve this, we present a modified version of the equal angle algorithm that naturally integrates reticulations into the layout process and thus leads to an appealing visualization of these networks. The second problem is the availability of explicit phylogenetic network methods for the general user. To advance the usage of explicit phylogenetic networks by biologists further, we present an extension to the SplitsTree framework that integrates these networks. By addressing these two problems, SplitsTree is among the first programs that incorporates implicit and explicit network methods together with standard phylogenetic tree methods in a graphical user interface environment. Conclusion. In this article, we presented an extension of SplitsTree 4 that incorporates explicit phylogenetic networks. The extension provides a set of core classes to handle explicit phylogenetic networks and a visualization of these networks. © 2008 Kloepper and Huson; licensee BioMed Central Ltd."



Steven M. Woolley,
David Posada and
Keith A. Crandall. A Comparison of Phylogenetic Network Methods Using Computer Simulation. In PLoS ONE, Vol. 3(4):e1913, 2008. Keywords: abstract network, distance between networks, evaluation, median network, MedianJoining, minimum spanning network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program SHRUB, Program SplitsTree, Program TCS, split decomposition. Note: http://dx.doi.org/10.1371/journal.pone.0001913.
Toggle abstract
"Background: We present a series of simulation studies that explore the relative performance of several phylogenetic network approaches (statistical parsimony, split decomposition, union of maximum parsimony trees, neighbornet, simulated history recombination upper bound, medianjoining, reduced median joining and minimum spanning network) compared to standard tree approaches (neighborjoining and maximum parsimony) in the presence and absence of recombination. Principal Findings: In the absence of recombination, all methods recovered the correct topology and branch lengths nearly all of the time when the subtitution rate was low, except for minimum spanning networks, which did considerably worse. At a higher substitution rate, maximum parsimony and union of maximum parsimony trees were the most accurate. With recombination, the ability to infer the correct topology was halved for all methods and no method could accurately estimate branch lengths. Conclusions: Our results highlight the need for more accurate phylogenetic network methods and the importance of detecting and accounting for recombination in phylogenetic studies. Furthermore, we provide useful information for choosing a network algorithm and a framework in which to evaluate improvements to existing methods and novel algorithms developed in the future. © 2008 Woolley et al."



James B. Whitfield,
Sydney A. Cameron,
Daniel H. Huson and
Mike Steel. Filtered ZClosure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees. In Systematic Biology, Vol. 57(6):939947, 2008. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, split, split network, supernetwork. Note: http://www.life.uiuc.edu/scameron/pdfs/Filtered%20Zclosure%20SystBiol.pdf.



Tobias Kloepper. Algorithms for the Calculation and Visualisation of Phylogenetic Networks. PhD thesis, EberhardKarlsUniversität Tübingen, Germany, 2008. Keywords: from rooted trees, from sequences, from unrooted trees, galled network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization. Note: https://publikationen.unituebingen.de/xmlui/handle/10900/49159.



Stefan Grünewald,
Andreas Spillner,
Kristoffer Forslund and
Vincent Moulton. Constructing Phylogenetic Supernetworks from Quartets. In WABI08, Vol. 5251:284295 of LNCS, springer, 2008. Keywords: abstract network, from quartets, from unrooted trees, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, reconstruction, split network. Note: http://dx.doi.org/10.1007/9783540873617_24.
Toggle abstract
"In phylogenetics it is common practice to summarize collections of partial phylogenetic trees in the form of supertrees. Recently it has been proposed to construct phylogenetic supernetworks as an alternative to supertrees as these allow the representation of conflicting information in the trees, information that may not be representable in a single tree. Here we introduce SuperQ, a new method for constructing such supernetworks. It works by breaking the input trees into quartet trees, and stitching together the resulting set to form a network. The stitching process is performed using an adaptation of the QNet method for phylogenetic network reconstruction. In addition to presenting the new method, we illustrate the applicability of SuperQ to three data sets and discuss future directions for testing and development. © 2008 SpringerVerlag Berlin Heidelberg."



Gabriel Cardona,
Francesc Rosselló and
Gabriel Valiente. Extended Newick: It is Time for a Standard Representation. In BMCB, Vol. 9:532, 2008. Keywords: evaluation, explicit network, phylogenetic network, Program Bio PhyloNetwork, Program Dendroscope, Program NetGen, Program PhyloNet, Program SplitsTree, Program TCS, visualization. Note: http://bioinfo.uib.es/media/uploaded/bmc2008enewicksub.pdf.



Magnus Bordewich,
Simone Linz,
Katherine St. John and
Charles Semple. A reduction algorithm for computing the hybridization number of two trees. In EBIO, Vol. 3:8698, 2007. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNumber. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BLSS07.pdf.



Magnus Bordewich and
Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914918, 2007. Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.





Daniel H. Huson. Split networks and Reticulate Networks. In
Olivier Gascuel and
Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 247276, Oxford University Press, 2007. Keywords: abstract network, consensus, from rooted trees, from sequences, from splits, from unrooted trees, galled tree, hybridization, phylogenetic network, phylogeny, Program Beagle, Program Spectronet, Program SplitsTree, Program SPNet, recombination, reconstruction, split network, survey. Note: similar to http://wwwab.informatik.unituebingen.de/research/phylonets/GCB2006.pdf.



Daniel H. Huson and
Tobias Kloepper. Beyond Galled Trees  Decomposition and Computation of Galled Networks. In RECOMB07, Vol. 4453:211225 of LNCS, springer, 2007. Keywords: FPT, from splits, from trees, galled network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction. Note: http://dx.doi.org/10.1007/9783540716815_15, errata..



Guohua Jin,
Luay Nakhleh,
Sagi Snir and
Tamir Tuller. A New Lineartime Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance. In ISBRA07, Vol. 4463:6172 of LNCS, springer, 2007. Keywords: approximation, heuristic, parsimony, phylogenetic network, phylogeny, Program Nepal. Note: http://www.cs.rice.edu/~nakhleh/Papers/isbra07.pdf.



Cam Thach Nguyen,
Nguyen Bao Nguyen and
WingKin Sung. Fast Algorithms for computing the Tripartitionbased Distance between Phylogenetic Networks. In JCO, Vol. 13(3), 2007. Keywords: distance between networks, phylogenetic network, phylogeny, tripartition distance. Note: http://dx.doi.org/10.1007/s1087800690255.
Toggle abstract
"Consider two phylogenetic networks N and N′ of size n. The tripartitionbased distance finds the proportion of tripartitions which are not shared by N and N′. This distance is proposed by Moret et al. (2004) and is a generalization of RobinsonFoulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an O(min {kn log n, n log n + hn} time algorithm to compute this distance, where h is the number of hybrid nodes in N and N′ while k is the maximum number of hybrid nodes among all biconnected components in N and N′. Note that k ≪ h ≪ n in a phylogenetic network. In addition, we propose algorithms for comparing galledtrees, which are an important, biological meaningful special case of phylogenetic network. We give an O(n)time algorithm for comparing two galledtrees. We also give an O(n + kh)time algorithm for comparing a galledtree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. © Springer Science+Business Media, LLC 2007."





Bastienne Vriesendorp. Phylogenenetworks, exploring reticulate evolution and its consequences for phylogenetic reconstruction. PhD thesis, Wageningen University, The Netherlands, 2007. Keywords: consensus, distance between networks, evaluation, hybridization, median network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program SplitsTree, split decomposition, survey. Note: http://library.wur.nl/wda/dissertations/dis4239.pdf.



Daniel H. Huson and
David Bryant. Application of Phylogenetic Networks in Evolutionary Studies. In MBE, Vol. 23(2):254267, 2006. Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, survey. Note: http://dx.doi.org/10.1093/molbev/msj030, software available from www.splitstree.org.
Toggle abstract
"The evolutionary history of a set of taxa is usually represented by a phylogenetic tree, and this model has greatly facilitated the discussion and testing of hypotheses. However, it is well known that more complex evolutionary scenarios are poorly described by such models. Further, even when evolution proceeds in a treelike manner, analysis of the data may not be best served by using methods that enforce a tree structure but rather by a richer visualization of the data to evaluate its properties, at least as an essential first step. Thus, phylogenetic networks should be employed when reticulate events such as hybridization, horizontal gene transfer, recombination, or gene duplication and loss are believed to be involved, and, even in the absence of such events, phylogenetic networks have a useful role to play. This article reviews the terminology used for phylogenetic networks and covers both split networks and reticulate networks, how they are defined, and how they can be interpreted. Additionally, the article outlines the beginnings of a comprehensive statistical framework for applying split network methods. We show how split networks can represent confidence sets of trees and introduce a conservative statistical test for whether the conflicting signal in a network is treelike. Finally, this article describes a new program, SplitsTree4, an interactive and comprehensive tool for inferring different types of phylogenetic networks from sequences, distances, and trees. © The Author 2005. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved."





Vladimir Makarenkov,
Dmytro Kevorkov and
Pierre Legendre. Phylogenetic Network Construction Approaches. In Applied Mycology and Biotechnology, Vol. 6:6197, 2006. Keywords: from distances, hybridization, lateral gene transfer, median network, NeighborNet, netting, Program Arlequin, Program Network, Program Pyramids, Program Reticlad, Program SplitsTree, Program T REX, Program TCS, Program WeakHierarchies, pyramid, reticulogram, split, split decomposition, split network, survey, weak hierarchy. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/MKL_article.pdf.



Sergey Bereg and
Kathryn Bean. Constructing Phylogenetic Networks from Trees. In BIBE05, Pages 299305, 2005. 1 comment Keywords: evaluation, from distances, phylogenetic network, phylogeny, Program SplitsTree, Program T REX, reconstruction, split, split network. Note: http://dx.doi.org/10.1109/BIBE.2005.19.
Toggle abstract
We present a new method of constructing a phylogenetic network from a given phylogenetic tree. It is based on a procedure that locally improves the tree. The procedure is quite general and can be applied to phylogenetic networks. By repeating local improvements user can introduce a given number of recombination cycles. A sequence of networks with decreasing distance deviation can be generated. The algorithm is efficient and shows a good performance on an example with plants. This is due to the fact that the update in every step is local and optimal. © 2005 IEEE.



Charles Choy,
Jesper Jansson,
Kunihiko Sadakane and
WingKin Sung. Computing the maximum agreement of phylogenetic networks. In TCS, Vol. 335(1):93107, 2005. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf.
Toggle abstract
"We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding branching structure shared by a set of phylogenetic networks. We prove that the problem is NPhard even if restricted to three phylogenetic networks and give an O(n2)time algorithm for the special case of two level1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a levelf phylogenetic network if every biconnected component in the underlying undirected graph induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomialtime algorithm for any two levelf phylogenetic networks N1,N2 satisfying f=O(logn); more precisely, its running time is O(V(N1)·V(N2)·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}. © 2005 Elsevier B.V. All rights reserved."



Daniel H. Huson and
Tobias Kloepper. Computing recombination networks from binary sequences. In ECCB05, Vol. 21(suppl. 2):ii159ii165 of BIO, 2005. Keywords: from sequences, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1126.
Toggle abstract
"Motivation:Phylogenetic networks are becoming an important tool in molecular evolution, as the evolutionary role of reticulate events, such as hybridization, horizontal gene transfer and recombination, is becoming more evident, and as the available data is dramatically increasing in quantity and quality. Results: This paper addresses the problem of computing a most parsimonious recombination network for an alignment of binary sequences that are assumed to have arisen under the 'infinite sites' model of evolution with recombinations. Using the concept of a splits network as the underlying datastructure, this paper shows how a recent method designed for the computation of hybridization networks can be extended to also compute recombination networks. A robust implementation of the approach is provided and is illustrated using a number of real biological datasets. © The Author 2005. Published by Oxford University Press. All rights reserved."



David A. Morrison. Networks in phylogenetic analysis: new tools for population biology. In IJP, Vol. 35:567582, 2005. Keywords: median network, NeighborNet, phylogenetic network, phylogeny, population genetics, Program Network, Program Spectronet, Program SplitsTree, Program T REX, Program TCS, reconstruction, reticulogram, split decomposition, survey. Note: http://hem.fyristorg.com/acacia/papers/networks.pdf.







David Bryant and
Vincent Moulton. NeighborNet: An Agglomerative Method for the Construction of Phylogenetic Networks. In MBE, Vol. 21(2):255265, 2004. Keywords: phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network. Note: http://www.math.auckland.ac.nz/~bryant/Papers/04NeighborNet.pdf.
Toggle abstract
"We present NeighborNet, a distance based method for constructing phylogenetic networks that is based on the NeighborJoining (NJ) algorithm of Saitou and Nei. NeighborNet provides a snapshot of the data that can guide more detailed analysis. Unlike split decomposition, NeighborNet scales well and can quickly produce detailed and informative networks for several hundred taxa. We illustrate the method by reanalyzing three published data sets: a collection of 110 highly recombinant Salmonella multilocus sequence typing sequences, the 135 "African Eve" human mitochondrial sequences published by Vigilant et al., and a collection of 12 Archeal chaperonin sequences demonstrating strong evidence for gene conversion. NeighborNet is available as part of the SplitsTree4 software package."



Charles Choy,
Jesper Jansson,
Kunihiko Sadakane and
WingKin Sung. Computing the maximum agreement of phylogenetic networks. In Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04), Vol. 91:134147 of Electronic Notes in Theoretical Computer Science, 2004. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf.
Toggle abstract
"We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NPhard even if restricted to three phylogenetic networks and give an O(n2)time algorithm for the special case of two level1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a levelf phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomialtime algorithm for two levelf phylogenetic networks N 1,N2 for any f which is upperbounded by a constant; more precisely, its running time is O(V(N1)·V(N 2)·4f), where V(Ni) denotes the set of nodes of Ni. © 2004 Published by Elsevier B.V."



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



Katharina Huber,
Michael Langton,
David Penny,
Vincent Moulton and
Mike Hendy. Spectronet: A package for computing spectra and median networks. In ABIO, Vol. 1(3):159161, 2004. Keywords: from splits, median network, phylogenetic network, phylogeny, Program Spectronet, software, split, visualization. Note: http://citeseer.ist.psu.edu/631776.html.
Toggle abstract
Spectronet is a package that uses various methods for exploring and visualising complex evolutionary signals. Given an alignment in NEXUS format, the package works by computing a collection of weighted splits or bipartitions of the taxa and then allows the user to interactively analyse the resulting collection using tools such as Lentoplots and median networks. The package is highly interactive and available for PCs.









David Bryant and
Vincent Moulton. NeighborNet: An Agglomerative Method for the Construction of Planar Phylogenetic Networks. In WABI02, Vol. 2452:375391 of LNCS, springer, 2002. Keywords: abstract network, circular split system, from distances, NeighborNet, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network. Note: http://dx.doi.org/10.1007/3540457844_28.





David Posada and
Keith A. Crandall. Intraspecific gene genealogies: trees grafting into networks. In TEE, Vol. 16(1):3745, 2001. Keywords: likelihood, median network, netting, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program SplitsTree, Program T REX, Program TCS, pyramid, reticulogram, split decomposition, statistical parsimony, survey. Note: http://darwin.uvigo.es/download/papers/09.networks01.pdf.



FrançoisJoseph Lapointe. How to account for reticulation events in phylogenetic analysis: A review of distancebased methods. In Journal of Classification, Vol. 17:175184, 2000. Keywords: abstract network, evaluation, from distances, phylogenetic network, Program Pyramids, Program SplitsTree, Program T REX, pyramid, reconstruction, reticulogram, split network, survey, weak hierarchy. Note: http://dx.doi.org/10.1007/s003570000016.



Vincent Berry and
David Bryant. Faster reliable phylogenetic analysis. In RECOMB99, Pages 5968, 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.





Andreas W. M. Dress,
Daniel H. Huson and
Vincent Moulton. Analyzing and visualizing distance data using SplitsTree. In DAM, Vol. 71(1):95109, 1996. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://bibiserv.techfak.unibielefeld.de/splits/splits.pdf.






