Editing Neighbor joining (section)

==Implementations and variants==
There are many programs available implementing neighbor joining. Among implementations of ''canonical'' NJ (i.e. using the classical NJ optimisation criteria, therefore giving the same results), RapidNJ (started 2003, major update in 2011, still updated in 2023)<ref>{{cite web |title=RapidNJ |url=http://birc.au.dk/Software/RapidNJ/ |website=birc.au.dk |language=en}}</ref> and NINJA (started 2009, last update 2013)<ref>{{cite web |title=NINJA: a tool for large-scale neighbor-joining phylogeny inference - Home |url=http://wheelerlab.org/software/ninja/index.html |website=wheelerlab.org}}</ref> are considered state-of-the-art. They have  typical run times proportional to approximately the square of the number of taxa.

Variants that deviate from canonical include:
* BIONJ (1997)<ref>{{cite web |title=ATGC: BioNJ |url=http://www.atgc-montpellier.fr/bionj/ |website=www.atgc-montpellier.fr}}</ref> and Weighbor (2000),<ref>{{cite web |title=WEIGHBOR Homepage |url=http://www.t6.lanl.gov/billb/weighbor/ |date=5 March 2015|archive-url=https://web.archive.org/web/20150305041147/http://www.t6.lanl.gov/billb/weighbor/ |archive-date=2015-03-05 }}</ref> improving on the accuracy by making use of the fact that the shorter distances in the distance matrix are generally better known than the longer distances. The two methods have been extended to run on incomplete distance matrices.<ref>{{cite journal |last1=Criscuolo |first1=Alexis |last2=Gascuel |first2=Olivier |title=Fast NJ-like algorithms to deal with incomplete distance matrices |journal=BMC Bioinformatics |date=December 2008 |volume=9 |issue=1 |page=166 |doi=10.1186/1471-2105-9-166 |pmid=18366787 |pmc=2335114 |doi-access=free }}</ref>
* "Fast NJ" remembers the best node and is O(n^2) always; "relax NJ" performs a hill-climbing search and retains the worst-case complexity of O(n^3). Rapid NJ is faster than plain relaxed NJ.<ref>{{cite book |last1=Simonsen |first1=Martin |last2=Mailund |first2=Thomas |last3=Pedersen |first3=Christian N. S. |chapter=Rapid Neighbour-Joining |title=Algorithms in Bioinformatics |series=Lecture Notes in Computer Science |date=2008 |volume=5251 |pages=113–122 |doi=10.1007/978-3-540-87361-7_10 |isbn=978-3-540-87360-0 |chapter-url=https://users-birc.au.dk/cstorm/software/rapidnj/papers/SimonsenOthers2008_WABI.pdf}}</ref>
* FastME is an implementation of the closely related ''balanced [[minimum evolution]]'' (BME) method (see {{section link||Neighbor joining as minimum evolution}}). It is about as fast as and more accurate than NJ. It starts with a rough tree then improves it using a set of topological moves such as Nearest Neighbor Interchanges (NNI).<ref>{{cite web |title=ATGC: FastME |url=http://www.atgc-montpellier.fr/fastme/ |website=www.atgc-montpellier.fr}}</ref> FastTree is a related method. It works on sequence "profiles" instead of a matrix. It starts with an approximately NJ tree, rearranges it into BME, then rearranges it into approximate maximum-likelihood.<ref>{{cite web |title=FastTree 2.1: Approximately-Maximum-Likelihood Trees for Large Alignments |url=http://www.microbesonline.org/fasttree/ |website=www.microbesonline.org}}</ref>