Publications related to 'NeighborNet' : NeighborNet is an algorithm which produces a planar split network from a set of splits. It is integrated in the SplitsTree software.

Order by: Type  Year







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






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






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



Marc Thuillard and
Vincent Moulton. Identifying and reconstructing lateral transfers from distance matrices by combining the Minimum Contradiction Method and NeighborNet. In JBCB, Vol. 9(4):453470, 2011. Keywords: from distances, lateral gene transfer, minimum contradiction, NeighborNet, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1142/S0219720011005409, slides available at http://www.newton.ac.uk/programmes/PLG/seminars/062015501.html.
Toggle abstract
"Identifying lateral gene transfers is an important problem in evolutionary biology. Under a simple model of evolution, the expected values of an evolutionary distance matrix describing a phylogenetic tree fulfill the socalled Kalmanson inequalities. The Minimum Contradiction method for identifying lateral gene transfers exploits the fact that lateral transfers may generate large deviations from the Kalmanson inequalities. Here a new approach is presented to deal with such cases that combines the NeighborNet algorithm for computing phylogenetic networks with the Minimum Contradiction method. A subset of taxa, prescribed using NeighborNet, is obtained by measuring how closely the Kalmanson inequalities are fulfilled by each taxon. A criterion is then used to identify the taxa, possibly involved in a lateral transfer between nonconsecutive taxa. We illustrate the utility of the new approach by applying it to a distance matrix for Archaea, Bacteria, and Eukaryota. © 2011 Imperial College Press."






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






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



Lichen Bao and
Sergey Bereg. Clustered SplitsNetworks. In COCOA08, Vol. 5165:469478 of LNCS, springer, 2008. Keywords: abstract network, from distances, NeighborNet, realization, reconstruction. Note: http://dx.doi.org/10.1007/9783540850977_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 CSnetwork and a method for constructing it. The method is based on the wellknown splitstree method. A CSnetwork contains a face which is kcycle, k ≥ 3 (not as splitstree). We discuss difficulties of using nonparallelogram 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. © SpringerVerlag Berlin Heidelberg 2008."






David Bryant,
Vincent Moulton and
Andreas Spillner. Consistency of the NeighborNet Algorithm. In AMB, Vol. 2(8), 2007. Keywords: abstract network, consistency, from distances, NeighborNet. Note: http://dx.doi.org/10.1186/1748718828.
Toggle abstract
"Background: NeighborNet 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, NeighborNet 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 NeighborNet satisfies both of these requirements so that, in particular, NeighborNet is statistically consistent on circular distances. © 2007 Bryant et al; licensee BioMed Central Ltd."



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






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






Martyn Kennedy,
Barbara R. Holland,
Russel D. Gray and
Hamish G. Spencer. Untangling Long Branches: Identifying Conflicting Phylogenetic Signals Using Spectral Analysis, NeighborNet, and Consensus Networks. In Systematic Biology, Vol. 54(4):620633, 2005. Keywords: abstract network, consensus, NeighborNet, phylogenetic network, phylogeny. Note: http://awcmee.massey.ac.nz/people/bholland/pdf/Kennedy_etal_2005.pdf.



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








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



