The neighbor-net algorithm
From MaRDI portal
Publication:550258
DOI10.1016/J.AAM.2010.09.002zbMATH Open1274.92005OpenAlexW2128686408MaRDI QIDQ550258FDOQ550258
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 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 1/2. 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1945176 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 2115083 (Why is no real title available?)
- scientific article; zbMATH DE number 1390038 (Why is no real title available?)
- A Note On Kalmanson Matrices∗
- A canonical decomposition theory for metrics on a finite set
- A note on circular decomposable metrics
- Algebraic Statistics for Computational Biology
- Automata, Languages and Programming
- Coxeter complexes and graph-associahedra
- Cyclic permutations and evolutionary trees
- Edgeconvex Circuits and the Traveling Salesman Problem
- Extending Tree Models to Splits Networks
- Geometry of the space of phylogenetic trees
- Small Trees and Generalized Neighbor-Joining
- Sometimes Travelling is Easy: The Master Tour Problem
- TSPLIB—A Traveling Salesman Problem Library
- The minimum evolution distance-based approach to phylogenetic inference
- The number of clone orderings
- The performance of neighbor-joining methods of phylogenetic reconstruction
- Toric geometry of cuts and splits
- When the greedy algorithm fails
- Why neighbor-joining works
- \(T\)-theory: An overview
Cited in
(10)- scientific article; zbMATH DE number 1940309 (Why is no real title available?)
- Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem
- The dual complex of \({\overline{M}_{0,n}}\) via phylogenetics
- Affine and projective tree metric theorems
- Level-1 phylogenetic networks and their balanced minimum evolution polytopes
- Fishing for minimum evolution trees with neighbor-nets
- Circular Planar Electrical Networks, Split Systems, and Phylogenetic Networks
- A space of phylogenetic networks
- scientific article; zbMATH DE number 1945177 (Why is no real title available?)
- Equidistant circular split networks
This page was built for publication: The neighbor-net algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550258)
