Who is Who in Phylogenetic Networks

Publications related to 'split network' : a finite, simple, connected, bipartite graph is called a split network if there exists an isometric and surjective edge coloring: each set of edges of the same color is called a split, and all edges of the same split are drawn parallel in a representation of the network. The term "split network" should be prefered to splits graph to avoid confusion with the classical graph class.   Order by:   Type | Year
Only And Or     related to: --- abstract network agreement forest AIC approximation APX hard ARG bayesian BIC block realization bootstrap bound branch and bound branch length cactus graph characterization circular split system cluster containment clustering coalescent compressed network compression consensus consistency cophylogeny counting database distance between networks distinct-cluster network diversity duplication dynamic programming enumeration evaluation explicit network exponential algorithm flat FPT from binary characters from binets from clusters from continuous characters from distances from gene order from multilabeled tree from multistate characters from network from NGS data from quartets from rooted trees from sequences from species tree from splits from trees From tri-LGT-nets from trinets from triplets from unrooted trees FU-stable network galled network galled tree generation genetically stable network haplotype network haplotyping heuristic HMM hybridization identifiability inapproximability incomplete lineage sorting integer linear programming isomorphism k-reticulated kernelization labeling lateral gene transfer level k phylogenetic network LGT network likelihood lineage sorting loss LST distance MASN median network MedianJoining minimal lateral network minimum contradiction minimum number minimum spanning network model selection mrca network MSOL mu distance nearly-stable network NeighborNet nested network netting NNI distance normal network NP complete Number of vertices optimal realization outerplanar parsimony partly reduced networks pedigree perfect phylogenetic network phylogeny planar polynomial population genetics Program AdmixTools Program ALE Program Angst Program Arlequin Program ARTNET Program Beagle Program BIMLR Program Bio PhyloNetwork Program BMhyd Program Clustistic Program CMPT Program CombineTrees Program ConsensusNetwork Program constNJ Program CycleKiller Program Dendroscope Program EEEP Program FastHN Program FastNet Program FlatNJ Program Fylogenetica Program GalledTree Program GraphDTL Program HapBound Program HGT_simul Program HiDe Program HorizStory Program Hybrid-coal Program Hybrid-Lambda Program HybridInterleave Program HybridNET Program HybridNumber Program Hybroscale Program icelu-PhyloNetwork Program ILPEACE Program JML Program JPrIME-DLTRS Program LatTrans Program LEV1ATHAN Program Lev1Generator Program Level2 Program LGTnetwork Program lingpy Program LNetwork Program MaafB Program Marlon Program MC-Net Program McKiTscH Program Mowgli Program MowgliNNI Program MPNet Program MY CLOSURE Program Nepal Program NetGen Program NetTest Program NetView Program Network Program Notung Program PADRE Program Phangorn Program PhippsNetwork Program PhyloDAG Program PhyloNet Program PhyloNet-HMM Program PhyloNetwork Program PhyloNetworks SNaQ Program PIRN Program PopART Program Prunier Program Pyramids Program QNet Program Quartet Program Quartet Decomposition Program QuartetMethods Program QuartetNet Program QuasiDec Program QuickCass Program RANGER-DTL Program RecMin Program Recodon Program RecPars Program Reticlad Program SAGE Program SAQ-Net Program Serial NetEvolve Program SHRUB Program Simplistic Program Sliding MinPD Program SNSA Program Spectronet Program SplitsTree Program SPNet Program SPRDist Program SuperQ Program SylvX Program T REX Program TCS Program TERA Program TerminusEst Program Treeduce Program TreeFix-DTL Program TreeMix Program Treevolve Program TriLoNet Program TripNet Program ultra-Net Program Ultranet Program WeakHierarchies Program Xscape pseudo-polynomial pyramid quasi-median network realization recombination recombination detection reconstruction reduced networks regular network reticulation-visible network reticulogram serial evolutionary networks simulated annealing simulation site consistency software split split decomposition SPR distance spread stable-child network statistical model statistical parsimony supernetwork survey tanglegram TBR distance time consistent network tree child network tree containment tree containment. tree sibling network tree-based network tripartition distance triplet distance unicyclic network uniqueness visualization weak hierarchy weakly compatible
Associated keywords
abstract-network AIC approximation bayesian BIC characterization circular-split-system consensus diversity dynamic-programming evaluation explicit-network flat FPT from-clusters from-continuous-characters from-distances from-gene-order from-network from-quartets from-rooted-trees from-sequences from-splits from-trees from-triplets from-unrooted-trees galled-network galled-tree heuristic hybridization integer-linear-programming lateral-gene-transfer level-k-phylogenetic-network likelihood median-network minimum-contradiction NeighborNet netting NP-complete phylogenetic-network phylogeny planar polynomial Program-Arlequin Program-Beagle Program-Dendroscope Program-FlatNJ Program-MC-Net Program-Network Program-Phangorn Program-PhippsNetwork Program-Pyramids Program-QNet Program-Quartet Program-Quartet-Decomposition Program-Reticlad Program-SAQ-Net Program-SNSA Program-Spectronet Program-SplitsTree Program-SPNet Program-SuperQ Program-T-REX Program-TCS Program-WeakHierarchies pyramid recombination reconstruction reticulogram simulated-annealing software split split-decomposition split-network statistical-model supernetwork survey uniqueness visualization weak-hierarchy weakly-compatible
2017
1 Monika Balvociute, David Bryant and Andreas Spillner. When can splits be drawn in the plane? In SIAM Journal on Discrete Mathematics, Vol. 31(2):839-856, 2017.   Keywords: abstract network, characterization, flat, phylogenetic network, planar, split, split network. Note: http://arxiv.org/abs/1509.06104v1.         2 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.
2016
3 Satyan L. Devadoss and Samantha Petti. A Space of Phylogenetic Networks. 2016.   Keywords: circular split system, phylogenetic network, phylogeny, split network. Note: http://arxiv.org/abs/1607.06978.
2014
4 Monika Balvociute, Andreas Spillner and Vincent Moulton. FlatNJ: A Novel Network-Based Approach to Visualize Evolutionary and Biogeographical Relationships. In Systematic Biology, Vol. 63(3):383-396, 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, non-neutral 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 intra-locus 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."
2013
5 Stefan Grünewald, Andreas Spillner, Sarah Bastkowski, Anja Bögershausen and Vincent Moulton. SuperQ: Computing Supernetworks from Quartets. In TCBB, Vol. 10(1):151-160, 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 Z-closure and Q-imputation supernetwork methods, and also present an analysis of some published data sets as an illustration of its applicability. © 2004-2012 IEEE." 6 Alexey A. Morozov, Yuri P. Galachyants and Yelena V. Likhoshway. Inferring Phylogenetic Networks from Gene Order Data. In BMRI, Vol. 2013(503193):1-7, 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 Neighbor-Net algorithm). Binary encoding can also be useful, but only when the methods mentioned above cannot be used. © 2013 Alexey Anatolievich Morozov et al."
2012
7 Jeremy G. Sumner, Barbara R. Holland and Peter D. Jarvis. The algebra of the general Markov model on phylogenetic trees and networks. In BMB, Vol. 74(4):858-880, 2012.   Keywords: abstract network, phylogenetic network, phylogeny, split, split network, statistical model. Note: http://arxiv.org/abs/1012.5165.         Toggle abstract "It is known that the Kimura 3ST model of sequence evolution on phylogenetic trees can be extended quite naturally to arbitrary split systems. However, this extension relies heavily on mathematical peculiarities of the associated Hadamard transformation, and providing an analogous augmentation of the general Markov model has thus far been elusive. In this paper, we rectify this shortcoming by showing how to extend the general Markov model on trees to include incompatible edges; and even further to more general network models. This is achieved by exploring the algebra of the generators of the continuous-time Markov chain together with the "splitting" operator that generates the branching process on phylogenetic trees. For simplicity, we proceed by discussing the two state case and then show that our results are easily extended to more states with little complication. Intriguingly, upon restriction of the two state general Markov model to the parameter space of the binary symmetric model, our extension is indistinguishable from the Hadamard approach only on trees; as soon as any incompatible splits are introduced the two approaches give rise to differing probability distributions with disparate structure. Through exploration of a simple example, we give an argument that our extension to more general networks has desirable properties that the previous approaches do not share. In particular, our construction allows for convergent evolution of previously divergent lineages; a property that is of significant interest for biological applications. © 2011 Society for Mathematical Biology." 8 Andreas W. M. Dress, Katharina Huber, Jacobus Koolen, Andreas Spillner and Vincent Moulton. An Introduction to Phylogenetic Combinatorics. Cambridge University Press, 2012.   Keywords: phylogenetic network, split network, survey. Note: http://www.amazon.fr/Basic-Phylogenetic-Combinatorics-Andreas-Dress/dp/0521768322.         9 Andreas Spillner and Vincent Moulton. Optimal algorithms for computing edge weights in planar split-networks. In Journal of Applied Mathematics and Computing, Vol. 39(1-2):1-13, 2012.   Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://dx.doi.org/10.1007/s12190-011-0506-z.         Toggle abstract "In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graph-theoretical 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 split-networks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outer-labeled 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 split-networks. © 2011 Korean Society for Computational and Applied Mathematics." 10 Magnus Bordewich and Charles Semple. Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. In JOMB, Vol. 64(1):69-85, 2012.   Keywords: abstract network, approximation, diversity, phylogenetic network, polynomial, split network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS11.pdf.         Toggle abstract "Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1-1/e)-approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1-1/e)-approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al. © 2011 Springer-Verlag." 11 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):123-127, 2012.   Keywords: abstract network, from quartets, heuristic, phylogenetic network, phylogeny, Program SAQ-Net, 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, SAQ-Net, as a method for constructing phylogenetic networks from weighted quartets. Similar to QNet algorithm, SAQ-Net constructs a collection of circular weighted splits of the taxa set. This collection is represented by a split network. In order to show that SAQ-Net 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 SAQ-Net produces a better circular ordering and phylogenetic networks than QNet in most cases. SAQ-Net has been implemented in Matlab and is available for download at http://bioinf.cs.ipm.ac.ir/softwares/saq.net. © 2011 Elsevier Inc." 12 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.archives-ouvertes.fr/hal-00678046/en/.         Toggle abstract "Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press." 13 Reza Hassanzadeh, Changiz Eslahchi and Wing-Kin Sung. Constructing phylogenetic supernetworks based on simulated annealing. In MPE, Vol. 63(3):738-744, 2012.   Keywords: abstract network, from unrooted trees, heuristic, phylogenetic network, phylogeny, Program SNSA, reconstruction, simulated annealing, software, split network. Note: http://dx.doi.org/10.1016/j.ympev.2012.02.009.         Toggle abstract Different partial phylogenetic trees can be derived from different sources of evidence and different methods. One important problem is to summarize these partial phylogenetic trees using a supernetwork. We propose a novel simulated annealing based method called SNSA which uses an optimization function to produce a simple network that still retains a great deal of phylogenetic information. We report the performance of this new method on real and simulated datasets. © 2012 Elsevier Inc. 14 Cayla McBee. Generalizing Fourier Calculus on Evolutionary Trees to Splits Networks. In ISPAN'12, Pages 149-155, 2012.   Keywords: abstract network, from sequences, phylogenetic network, phylogeny, split network, statistical model.         Toggle abstract "Biologists have been interested in Phylogenetics, the study of evolutionary relatedness among various groups of organisms, for more than 140 years. In spite of this, it has only been in the last 40 years that advances in technology and the availability of DNA sequences have led to statistical, computational and algorithmic work on determining evolutionary relatedness between organisms. One method of determining historical relationships between organisms is to assume a group based evolutionary model and use a discrete Fourier transform. The 1993 paper 'Fourier Calculus on Evolutionary Trees' by L.A. Szekely, M.A. Steel and P.L. Erdos outlines this process. The transform presented in Szekely et al provides an invertible relationship between phylogenetic trees and expected frequencies of nucleotide patterns in nucleotide sequences. This implies that given a set of nucleotide sequences from various organisms it is possible to construct a phylogenetic tree that represents the historical relationships of those organisms. Some scenarios are poorly described by phylogenetic trees and there are biological and statistical reasons for using networks to model phylogenetic relationships. Given this motivation I have generalized Szekely et al's result to apply to a specific type of phylogenetic network known as a splits network. © 2012 IEEE." 15 Fenglou Mao, David Williams, Olga Zhaxybayeva, Maria S. Poptsova, Pascal Lapierre, J. Peter Gogarten and Ying Xu. Quartet decomposition server: a platform for analyzing phylogenetic trees. In BMCB, Vol. 13:123, 2012.   Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program Quartet Decomposition, reconstruction, software, split network.         Toggle abstract "Background: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes.Results: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu.Conclusions: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts. © 2012 Mao et al.; licensee BioMed Central Ltd." 16 Donovan H. Parks and Robert G. Beiko. Measuring Community Similarity with Phylogenetic Networks. In MBE, Vol. 29(12):3947-3958, 2012.   Keywords: abstract network, diversity, phylogenetic network, phylogeny, split network. Note: poster available at http://dparks.wdfiles.com/local--files/publications/SMBE_BetaDiversity_2011.pdf.         Toggle abstract "Environmental drivers of biodiversity can be identified by relating patterns of community similarity to ecological factors. Community variation has traditionally been assessed by considering changes in species composition and more recently by incorporating phylogenetic information to account for the relative similarity of taxa. Here, we describe how an important class of measures including Bray-Curtis, Canberra, and UniFrac can be extended to allow community variation to be computed on a phylogenetic network. We focus on phylogenetic split systems, networks that are produced by the widely used median network and neighbor-net methods, which can represent incongruence in the evolutionary history of a set of taxa. Calculating β diversity over a split system provides a measure of community similarity averaged over uncertainty or conflict in the available phylogenetic signal. Our freely available software, Network Diversity, provides 11 qualitative (presence-absence, unweighted) and 14 quantitative (weighted) network-based measures of community similarity that model different aspects of community richness and evenness. We demonstrate the broad applicability of network-based diversity approaches by applying them to three distinct data sets: pneumococcal isolates from distinct geographic regions, human mitochondrial DNA data from the Indonesian island of Nias, and proteorhodopsin sequences from the Sargasso and Mediterranean Seas. Our results show that major expected patterns of variation for these data sets are recovered using network-based measures, which indicates that these patterns are robust to phylogenetic uncertainty and conflict. Nonetheless, network-based measures of community similarity can differ substantially from measures ignoring phylogenetic relationships or from tree-based measures when incongruent signals are present in the underlying data. Network-based measures provide a methodology for assessing the robustness of β-diversity results in light of incongruent phylogenetic signal and allow β diversity to be calculated over widely used network structures such as median networks. © 2012 The Author 2012."
2011
17 Dan Levy and Lior Pachter. The Neighbor-Net Algorithm. In Advances in Applied Mathematics, Vol. 47(2):240-258, 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 neighbor-joining algorithm is a popular phylogenetics method for constructing trees from dissimilarity maps. The neighbor-net algorithm is an extension of the neighbor-joining algorithm and is used for constructing split networks. We begin by describing the output of neighbor-net in terms of the tessellation of M̄0n(R) by associahedra. This highlights the fact that neighbor-net outputs a tree in addition to a circular ordering and we explain when the neighbor-net tree is the neighbor-joining tree. A key observation is that the tree constructed in existing implementations of neighbor-net is not a neighbor-joining tree. Next, we show that neighbor-net is a greedy algorithm for finding circular split systems of minimal balanced length. This leads to an interpretation of neighbor-net as a greedy algorithm for the traveling salesman problem. The algorithm is optimal for Kalmanson matrices, from which it follows that neighbor-net 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." 18 Klaus Schliep. Phangorn: Phylogenetic analysis in R. In Bioinformatics, Vol. 27(4):592-593, 2011.   Keywords: abstract network, from distances, phylogenetic network, Program Phangorn, software, split, split network. Note: http://dx.doi.org/10.1093/bioinformatics/btq706.         Toggle abstract "Summary: phangorn is a package for phylogenetic reconstruction and analysis in the R language. Previously it was only possible to estimate phylogenetic trees with distance methods in R. phangorn, now offers the possibility of reconstructing phylogenies with distance based methods, maximum parsimony or maximum likelihood (ML) and performing Hadamard conjugation. Extending the general ML framework, this package provides the possibility of estimating mixture and partition models. Furthermore, phangorn offers several functions for comparing trees, phylogenetic models or splits, simulating character data and performing congruence analyses. © The Author(s) 2010. Published by Oxford University Press." 19 Paul Phipps. Planar phylogenetic network optimization. PhD thesis, University of Texas at Dallas, U.S.A., 2011.   Keywords: abstract network, from distances, phylogenetic network, Program PhippsNetwork, split, split network. Note: http://proquest.umi.com/pqdlink?did=2337197411&Fmt=7&clientId=176295&RQT=309&VName=PQD.         20 Alethea Rea. Statistical approaches to phylogenetic networks, recombination and testing of incongruence. PhD thesis, The University of Auckland, New Zealand, 2011.   Keywords: abstract network, AIC, BIC, phylogenetic network, phylogeny, split, split network, statistical model. Note: https://researchspace.auckland.ac.nz/handle/2292/67624.         21 Changiz Eslahchi and Reza Hassanzadeh. New Algorithm for Constructing Supernetworks from Partial Trees. In MCCMB11, Pages 106-107, 2011.   Keywords: abstract network, from unrooted trees, heuristic, phylogenetic network, phylogeny, Program SNSA, reconstruction, simulated annealing, split network. Note: http://mccmb.belozersky.msu.ru/2011/mccmb11.pdf#page=106.
2010
22 Robert G. Beiko. Gene sharing and genome evolution: networks in trees and trees in networks. In Biology and Philosophy, Vol. 25(4):659-673, 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/s10539-010-9217-3.         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 within-species 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 tree-thinking 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." 23 Changiz Eslahchi, Mahnaz Habibi, Reza Hassanzadeh and Ehsan Mottaghi. MC-Net: a method for the construction of phylogenetic networks based on the Monte-Carlo method. In BMCEB, Vol. 10:254, 2010.   Keywords: abstract network, circular split system, from distances, heuristic, phylogenetic network, Program MC-Net, Program SplitsTree, software, split, split network. Note: http://dx.doi.org/10.1186/1471-2148-10-254.         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 Neighbor-Net (N-Net) is a distance-based method. The N-Net 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 NP-hard problem. The N-Net is a heuristic algorithm to find the optimal circular ordering which is based on neighbor-joining algorithm. Results. In this paper, we present a heuristic algorithm to find an optimal circular ordering based on the Monte-Carlo method, called MC-Net algorithm. In order to show that MC-Net performs better than N-Net, 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 MC-Net is closer to optimal circular ordering than the N-Net. Furthermore, the networks corresponding to outputs of MC-Net made by SplitsTree are simpler than N-Net. © 2010 Eslahchi et al; licensee BioMed Central Ltd." 24 Philippe Gambette. Méthodes combinatoires de reconstruction de réseaux phylogénétiques. PhD thesis, Université Montpellier 2, France, 2010.   Keywords: abstract network, characterization, circular split system, explicit network, FPT, from clusters, from triplets, integer linear programming, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, Program Dendroscope, pyramid, reconstruction, split network, weak hierarchy. Note: http://tel.archives-ouvertes.fr/tel-00608342/en/.         25 Binh T. Nguyen. Novel Split-Based 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.
2009
26 Stefan Grünewald, Katharina Huber, Vincent Moulton, Charles Semple and Andreas Spillner. Characterizing weak compatibility in terms of weighted quartets. In Advances in Applied Mathematics, Vol. 42(3):329-341, 2009.   Keywords: abstract network, characterization, from quartets, split network, weak hierarchy. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/GHMSS08.pdf, slides at http://www.lirmm.fr/miep08/slides/12_02_huber.pdf.         27 Klaus Schliep. Some applications of statistical phylogenetics. PhD thesis, Massey University, New Zealand, 2009.   Keywords: abstract network, phylogenetic network, Program Phangorn, reconstruction, split network. Note: http://muir.massey.ac.nz/handle/10179/931.         28 Marc Thuillard and Didier Fraix-Burnet. Phylogenetic Applications of the Minimum Contradiction Approach on Continuous Characters. In Evolutionary Bioinformatics, Vol. 5:53-46, 2009.   Keywords: from continuous characters, minimum contradiction, phylogenetic network, phylogeny, split, split network. Note: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2747132/.         29 Bui Quang Minh, Steffen Klaere and Arndt von Haeseler. Taxon Selection under Split Diversity. In Systematic Biology, Vol. 58(6):586-594, 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 NP-hard. 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." 30 Bui Quang Minh, Fabio Pardi, Steffen Klaere and Arndt von Haeseler. Budgeted Phylogenetic Diversity on Circular Split Systems. In TCBB, Vol. 6(1):22-29, 2009.   Keywords: abstract network, circular split system, dynamic programming, from network, phylogenetic network, polynomial, split, split network. Note: http://dx.doi.org/10.1109/TCBB.2008.54.         Toggle abstract "In the last 15 years, Phylogenetic Diversity (PD) has gained interest in the community of conservation biologists as a surrogate measure for assessing biodiversity. We have recently proposed two approaches to select taxa for maximizing PD, namely PD with budget constraints and PD on split systems. In this paper, we will unify these two strategies and present a dynamic programming algorithm to solve the unified framework of selecting taxa with maximal PD under budget constraints on circular split systems. An improved algorithm will also be given if the underlying split system is a tree. © 2006 IEEE." 31 Qiong Wu. Phylogenetic Networks: New Constructions and Applications. PhD thesis, Université of East Anglia, U.K., 2009.   Keywords: abstract network, phylogenetic network, phylogeny, reconstruction, split network. Note: http://ethos.bl.uk/OrderDetails.do?did=1&uin=uk.bl.ethos.514315.         32 Lichen Bao. Phylogenetic network construction and the application. PhD thesis, University of Texas at Dallas, U.S.A., 2009.   Keywords: from distances, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://proquest.umi.com/pqdlink?did=1952801881&sid=1&Fmt=6&clientId=176295&RQT=309&VName=PQD.         33 Vincent Moulton and Katharina Huber. Split Networks. A tool for exploring complex evolutionary relationships in molecular data. In Philippe Lemey, Marco Salemi and Anne-Mieke Vandamme editors, The Phylogenetic Handbook, Cambridge University Press, 2009.   Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network.
2008
34 Philippe Gambette and Daniel H. Huson. Improved Layout of Phylogenetic Networks. In TCBB, Vol. 5(3):472-479, 2008.   Keywords: abstract network, heuristic, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00309694/en/.         Toggle abstract "Split networks are increasingly being used in phylogenetic analysis. Usually, a simple equal-angle 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 equal-daylight algorithm to networks, looks into using a spring embedder, and discusses how to construct rooted split networks. © 2008 IEEE." 35 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/1471-2148-8-22.         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." 36 James B. Whitfield, Sydney A. Cameron, Daniel H. Huson and Mike Steel. Filtered Z-Closure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees. In Systematic Biology, Vol. 57(6):939-947, 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%20Z-closure%20SystBiol.pdf.         37 Tobias Kloepper. Algorithms for the Calculation and Visualisation of Phylogenetic Networks. PhD thesis, Eberhard-Karls-Universitä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: http://tobias-lib.ub.uni-tuebingen.de/volltexte/2008/3336/.         38 Stefan Grünewald, Andreas Spillner, Kristoffer Forslund and Vincent Moulton. Constructing Phylogenetic Supernetworks from Quartets. In WABI08, Vol. 5251:284-295 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/978-3-540-87361-7_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 Springer-Verlag Berlin Heidelberg."
2007
39 Barbara R. Holland, Glenn Conner, Katharina Huber and Vincent Moulton. Imputing Supertrees and Supernetworks from Quartets. In Systematic Biology, Vol. 56(1):57-67, 2007.   Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program Quartet, reconstruction, split network, supernetwork. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.3215.         Toggle abstract "Inferring species phylogenies is an important part of understanding molecular evolution. Even so, it is well known that an accurate phylogenetic tree reconstruction for a single gene does not always necessarily correspond to the species phylogeny. One commonly accepted strategy to cope with this problem is to sequence many genes; the way in which to analyze the resulting collection of genes is somewhat more contentious. Supermatrix and supertree methods can be used, although these can suppress conflicts arising from true differences in the gene trees caused by processes such as lineage sorting, horizontal gene transfer, or gene duplication and loss. In 2004, Huson et al. (IEEE/ACM Trans. Comput. Biol. Bioinformatics 1:151-158) presented the Z-closure method that can circumvent this problem by generating a supernetwork as opposed to a supertree. Here we present an alternative way for generating supernetworks called Q-imputation. In particular, we describe a method that uses quartet information to add missing taxa into gene trees. The resulting trees are subsequently used to generate consensus networks, networks that generalize strict and majority-rule consensus trees. Through simulations and application to real data sets, we compare Q-imputation to the matrix representation with parsimony (MRP) supertree method and Z-closure, and demonstrate that it provides a useful complementary tool. Copyright © Society of Systematic Biologists." 40 Daniel H. Huson. Split networks and Reticulate Networks. In Olivier Gascuel and Mike Steel editors, Reconstructing Evolution, New Mathematical and Computational Advances, Pages 247-276, 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://www-ab.informatik.uni-tuebingen.de/research/phylonets/GCB2006.pdf.         41 Yuanyi Zhang. Optimization Algorithms for Phylogenetic Networks. PhD thesis, University of Texas at Dallas, U.S.A., 2007.   Keywords: abstract network, explicit network, from distances, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://proquest.umi.com/pqdlink?did=1421626541&sid=1&Fmt=6&clientId=176295&RQT=309&VName=PQD.
2006
42 Vladimir Makarenkov, Dmytro Kevorkov and Pierre Legendre. Phylogenetic Network Construction Approaches. In Applied Mycology and Biotechnology, Vol. 6:61-97, 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.
2005
43 Sergey Bereg and Kathryn Bean. Constructing Phylogenetic Networks from Trees. In BIBE05, Pages 299-305, 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. 44 Daniel H. Huson, Tobias Kloepper, Peter J. Lockhart and Mike Steel. Reconstruction of Reticulate Networks from Gene Trees. In RECOMB05, Vol. 3500:233-249 of LNCS, springer, 2005.   Keywords: from rooted trees, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://dx.doi.org/10.1007/11415770_18.         45 Richard C. Winkworth, David Bryant, Peter J. Lockhart, David Havell and Vincent Moulton. Biogeographic Interpretation of Splits Graphs: Least Squares Optimization of Branch Lengths. In Systematic Biology, Vol. 54(1):56-65, 2005.   Keywords: abstract network, from distances, from network, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://www.math.auckland.ac.nz/~bryant/Papers/05Biogeographic.pdf.         46 David Bryant. Extending tree models to splits networks. In Lior Pachter and Bernd Sturmfels editors, Algebraic Statistics for Computational Biology, Pages 322-334, Cambridge University Press, 2005.   Keywords: abstract network, from splits, likelihood, phylogenetic network, phylogeny, split, split network, statistical model. Note: http://www.math.auckland.ac.nz/~bryant/Papers/05ascbChapter.pdf.
2004
47 David Bryant and Vincent Moulton. NeighborNet: An Agglomerative Method for the Construction of Phylogenetic Networks. In MBE, Vol. 21(2):255-265, 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 Neighbor-Net, a distance based method for constructing phylogenetic networks that is based on the Neighbor-Joining (NJ) algorithm of Saitou and Nei. Neighbor-Net provides a snapshot of the data that can guide more detailed analysis. Unlike split decomposition, Neighbor-Net 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 multi-locus 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. Neighbor-Net is available as part of the SplitsTree4 software package." 48 Andreas W. M. Dress and Daniel H. Huson. Constructing splits graphs. In TCBB, Vol. 1(3):109-115, 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 one-to-one 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, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called 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."
2003
49 Daniel H. Huson. What If I Don't Have a Tree? Split Decomposition and Related Models. In Current Protocols in Bioinformatics, Vol. Unit 6.7, 2003.   Keywords: abstract network, phylogenetic network, Program SplitsTree, software, split decomposition, split network. Note: http://dx.doi.org/10.1002/0471250953.bi0607s01.
2002
50 David Bryant and Vincent Moulton. Neighbor-Net: An Agglomerative Method for the Construction of Planar Phylogenetic Networks. In WABI02, Vol. 2452:375-391 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/3-540-45784-4_28.
2000
51 François-Joseph Lapointe. How to account for reticulation events in phylogenetic analysis: A review of distance-based methods. In Journal of Classification, Vol. 17:175-184, 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.         52 Korbinian Strimmer and Vincent Moulton. Likelihood Analysis of Phylogenetic Networks Using Directed Graphical Models. In MBE, Vol. 17(6):875-881, 2000.   Keywords: bayesian, likelihood, median network, split network, statistical model. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/17/6/875.
1999
53 Vincent Berry and David Bryant. Faster reliable phylogenetic analysis. In RECOMB99, Pages 59-68, 1999.   Keywords: abstract network, from quartets, phylogenetic network, phylogeny, polynomial, Program SplitsTree, reconstruction, split network, weakly compatible. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9151.
1998
54 Daniel H. Huson. SplitsTree: analyzing and visualizing evolutionary data. In BIO, Vol. 14(1):68-73, 1998.   Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, split network. Note: http://bioweb.pasteur.fr/docs/doc-gensoft/splitstree/splitstree.ps.
1996
55 Andreas W. M. Dress, Daniel H. Huson and Vincent Moulton. Analyzing and visualizing distance data using SplitsTree. In DAM, Vol. 71(1):95-109, 1996.   Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://bibiserv.techfak.uni-bielefeld.de/splits/splits.pdf.
1995
56 Daniel H. Huson and Rainer Wetzel. Analyzing and visualizing sequence and distance data with SplitsTree V1.0.2. 1995.   Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, software, split network, visualization. Note: Technical report, http://citeseer.ist.psu.edu/173442.html.
1993
57 Joaquin Dopazo, Andreas W. M. Dress and Arndt von Haeseler. Split decomposition: a new technique to analyse viral evolution. In PNAS, Vol. 90:10320-10324, 1993.   Keywords: abstract network, phylogenetic network, phylogeny, split, split decomposition, split network, visualization. Note: http://dx.doi.org/10.1073/pnas.90.21.10320.
1992
58 Hans-Jürgen Bandelt and Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. In Advances in Mathematics, Vol. 92(1):47-105, 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 split-decomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally split-decomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally split-decomposable metric and a split-prime 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 four-point subset all three splits with block size two. © 1992." 59 Hans-Jürgen Bandelt and Andreas W. M. Dress. Split Decomposition: A new and useful approach to phylogenetic analysis of distance data. In MPE, Vol. 1(3):242-252, 1992.   Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split decomposition, split network. Note: http://dx.doi.org/10.1016/1055-7903(92)90021-8.         Toggle abstract "In order to analyze the structure inherent to a matrix of dissimilarities (such as evolutionary distances) we propose to use a new technique called split decomposition. This method accurately dissects the given dissimilarity measure as a sum of elementary "split" metrics plus a (small) residue. The split summands identify related groups which are susceptible to further interpretation when casted against the available biological information. Reanalysis of previously published ribosomal RNA data sets using split decomposition illustrate the potential of this approach. © 1992."