Talk:Neighbor joining

	This article is within the scope of WikiProject Tree of Life, a collaborative effort to improve the coverage of taxonomy and the phylogenetic tree of life on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Tree of LifeWikipedia:WikiProject Tree of LifeTemplate:WikiProject Tree of Lifetaxonomic articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been marked as needing immediate attention.

Template:WikiProject Computational Biology

Comments

The last sentence of the 2nd paragraph needs to be referenced: Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree.

Who tested it?

Yeah, that's a really bad statement. The basic idea is that neighbor-joining assumes rates-across-sites. So if you generate your data under a rates-across-sites model, then you can be fairly sure that you'll get pretty good results. So neighbor-joining is only "suboptimal" in the sense that it requires the rates-across-sites assumption to do well. I'll look for a reference for this. --Wzhao553 20:10, 21 February 2006 (UTC)[reply]

Actually, there is a precise answer. A distance matrix is called additive if it can be specified by a tree with distances along the edges. NJ works if the given distance matrix d is 'close' to additive. The precise notion is given in one of the references of the article (why NJ works). --Jochgem (talk) 15:38, 18 April 2008 (UTC)[reply]

In the algorithm description: "Find the pair of taxa in Q with the lowest value. Create a node on the tree that joins these two taxa (i.e. join the closest neighbors, as the algorithm name implies)." -- It is not clear to me how the joining of two taxa works. while the method is probably specific to the given data, at least the general criteria for the joined object should be mentioned. 91.89.65.97 (talk) 09:13, 29 July 2008 (UTC)[reply]

Time and space complexity of this algorithm? --TobiasBengtsson (talk) 20:47, 17 November 2008 (UTC)[reply]

I'm currently trying to improve the article, and I added what a naive implementation would result in. Probably the faster methods out there give more details in their papers, but I haven't looked at them yet 134.58.42.46 (talk) 08:58, 16 March 2011 (UTC)[reply]

The statement "In the example above, this formula would give a distance of 6 between A and the new node and a distance of 1 between B and the new node." appears to be wrong. For the distance between A and the new node, I get 7/2 + 17/4. Tedtoal (talk) 01:20, 27 August 2010 (UTC)[reply]

My implementation gets the "right" values (6 and 1), maybe I should finish the example originally posted by "???" 134.58.42.46 (talk) 08:58, 16 March 2011 (UTC)[reply]

Branch lengths

Does neighbor joining always produce trees with strictly positive integer branch lengths?