Who is Who in Phylogenetic Networks

Publications related to 'abstract network' : An abstract network reflects some phylogenetic signals rather than explicitely displaying biological reticulation events. Split networks are classical examples of abstract phylogenetic networks. The contrary of abstract is explicit, and abstract networks are sometimes called implicit.   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network AIC approximation BIC block-realization cactus-graph characterization circular-split-system cluster-containment clustering consensus consistency distance-between-networks diversity dynamic-programming evaluation explicit-network flat FPT from-clusters from-distances from-gene-order from-network from-NGS-data from-quartets from-rooted-trees from-sequences from-splits from-trees from-triplets from-unrooted-trees galled-network galled-tree haplotype-network heuristic hybridization integer-linear-programming isomorphism level-k-phylogenetic-network likelihood median-network MedianJoining minimum-spanning-network NeighborNet NP-complete optimal-realization orientation parsimony phylogenetic-network phylogeny planar polynomial population-genetics Program-Arlequin Program-Beagle Program-CombineTrees Program-Dendroscope Program-FlatNJ Program-Fylogenetica Program-MC-Net Program-MY-CLOSURE Program-Network Program-Phangorn Program-PhippsNetwork Program-PhyloNet Program-PhyloNetworks-SNaQ Program-PopART Program-Pyramids Program-QNet Program-Quartet Program-Quartet-Decomposition Program-QuartetMethods Program-QuartetNet Program-QuasiDec Program-SAQ-Net Program-SHRUB Program-SNSA Program-Spectronet Program-SplitsTree Program-SPNet Program-SuperQ Program-T-REX Program-TCS Program-Ultranet Program-WeakHierarchies pyramid quasi-median-network realization recombination reconstruction regular-network reticulogram simulated-annealing simulation software split split-decomposition split-network statistical-model supernetwork survey tree-sibling-network unicyclic-network visualization weak-hierarchy weakly-compatible

Article (Journal)

1 Hans-Jürgen Bandelt and Andreas W. M. Dress. Weak hierarchies associated with similarity measures: an additive clustering technique. In BMB, Vol. 51:113-166, 1989. Keywords: abstract network, clustering, from distances, from trees, phylogenetic network, phylogeny, Program WeakHierarchies, reconstruction, weak hierarchy. Note: http://dx.doi.org/10.1007/BF02458841.         Toggle abstract "A new and apparently rather useful and natural concept in cluster analysis is studied: given a similarity measure on a set of objects, a sub-set is regarded as a cluster if any two objects a, b inside this sub-set have greater similarity than any third object outside has to at least one of a, b. These clusters then form a closure system which can be described as a hypergraph without triangles. Conversely, given such a system, one may attach some weight to each cluster and then compose a similarity measure additively, by letting the similarity of a pair be the sum of weights of the clusters containing that particular pair. The original clusters can be reconstructed from the obtained similarity measure. This clustering model is thus located between the general additive clustering model of Shepard and Arabie (1979) and the standard hierarchical model. Potential applications include fitting dendrograms with few additional nonnested clusters and simultaneous representation of some families of multiple dendrograms (in particular, two-dendrogram solutions), as well as assisting the search for phylogenetic relationships by proposing a somewhat larger system of possibly relevant "family groups", from which an appropriate choice (based on additional insight or individual preferences) remains to be made. © 1989 Society for Mathematical Biology." 2 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." 3 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." 4 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.         5 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.         6 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." 7 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." 8 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):532-538, 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 distance-based Neighbor-Net (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 character-based approach is preferred. Moreover, it can be used as an aid for determining when a quartet-based tree-building 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." 9 Stefan Grünewald, Katharina Huber and Qiong Wu. Two novel closure rules for constructing phylogenetic super-networks. In BMB, Vol. 70(7):1906-1924, 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 (leaf-labeled 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 Z-closure super-network approach, which is based on the Z-closure rule, and the Q-imputation 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 M-rule) 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 Y-rule and also reanalyze an Arabidopsis thaliana data set. © 2008 Society for Mathematical Biology." 10 Stefan Grünewald, Vincent Moulton and Andreas Spillner. Consistency of the QNet algorithm for generating planar split networks from weighted quartets. In DAM, Vol. 157(10):2325-2334, 2009. Keywords: abstract network, consistency, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software. Note: http://dx.doi.org/10.1016/j.dam.2008.06.038.         Toggle abstract "Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or "QNet" method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method. © 2008 Elsevier B.V. All rights reserved." 11 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." 12 Daniel H. Huson, Tobias Dezulian, Tobias Kloepper and Mike Steel. Phylogenetic Super-Networks from Partial Trees. In TCBB, Vol. 1(4):151-158, 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 super-network from such data and provides an efficient algorithm for doing so, called the Z-closure 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 plug-in for the program SplitsTree4. © 2004 IEEE." 13 Katharina Huber, Vincent Moulton, Peter J. Lockhart and Andreas W. M. Dress. Pruned Median Networks: A Technique for Reducing the Complexity of Median Networks. In MPE, Vol. 19(2):302-310, 2001. Keywords: abstract network, median network, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1006/mpev.2001.0935.         Toggle abstract "Observations from molecular marker studies on recently diverged species indicate that substitution patterns in DNA sequences can often be complex and poorly described by tree-like bifurcating evolutionary models. These observations might result from processes of species diversification and/or processes of sequence evolution that are not tree-like. In these cases, bifurcating tree representations provide poor visualization of phylogenetic signals in sequence data. In this paper, we use median networks to study DNA sequence substitution patterns in plant nuclear and chloroplast markers. We describe how to prune median networks to obtain so called pruned median networks. These simpler networks may help to provide a useful framework for investigating the phylogenetic complexity of recently diverged taxa with hybrid origins. © 2001 Academic Press." 14 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.         15 Daniel H. Huson and David Bryant. Application of Phylogenetic Networks in Evolutionary Studies. In MBE, Vol. 23(2):254-267, 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 tree-like 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." 16 Martyn Kennedy, Barbara R. Holland, Russel D. Gray and Hamish G. Spencer. Untangling Long Branches: Identifying Conflicting Phylogenetic Signals Using Spectral Analysis, Neighbor-Net, and Consensus Networks. In Systematic Biology, Vol. 54(4):620-633, 2005. Keywords: abstract network, consensus, NeighborNet, phylogenetic network, phylogeny. Note: http://awcmee.massey.ac.nz/people/bholland/pdf/Kennedy_etal_2005.pdf.         17 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.         18 Vladimir Makarenkov and Pierre Legendre. From a phylogenetic tree to a reticulated network. In JCB, Vol. 11(1):195-212, 2004. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program T REX, reticulogram. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/article_JCB2004.pdf.         19 Andreas Spillner, Binh T. Nguyen and Vincent Moulton. Computing phylogenetic diversity for split systems. In TCBB, Vol. 5(2):235-244, 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 NP-hard. 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." 20 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.         21 David Bryant, Vincent Moulton and Andreas Spillner. Consistency of the Neighbor-Net Algorithm. In AMB, Vol. 2(8), 2007. Keywords: abstract network, consistency, from distances, NeighborNet. Note: http://dx.doi.org/10.1186/1748-7188-2-8.         Toggle abstract "Background: Neighbor-Net is a novel method for phylogenetic analysis that is currently being widely used in areas such as virology, bacteriology, and plant evolution. Given an input distance matrix, Neighbor-Net produces a phylogenetic network, a generalization of an evolutionary or phylogenetic tree which allows the graphical representation of conflicting phylogenetic signals. Results: In general, any network construction method should not depict more conflict than is found in the data, and, when the data is fitted well by a tree, the method should return a network that is close to this tree. In this paper we provide a formal proof that Neighbor-Net satisfies both of these requirements so that, in particular, Neighbor-Net is statistically consistent on circular distances. © 2007 Bryant et al; licensee BioMed Central Ltd." 22 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved." 23 Katharina Huber, Elizabeth E. Watson and Mike Hendy. An Algorithm for Constructing Local Regions in a Phylogenetic Network. In MPE, Vol. 19(1):1-8, 2000. Keywords: abstract network, median network, phylogenetic network, phylogeny, reconstruction, split. Note: http://dx.doi.org/10.1006/mpev.2000.0891.         Toggle abstract "The groupings of taxa in a phylogenetic tree cannot represent all the conflicting signals that usually occur among site patterns in aligned homologous genetic sequences. Hence a tree-building program must compromise by reporting a subset of the patterns, using some discriminatory criterion. Thus, in the worst case, out of possibly a large number of equally good trees, only an arbitrarily chosen tree might be reported by the tree-building program as" The Tree." This tree might then be used as a basis for phylogenetic conclusions. One strategy to represent conflicting patterns in the data is to construct a network. The Buneman graph is a theoretically very attractive example of such a network. In particular, a characterization for when this network will be a tree is known. Also the Buneman graph contains each of the most parsimonious trees indicated by the data. In this paper we describe a new method for constructing the Buneman graph that can be used for a generalization of Hadamard conjugation to networks. This new method differs from previous methods by allowing us to focus on local regions of the graph without having to first construct the full graph. The construction is illustrated by an example. © 2001 Academic Press." 24 Andreas W. M. Dress, Mike Hendy, Katharina Huber and Vincent Moulton. On the number of vertices and edges in the Buneman graph. In ACOM, Vol. 1:329-337, 1997. Keywords: abstract network, median network, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1007/BF02558484.         25 Insa Cassens, Patrick Mardulyn and Michel C. Milinkovitch. Evaluating Intraspecific Network Construction Methods Using Simulated Sequence Data: Do Existing Algorithms Outperform the Global Maximum Parsimony Approach? In Systematic Biology, Vol. 54(3):363-372, 2005. Keywords: abstract network, evaluation, from unrooted trees, haplotype network, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program TCS, reconstruction, software. Note: http://www.lanevol.org/LANE/publications_files/Cassens_etal_SystBio_2005.pdf.         26 Andreas W. M. Dress, Katharina Huber, Jacobus Koolen and Vincent Moulton. Compatible decompositions and block realizations of finite metrics. In EJC, Vol. 29(7):1617-1633, 2008. Keywords: abstract network, block realization, from distances, phylogenetic network, phylogeny, realization, reconstruction. Note: http://www.ims.nus.edu.sg/preprints/2007-21.pdf.         Toggle abstract "Given a metric D defined on a finite set X, we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in RX × X), D = ∑d ∈ D d holds, and there exist points x, x′ ∈ X for any two distinct metrics d, d′ in D such that d (x, y) d′ (x′, y) = 0 holds for every y ∈ X. In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d ∈ D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers. © 2007 Elsevier Ltd. All rights reserved." 27 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." 28 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, neighbor-net, simulated history recombination upper bound, median-joining, reduced median joining and minimum spanning network) compared to standard tree approaches (neighbor-joining 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." 29 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.         30 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.         31 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.         32 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. The comparison of tree-sibling time consistent phylogenetic networks is graph-isomorphism complete. In The Scientific World Journal, Vol. 2014(254279):1-6, 2014. Keywords: abstract network, distance between networks, from network, isomorphism, phylogenetic network, tree sibling network. Note: http://arxiv.org/abs/0902.4640.         Toggle abstract "Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time. © 2014 Gabriel Cardona et al." 33 Sarah C. Ayling and Terence A. Brown. Novel methodology for construction and pruning of quasi-median networks. In BMCB, Vol. 9:115, 2009. Keywords: abstract network, from sequences, median network, phylogenetic network, phylogeny, quasi-median network, reconstruction. Note: http://dx.doi.org/10.1186/1471-2105-9-115.         Toggle abstract "BACKGROUND: Visualising the evolutionary history of a set of sequences is a challenge for molecular phylogenetics. One approach is to use undirected graphs, such as median networks, to visualise phylogenies where reticulate relationships such as recombination or homoplasy are displayed as cycles. Median networks contain binary representations of sequences as nodes, with edges connecting those sequences differing at one character; hypothetical ancestral nodes are invoked to generate a connected network which contains all most parsimonious trees. Quasi-median networks are a generalisation of median networks which are not restricted to binary data, although phylogenetic information contained within the multistate positions can be lost during the preprocessing of data. Where the history of a set of samples contain frequent homoplasies or recombination events quasi-median networks will have a complex topology. Graph reduction or pruning methods have been used to reduce network complexity but some of these methods are inapplicable to datasets in which recombination has occurred and others are procedurally complex and/or result in disconnected networks. RESULTS: We address the problems inherent in construction and reduction of quasi-median networks. We describe a novel method of generating quasi-median networks that uses all characters, both binary and multistate, without imposing an arbitrary ordering of the multistate partitions. We also describe a pruning mechanism which maintains at least one shortest path between observed sequences, displaying the underlying relations between all pairs of sequences while maintaining a connected graph. CONCLUSION: Application of this approach to 5S rDNA sequence data from sea beet produced a pruned network within which genetic isolation between populations by distance was evident, demonstrating the value of this approach for exploration of evolutionary relationships." 34 Mark A. Ragan. Trees and networks before and after Darwin. In Biology Direct, Vol. 4(43), 2009. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, survey, visualization. Note: http://dx.doi.org/10.1186/1745-6150-4-43.         Toggle abstract "It is well-known that Charles Darwin sketched abstract trees of relationship in his 1837 notebook, and depicted a tree in the Origin of Species (1859). Here I attempt to place Darwin's trees in historical context. By the mid-Eighteenth century the Great Chain of Being was increasingly seen to be an inadequate description of order in nature, and by about 1780 it had been largely abandoned without a satisfactory alternative having been agreed upon. In 1750 Donati described aquatic and terrestrial organisms as forming a network, and a few years later Buffon depicted a network of genealogical relationships among breeds of dogs. In 1764 Bonnet asked whether the Chain might actually branch at certain points, and in 1766 Pallas proposed that the gradations among organisms resemble a tree with a compound trunk, perhaps not unlike the tree of animal life later depicted by Eichwald. Other trees were presented by Augier in 1801 and by Lamarck in 1809 and 1815, the latter two assuming a transmutation of species over time. Elaborate networks of affinities among plants and among animals were depicted in the late Eighteenth and very early Nineteenth centuries. In the two decades immediately prior to 1837, so-called affinities and/or analogies among organisms were represented by diverse geometric figures. Series of plant and animal fossils in successive geological strata were represented as trees in a popular textbook from 1840, while in 1858 Bronn presented a system of animals, as evidenced by the fossil record, in a form of a tree. Darwin's 1859 tree and its subsequent elaborations by Haeckel came to be accepted in many but not all areas of biological sciences, while network diagrams were used in others. Beginning in the early 1960s trees were inferred from protein and nucleic acid sequences, but networks were re-introduced in the mid-1990s to represent lateral genetic transfer, increasingly regarded as a fundamental mode of evolution at least for bacteria and archaea. In historical context, then, the Network of Life preceded the Tree of Life and might again supersede it. Reviewers: This article was reviewed by Eric Bapteste, Patrick Forterre and Dan Graur. © 2009 Ragan; licensee BioMed Central Ltd." 35 David A. Morrison. Using data-display networks for exploratory data analysis in phylogenetic studies. In MBE, Vol. 27(5):1044-1057, 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 data-display 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 data-display 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." 36 Hans-Jürgen Bandelt and Arne Dür. Translating DNA data tables into quasi-median networks for parsimony analysis and error detection. In MPE, Vol. 42(1):256-271, 2007. Keywords: abstract network, from sequences, parsimony, phylogenetic network, phylogeny, quasi-median network, reconstruction. Note: http://dx.doi.org/10.1016/j.ympev.2006.07.013.         Toggle abstract "Every DNA data table can be turned into a quasi-median network that faithfully represents the data. We show that for (weighted) condensed data tables the associated network harbors all most parsimonious reconstructions for any tree that connects the sampled haplotypes. Structural features of this network can be computed directly from the data table. The key principle repeatedly used is that the quasi-median network is uniquely determined by the sub-tables for pairs of characters. The translation of a table into a network enhances the understanding of the properties of the data in regard to homoplasy and potential artifacts. The total number of nodes of such a network measures the complexity of the data. In particular, networks that display the results of filter analyses by which hotspot mutations are removed help to detect data idiosyncrasies and thus pinpoint sequencing problems. A pertinent example drawn from human mtDNA illustrates these points. © 2006 Elsevier Inc. All rights reserved." 37 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." 38 Mihaela Baroni and Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.         Toggle abstract "We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg." 39 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." 40 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." 41 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." 42 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." 43 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." 44 Andreas Spillner, Binh T. Nguyen and Vincent Moulton. Constructing and Drawing Regular Planar Split Networks. In TCBB, Vol. 9(2):395-407, 2012. Keywords: abstract network, from splits, phylogenetic network, phylogeny, reconstruction, visualization. Note: slides and presentation available at http://www.newton.ac.uk/programmes/PLG/seminars/062111501.html.         Toggle abstract "Split networks are commonly used to visualize collections of bipartitions, also called splits, of a finite set. Such collections arise, for example, in evolutionary studies. Split networks can be viewed as a generalization of phylogenetic trees and may be generated using the SplitsTree package. Recently, the NeighborNet method for generating split networks has become rather popular, in part because it is guaranteed to always generate a circular split system, which can always be displayed by a planar split network. Even so, labels must be placed on the "outside" of the network, which might be problematic in some applications. To help circumvent this problem, it can be helpful to consider so-called flat split systems, which can be displayed by planar split networks where labels are allowed on the inside of the network too. Here, we present a new algorithm that is guaranteed to compute a minimal planar split network displaying a flat split system in polynomial time, provided the split system is given in a certain format. We will also briefly discuss two heuristics that could be useful for analyzing phylogeographic data and that allow the computation of flat split systems in this format in polynomial time. © 2006 IEEE." 45 Paul Phipps and Sergey Bereg. Optimizing Phylogenetic Networks for Circular Split Systems. In TCBB, Vol. 9(2):535-547, 2012. Keywords: abstract network, from distances, from splits, phylogenetic network, phylogeny, Program PhippsNetwork, reconstruction, software.         Toggle abstract "We address the problem of realizing a given distance matrix by a planar phylogenetic network with a minimum number of faces. With the help of the popular software SplitsTree4, we start by approximating the distance matrix with a distance metric that is a linear combination of circular splits. The main results of this paper are the necessary and sufficient conditions for the existence of a network with a single face. We show how such a network can be constructed, and we present a heuristic for constructing a network with few faces using the first algorithm as the base case. Experimental results on biological data show that this heuristic algorithm can produce phylogenetic networks with far fewer faces than the ones computed by SplitsTree4, without affecting the approximation of the distance matrix. © 2012 IEEE." 46 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." 47 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." 48 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." 49 Philippe Gambette, Vincent Berry and Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012. Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, orientation, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network. Note: http://hal.archives-ouvertes.fr/hal-00678046/en/.         Toggle abstract "Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press." 50 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. 51 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." 52 Ruogu Sheng and Sergey Bereg. Approximating Metrics with Planar Boundary-Labeled Phylogenetic Networks. In JBCB, Vol. 10(6):1250017, 2012. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction.         Toggle abstract "Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa. © 2012 Imperial College Press." 53 Sven Herrmann and Vincent Moulton. Computing the blocks of a quasi-median graph. In DAM, Vol. 179:129-138, 2014. Keywords: abstract network, from sequences, phylogenetic network, phylogeny, polynomial, Program QuasiDec, quasi-median network, reconstruction. Note: http://arxiv.org/abs/1206.6135.         54 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." 55 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." 56 Eric Bapteste, Leo van Iersel, Axel Janke, Scott Kelchner, Steven Kelk, James O. McInerney, David A. Morrison, Luay Nakhleh, Mike Steel, Leen Stougie and James B. Whitfield. Networks: expanding evolutionary thinking. In Trends in Genetics, Vol. 29(8):439-441, 2013. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction. Note: http://bioinf.nuim.ie/wp-content/uploads/2013/06/Bapteste-TiG-2013.pdf.         Toggle abstract "Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes. © 2013 Elsevier Ltd." 57 Anthony Labarre and Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. In TCBB, Vol. 11(2):389-397, 2014. Keywords: abstract network, from unrooted trees, heuristic, NP complete, phylogenetic network, phylogeny, reconstruction. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-00855669.         Toggle abstract "Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of t partially labelled trees. Although algorithms have been proposed for solving that problem on two graphs, the complexity of the general problem on trees remains unknown. In this paper, we show that the corresponding decision problem is NP-complete for t=3. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the idpsystem, and assess the performance of both methods on randomly generated data. © 2004-2012 IEEE." 58 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." 59 Jialiang Yang, Stefan Grünewald, Yifei Xu and Xiu-Feng Wan. Quartet-based 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/1752-0509-8-21 .         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 distance-based methods, quartet-based 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 quartet-based 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." 60 David A. Morrison. Rooted Phylogenetic Networks for Exploratory Data Analysis. In Advances in Research, Vol. 2(3):145-152, 2014. Keywords: abstract network, explicit network, phylogenetic network, reconstruction.         61 David A. Morrison. Next generation sequencing and phylogenetic networks. In EMBnet.journal, Vol. 20(e760):1-4, 2014. Keywords: abstract network, from NGS data, phylogenetic network, phylogeny, Program SplitsTree, reconstruction.         62 Alberto Apostolico, Matteo Comin, Andreas W. M. Dress and Laxmi Parida. Ultrametric networks: a new tool for phylogenetic analysis. In Algorithms for Molecular Biology, Vol. 8(7):1-10, 2013. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program Ultranet. Note: http://dx.doi.org/10.1186/1748-7188-8-7.         Toggle abstract "Background: The large majority of optimization problems related to the inference of distance-based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.Results: This paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availability: http://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html. © 2013 Apostolico et al.; licensee BioMed Central Ltd." 63 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." 64 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.         65 David A. Morrison. Is the Tree of Life the Best Metaphor, Model, or Heuristic for Phylogenetics? In Systematic Biology, Vol. 63(4):628-638, 2014. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, survey.         66 Jessica W. Leigh and David Bryant. PopART: full-feature software for haplotype network construction. In Methods in Ecology and Evolution, Vol. 6(9):1110-1116, 2015. Keywords: abstract network, from sequences, haplotype network, MedianJoining, phylogenetic network, phylogeny, population genetics, Program PopART, Program TCS, software. Note: http://dx.doi.org/10.1111/2041-210X.12410.         67 Hussein A. Hejase and Kevin J. Liu. A scalability study of phylogenetic network inference methods using empirical datasets and simulations involving a single reticulation. Vol. 17(422):1-12, 2016. Keywords: abstract network, evaluation, from sequences, phylogenetic network, phylogeny, Program PhyloNet, Program PhyloNetworks SNaQ, reconstruction, simulation, unicyclic network. Note: http://dx.doi.org/10.1186/s12859-016-1277-1.         68 Satyan L. Devadoss and Samantha Petti. A Space of Phylogenetic Networks. In SIAM Journal on Applied Algebra and Geometry, Vol. 1(1):683-705, 2017. Keywords: abstract network, circular split system, phylogenetic network, phylogeny, split network. Note: http://arxiv.org/abs/1607.06978.         69 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):1057-1058, 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.         70 Klaus Schliep, Alastair J. Potts, David A. Morrison and Guido W. Grimm. Intertwining phylogenetic trees and networks. In Methods in Ecology and Evolution, Vol. 8(10):1212-1220, 2017. Keywords: abstract network, from network, from unrooted trees, phylogenetic network, phylogeny, split network, visualization. Note: http://dx.doi.org/10.1111/2041-210X.12760.

InProceedings

71 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.         72 Andreas W. M. Dress, Katharina Huber and Vincent Moulton. Hereditarily Optimal Realizations: Why are they Relevant in Phylogenetic Analysis, and how does one Compute them? In Proceedings of the Euroconference on Algebraic Combinatorics and Applications (Alcoma'99), Pages 110-117, springer, 2001. Keywords: abstract network, from distances, optimal realization, phylogenetic network. Note: http://www.math.uni-bielefeld.de/fsp-math/Preprints/139.pdf.         73 Daniel H. Huson and Regula Rupp. Summarizing Multiple Gene Trees Using Cluster Networks. In WABI08, Vol. 5251:296-305 of LNCS, springer, 2008. Keywords: abstract network, from clusters, from rooted trees, phylogenetic network, phylogeny, polynomial, Program Dendroscope. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_25, slides from the MIEP Conference available at http://www.lirmm.fr/MIEP08/slides/11_13_rupp.pdf.         Toggle abstract "The result of a multiple gene tree analysis is usually a number of different tree topologies that are each supported by a significant proportion of the genes. We introduce the concept of a cluster network that can be used to combine such trees into a single rooted network, which can be drawn either as a cladogram or phylogram. In contrast to split networks, which can grow exponentially in the size of the input, cluster networks grow only quadratically. A cluster network is easily computed using a modification of the tree-popping algorithm, which we call network-popping. The approach has been implemented as part of the Dendroscope tree-drawing program and its application is illustrated using data and results from three recent studies on large numbers of gene trees. © 2008 Springer-Verlag Berlin Heidelberg." 74 Lichen Bao and Sergey Bereg. Clustered SplitsNetworks. In COCOA08, Vol. 5165:469-478 of LNCS, springer, 2008. Keywords: abstract network, from distances, NeighborNet, realization, reconstruction. Note: http://dx.doi.org/10.1007/978-3-540-85097-7_44, slides available at http://www.utdallas.edu/~besp/cocoa08talk.pdf.         Toggle abstract "We address the problem of constructing phylogenetic networks using two criteria: the number of cycles and the fit value of the network. Traditionally the fit value is the main objective for evaluating phylogenetic networks. However, a small number of cycles in a network is desired and pointed out in several publications. We propose a new phylogenetic network called CS-network and a method for constructing it. The method is based on the well-known splitstree method. A CS-network contains a face which is k-cycle, k ≥ 3 (not as splitstree). We discuss difficulties of using non-parallelogram faces in splitstree networks. Our method involves clustering and optimization of weights of the network edges. The algorithm for constructing the underlying graph (except the optimization step) has a polynomial time. Experimental results show a good performance of our algorithm. © Springer-Verlag Berlin Heidelberg 2008." 75 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." 76 Daniel H. Huson, Regula Rupp, Vincent Berry, Philippe Gambette and Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009. Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.         Toggle abstract "Motivation: Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. Results: In this article, we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves successively solving instances of two different NP-complete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. © 2009 The Author(s)." 77 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.         78 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.         79 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." 80 Sebastien Roch and Kun-Chieh Wang. Circular Networks from Distorted Metrics. In RECOMB18, Vol. 10812:167-176 of LNCS, Springer, 2018. Keywords: abstract network, circular split system, from distances, NeighborNet, phylogenetic network, phylogeny, reconstruction, split network. Note: https://arxiv.org/abs/1707.05722.

InBook

81 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.         82 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.         83 David A. Morrison. Phylogenetic networks in systematic biology (and elsewhere) In R.M. Mohan editor, Research Advances in Systematic Biology, Global Research Network, Trivandrum, India, 2010. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, reconstruction, survey.         84 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.         85 David A. Morrison. Phylogenetic networks are fundamentally different from other kinds of biological networks. In WenJun Zhang editor, Network Biology: Theories, Methods and Applications, Chapter 2, Nova Publishers, 2013. Keywords: abstract network, explicit network, phylogenetic network, phylogeny.         86 Mike Steel. Introduction to phylogenetic networks. In Phylogeny: Discrete and Random Processes in Evolution, Vol. 89 of CBMS-NSF Regional Conference Series in Applied Mathematics, Chapter 10, SIAM, 2016. Keywords: abstract network, explicit network, phylogenetic network, phylogeny, survey. Note: http://bookstore.siam.org/cb89/.

PhdThesis

87 Patrice Bertrand. Étude de la représentation pyramidale. PhD thesis, Université de Paris-Dauphine, France, 1986. Keywords: abstract network, pyramid.         88 Rainer Wetzel. Zur Visualisierung abstrakter Ahnlichkeitsbeziehungen. PhD thesis, Universität Bielefeld, Germany, 1995. Keywords: abstract network, circular split system, visualization.         89 Anthony Labarre. Combinatorial aspects of genome rearrangements and haplotype networks. PhD thesis, Université Libre de Bruxelles, Belgium, 2008. Keywords: abstract network, from unrooted trees, haplotype network, phylogenetic network, phylogeny, reconstruction. Note: http://homepages.ulb.ac.be/~alabarre/publications/phd-thesis.pdf.         90 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.         91 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/.         92 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.         93 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.         94 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.         95 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.         96 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.         97 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://spectre-suite-of-phylogenetic-tools-for-reticulate-evolution.readthedocs.io/en/latest/_downloads/spectre_bastkowskis_thesis.pdf.         98 Pei Wu. Quartet weights in phylogenetic network reconstruction. PhD thesis, University of Chinese Academy of Sciences, 2016. Keywords: abstract network, from distances, from quartets, phylogenetic network, phylogeny, reconstruction, split, split network. Note: https://www.researchgate.net/publication/324475948_Quartet_weights_in_phylogenetic_network_reconstruction.         99 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.

Misc

100 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.         101 Willem Sonke. Reconstructing a level-1-network from quartets. 2013. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, polynomial, Program Fylogenetica, reconstruction, software, visualization. Note: http://alexandria.tue.nl/extra1/afstversl/wsk-i/sonke2013.pdf.