Aarhus University Seal / Aarhus Universitets segl

RapidNJ

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:

Download and Installation

Source code and compilation and installation instructions for Mac, Linux, and Windows are available via GitHub:

https://github.com/somme89/rapidNJ

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. A full (squared) 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

Christian N. S. Pedersen, Bioinformatics Research Centre, Aarhus University