RapidNJ is an algorithmic engineered implementation of canonical neighbour-joining. It uses an efficient search heuristic to speed-up the core computations of the neighbour-joining method that enables RapidNJ to outperform other state-of-the-art neighbour-joining implementations. The RapidNJ method was originally presented in:

• Rapid Neighbour Joining. Martin Simonsen, Thomas Mailund and Christian N. S. Pedersen. In Proceedings of the 8th Workshop in Algorithms in Bioinformatics (WABI), LNBI 5251, 113-122, Springer Verlag, October 2008. doi:10.1007/978-3-540-87361-7_10

Further development of RapidNJ has improved the search heuristic, decreased memory consumption and enabled the utilization of external memory. It also includes an efficient computation of distance estimators from input alignments. These improvements allow the current implementation of RapidNJ to handle very large datasets (50,000+ taxa) efficiently on a normal desktop computer. Papers describing these improvements are:

• Inference of Large Phylogenies using Neighbour-Joining. Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen. Communications in Computer and Information Science (Biomedical Engineering Systems and Technologies: 3rd International Joint Conference, BIOSTEC 2010, Revised Selected Papers), volume 127, pages 334-344, Springer Verlag, 2011. (Extended version of a paper published at BIOSTEC 2010).
• Rapid Computation of Distance Estimators from Nucleotide and Amino Acid Alignments. Martin Simonsen, Christian N. S. Pedersen. In Proceedings of 26th Annual ACM Symposium on Applied Computing (SAC 2011), ACM Press, March 2011.

Download

The latest version of RapidNJ is 2.2.0 and it was released on January 31, 2013. 

rapidnj-src-2.2.1.zip (distributed under the GPL v2 license)

The are also precompiled versions of the latest RapidNJ available for Windows (32 and 64 bit).

rapidnj_win32.exe

rapidnj_win64.exe

Prerequisites

RapidNJ has been developed and tested on Linux (Ubuntu version 8.10) running on an Intel Pentium compatible CPU. It has also been tested on Mac OS X. Compiling RapidNJ requires gcc version 2.1 (or higher).

Installation

Unpack the source code:

$ unzip rapidnj-src-2.2.0.zip

Compile the program using the included Makefile (on some older systems it might be necessary to remove the flag '-flax-vector-conversions' from the makefile):

$ cd rapidNJ

$ make

After a succesful compilation the binary 'rapidnj' can be found in the subdirectory 'bin'. You can e.g. copy this binary to a directory in your search path for easier access.

Advanced compilation options

To enable support for computation of distance matrices using SSE4.2 instructions, replace the '-msse2' switch in the Makefile with '-msse4'.

To compile with support for computation of distance estimators on CUDA enabled hardware, use the 'rapidnj_cuda' target in the Makefile. The CUDA SDK is required for this and must be installed on the system.

In most case the default method for computing distance matrices is the fastest and should be used.

Usage

Executing the binary 'rapidnj' with no arguments will produce a help message containing the syntaxt and a list of options. RapidNJ will accept two different input formats. Distance matrices in phylip format and alignments in stockholm format. The program can usually guess the input format, otherwise the -i option can be used to choose between different formats. Support for phylip formatted multiple alignments is also included but might not work with all methods for computation of distance matrices.

To infer a tree from an alignment in Stockholm format use the following command

$ rapidnj FILENAME -i sth

where FILENAME is the name of the file with the alignment.

The program will automatically switch between three different versions of the rapidNJ algorithm depending on the size of the tree and the amount of available memory. Several options are available to force a specific algorithm to be used.

Contact

Martin Simonsen, Bioinformatics Research Centre, Aarhus University