CaltechAUTHORS
  A Caltech Library Service

The neighbor-net algorithm

Levy, Dan and Pachter, Lior (2011) The neighbor-net algorithm. Advances in Applied Mathematics, 47 (2). pp. 240-258. ISSN 0196-8858. doi:10.1016/j.aam.2010.09.002. https://resolver.caltech.edu/CaltechAUTHORS:20170306-113043756

[img] PDF - Submitted Version
See Usage Policy.

837kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170306-113043756

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¯_0^n(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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.aam.2010.09.002DOIArticle
http://www.sciencedirect.com/science/article/pii/S019688581000093XPublisherArticle
https://arxiv.org/abs/math/0702515arXivDiscussion Paper
ORCID:
AuthorORCID
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2010 Elsevier. Received 18 February 2007, Accepted 3 June 2007, Available online 5 November 2010. Fig. 1(e) is inspired by Fig. 13(b) from [23]. We thank David Bryant, Vincent Moulton and Andreas Spillner for kindly sharing with us a preprint of [10], Lu Luo for useful comments on a preliminary version of this manuscript, and Radu Mihaescu for suggestions in the proof of Theorem 29. Lior Pachter was supported in part by an NSF CAREER award (CCF-0347992) and thanks Jotun Hem and Philip Maini for hosting him while on sabbatical when this work was performed. Dan Levy was supported by a grant from the Biotechnology and Biological Sciences Research Council of the UK (BB/D005418/1).
Funders:
Funding AgencyGrant Number
NSFCCF-0347992
Biotechnology and Biological Sciences Research Council (BBSRC)BB/D005418/1
Subject Keywords:Neighbor-net; Neighbor-joining; Circular decomposable metric; Traveling salesman problem; Kalmanson conditions; Balanced length; Minimum evolution; Splits network
Issue or Number:2
Classification Code:MSC: 92B10 92D15 68R05 62P10 05E99
DOI:10.1016/j.aam.2010.09.002
Record Number:CaltechAUTHORS:20170306-113043756
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170306-113043756
Official Citation:Dan Levy, Lior Pachter, The neighbor-net algorithm, Advances in Applied Mathematics, Volume 47, Issue 2, 2011, Pages 240-258, ISSN 0196-8858, http://dx.doi.org/10.1016/j.aam.2010.09.002. (http://www.sciencedirect.com/science/article/pii/S019688581000093X)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74786
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:06 Mar 2017 20:54
Last Modified:11 Nov 2021 05:29

Repository Staff Only: item control page