
HansJürgen Bandelt and
Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. In Advances in Mathematics, Vol. 92(1):47105, 1992. Keywords: abstract network, circular split system, from distances, split, split decomposition, split network, weak hierarchy, weakly compatible.
Toggle abstract
"We consider specific additive decompositions d = d1 + ... + dn of metrics, defined on a finite set X (where a metric may give distance zero to pairs of distinct points). The simplest building stones are the slit metrics, associated to splits (i.e., bipartitions) of the given set X. While an additive decomposition of a Hamming metric into split metrics is in no way unique, we achieve uniqueness by restricting ourselves to coherent decompositions, that is, decompositions d = d1 + ... + dn such that for every map f:X → R with f(x) + f(y) ≥ d(x, y) for all x, y ε{lunate} X there exist maps f1, ..., fn: X → R with f = f1 + ... + fn and fi(x) + fi(y) ≥ di(x, y) for all i = 1,..., n and all x, y ε{lunate} X. These coherent decompositions are closely related to a geometric decomposition of the injective hull of the given metric. A metric with a coherent decomposition into a (weighted) sum of split metrics will be called totally splitdecomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally splitdecomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally splitdecomposable metric and a splitprime residue, where all the split summands and hence the decomposition can be determined in polynomial time, and that a family of splits can occur this way if and only if it does not induce on any fourpoint subset all three splits with block size two. © 1992."



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



Stefan Grünewald,
Kristoffer Forslund,
Andreas W. M. Dress and
Vincent Moulton. QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets. In MBE, Vol. 24(2):532538, 2007. Keywords: abstract network, circular split system, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/24/2/532.
Toggle abstract
"We present QNet, a method for constructing split networks from weighted quartet trees. QNet can be viewed as a quartet analogue of the distancebased NeighborNet (NNet) method for network construction. Just as NNet, QNet works by agglomeratively computing a collection of circular weighted splits of the taxa set which is subsequently represented by a planar split network. To illustrate the applicability of QNet, we apply it to a previously published Salmonella data set. We conclude that QNet can provide a useful alternative to NNet if distance data are not available or a characterbased approach is preferred. Moreover, it can be used as an aid for determining when a quartetbased treebuilding method may or may not be appropriate for a given data set. QNet is freely available for download. © The Author 2006. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved."



Dan Levy and
Lior Pachter. The NeighborNet Algorithm. In Advances in Applied Mathematics, Vol. 47(2):240258, 2011. Keywords: abstract network, circular split system, evaluation, from distances, NeighborNet, phylogenetic network, phylogeny, split network. Note: http://arxiv.org/abs/math/0702515.
Toggle abstract
"The neighborjoining algorithm is a popular phylogenetics method for constructing trees from dissimilarity maps. The neighbornet algorithm is an extension of the neighborjoining algorithm and is used for constructing split networks. We begin by describing the output of neighbornet in terms of the tessellation of M̄0n(R) by associahedra. This highlights the fact that neighbornet outputs a tree in addition to a circular ordering and we explain when the neighbornet tree is the neighborjoining tree. A key observation is that the tree constructed in existing implementations of neighbornet is not a neighborjoining tree. Next, we show that neighbornet is a greedy algorithm for finding circular split systems of minimal balanced length. This leads to an interpretation of neighbornet as a greedy algorithm for the traveling salesman problem. The algorithm is optimal for Kalmanson matrices, from which it follows that neighbornet is consistent and has optimal radius 12. We also provide a statistical interpretation for the balanced length for a circular split system as the length based on weighted least squares estimates of the splits. We conclude with applications of these results and demonstrate the implications of our theorems for a recently published comparison of Papuan and Austronesian languages. © 2010 Elsevier Inc. All rights reserved."



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



Bui Quang Minh,
Steffen Klaere and
Arndt von Haeseler. Taxon Selection under Split Diversity. In Systematic Biology, Vol. 58(6):586594, 2009. Keywords: abstract network, circular split system, diversity, from network, phylogenetic network, split network. Note: http://dx.doi.org/10.1093/sysbio/syp058.
Toggle abstract
"The phylogenetic diversity (PD) measure of biodiversity is evaluated using a phylogenetic tree, usually inferred from morphological or molecular data. Consequently, it is vulnerable to errors in that tree, including those resulting from sampling error, model misspecification, or conflicting signals. To improve the robustness of PD, we can evaluate the measure using either a collection (or distribution) of trees or a phylogenetic network. Recently, it has been shown that these 2 approaches are equivalent but that the problem of maximizing PD in the general concept is NPhard. In this study, we provide an efficient dynamic programming algorithm for maximizing PD when splits in the trees or network form a circular split system. We illustrate our method using a case study of game birds (Galliformes) and discuss the different choices of taxa based on our approach and PD."



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,
Vincent Berry and
Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012. Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network. Note: http://hal.archivesouvertes.fr/hal00678046/en/.
Toggle abstract
"Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of levelk networks. In particular, we give an equivalence theorem between circular split systems and unrooted level1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted levelk phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press."



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



Sarah Bastkowski,
Andreas Spillner and
Vincent Moulton. Fishing for minimum evolution trees with NeighborNets. In IPL, Vol. 114(12):318, 2014. Keywords: circular split system, from distances, NeighborNet, phylogeny, polynomial.
Toggle abstract
"In evolutionary biology, biologists commonly use a phylogenetic tree to represent the evolutionary history of some set of species. A common approach taken to construct such a tree is to search through the space of all possible phylogenetic trees on the set so as to find one that optimizes some score function, such as the minimum evolution criterion. However, this is hampered by the fact that the space of phylogenetic trees is extremely large in general. Interestingly, an alternative approach, which has received somewhat less attention in the literature, is to instead search for trees within some set of bipartitions or splits of the set of species in question. Here we consider the problem of searching through a set of splits that is circular. Such sets can, for example, be generated by the NeighborNet algorithm for constructing phylogenetic networks. More specifically, we present an O(n4) time algorithm for finding an optimal minimum evolution tree in a circular set of splits on a set of species of size n. In addition, using simulations, we compare the performance of this algorithm when applied to NeighborNet output with that of FastME, a leading method for searching for minimum evolution trees in tree space. We find that, even though a circular set of splits represents just a tiny fraction of the total number of possible splits of a set, the trees obtained from circular sets compare quite favorably with those obtained with FastME, suggesting that the approach could warrant further investigation. © 2013 Elsevier B.V."



Marc Thuillard and
Didier FraixBurnet. Phylogenetic Trees and Networks Reduce to Phylogenies on Binary States: Does It Furnish an Explanation to the Robustness of Phylogenetic Trees against Lateral Transfers? In Evolutionary Bioinformatics, Vol. 11:213221, 2015. [Abstract] Keywords: circular split system, explicit network, from multistate characters, outerplanar, perfect, phylogenetic network, phylogeny, planar, polynomial, reconstruction, split. Note: http://dx.doi.org/10.4137%2FEBO.S28158.



Philippe Gambette,
Katharina Huber and
Guillaume Scholz. Bridging the gap between rooted and unrooted phylogenetic networks. In BMB, 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, to appear.



