The Neighbor-Net Algorithm
| dc.creator | Levy, Dan | |
| dc.creator | Pachter, Lior | |
| dc.date | 2007-02-18 | |
| dc.date | 2008-05-12 | |
| dc.date.accessioned | 2026-07-07T09:38:27Z | |
| dc.date.available | 2026-07-07T09:38:27Z | |
| dc.description | 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 $\bar{\MM}_{0}^n(\mathbb{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 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. | |
| dc.identifier | https://arxiv.org/abs/math/0702515 | |
| dc.identifier | http://arxiv.org/abs/math/0702515 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160811 | |
| dc.subject | Combinatorics | |
| dc.subject | Quantitative Methods | |
| dc.title | The Neighbor-Net Algorithm | |
| dc.type | text |