The neighbor-net algorithm

DOI10.1016/J.AAM.2010.09.002zbMATH Open1274.92005arXivmath/0702515OpenAlexW2128686408MaRDI QIDQ550258FDOQ550258

Authors: Dan Levy, Lior Pachter 

Publication date: 8 July 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0702515

Recommendations

• Fishing for minimum evolution trees with neighbor-nets
• scientific article; zbMATH DE number 1945177
• QUARTET CONSISTENCY COUNT METHOD FOR RECONSTRUCTING PHYLOGENETIC TREES
• scientific article; zbMATH DE number 1088265
• The Geometry of the Neighbor-Joining Algorithm for Small Trees

zbMATH Keywords

traveling salesman problemneighbor-joiningminimum evolutionbalanced lengthcircular decomposable metricKalmanson conditionsneighbor-netsplits network

Mathematics Subject Classification ID

Applications of statistics to biology and medical sciences; meta analysis (62P10) Problems related to evolution (92D15) Combinatorics in computer science (68R05) Taxonomy, cladistics, statistics in mathematical biology (92B10) Algebraic combinatorics (05E99)

Cites Work

• TSPLIB—A Traveling Salesman Problem Library
• Title not available (Why is that?)
• Geometry of the space of phylogenetic trees
• Title not available (Why is that?)
• Algebraic Statistics for Computational Biology
• A canonical decomposition theory for metrics on a finite set
• Cyclic permutations and evolutionary trees
• Title not available (Why is that?)
• Coxeter complexes and graph-associahedra
• Title not available (Why is that?)
• Why neighbor-joining works
• The performance of neighbor-joining methods of phylogenetic reconstruction
• Edgeconvex Circuits and the Traveling Salesman Problem
• A note on circular decomposable metrics
• \(T\)-theory: An overview
• Sometimes Travelling is Easy: The Master Tour Problem
• Toric geometry of cuts and splits
• When the greedy algorithm fails
• Extending Tree Models to Splits Networks
• Small Trees and Generalized Neighbor-Joining
• The minimum evolution distance-based approach to phylogenetic inference
• The number of clone orderings
• A Note On Kalmanson Matrices^∗
• Title not available (Why is that?)
• Automata, Languages and Programming

Cited In (10)

• The dual complex of \({\overline{M}_{0,n}}\) via phylogenetics
• Fishing for minimum evolution trees with neighbor-nets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem
• Circular Planar Electrical Networks, Split Systems, and Phylogenetic Networks
• Affine and projective tree metric theorems
• Level-1 phylogenetic networks and their balanced minimum evolution polytopes
• A Space of Phylogenetic Networks
• Equidistant circular split networks

Uses Software

• TSPLIB
• Concorde
• BIONJ

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)