phylobuild - Fast Neighbor-Joining Trees in R • phylobuild

phylobuild provides fast neighbor-joining algorithms for phylogenetic tree construction in R. It wraps the highly optimized decenttree C++ library to deliver 10-100x speedups over ape::nj() for large datasets.

Performance

Taxa	ape::nj()	phylobuild::fast_nj()	Speedup
100	0.001s	0.001s	~1x
500	0.07s	0.02s	4x
1,000	0.55s	0.07s	8x
2,000	4.5s	0.25s	18x
5,000	70s	1.5s	47x

For datasets with thousands of taxa, phylobuild makes neighbor-joining practical.

Benchmark comparing phylobuild::fast_nj() vs ape::nj() showing computation time in seconds across different numbers of taxa, demonstrating 10-100x speedups for large datasets

Installation

# Install from GitHub
devtools::install_github("slowkow/phylobuild")

Quick Start

library(phylobuild)
library(ape)

# Load example primate data
data(primates)

# Build tree with RapidNJ (default, fastest)
tree <- fast_nj(primates)

# Plot the result
plot(tree, type = "unrooted")

The result is a standard phylo object, fully compatible with ape and the broader R phylogenetics ecosystem.

Available Algorithms

list_algorithms()
#> [1] "rapidnj"     "nj"          "bionj"       "rapid_bionj"

Algorithm	Description	When to Use
`rapidnj`	RapidNJ with branch-and-bound	Default. Best for large datasets
`nj`	Classic NJ (Saitou & Nei 1987)	When exact NJ is required
`bionj`	BIONJ with variance estimates	When distance uncertainty matters
`rapid_bionj`	RapidNJ + BIONJ	Large datasets + variance weighting

Example: Comparing Algorithms

# Build trees with different methods
tree_rapid <- fast_nj(primates, method = "rapidnj")
tree_nj    <- fast_nj(primates, method = "nj")
tree_bionj <- fast_nj(primates, method = "bionj")

# All produce valid phylo objects
class(tree_rapid)
#> [1] "phylo"

Acknowledgements

phylobuild is a thin wrapper around the excellent decenttree C++ library. All the heavy lifting—the algorithmic innovations, optimizations, and years of development work—was done by the decenttree authors:

James Barbetti — Primary developer of decenttree
Bui Quang Minh — Co-developer, IQ-TREE project lead

Their paper describes the scalable neighbor-joining implementations that power this package:

Barbetti J, Minh BQ (2023). “Decenttree: Scalable Neighbour-Joining for the Genomic Era.” Bioinformatics, 39(9), btad536. doi:[10.1093/bioinformatics/btad536](https://doi.org/10.1093/bioinformatics/btad536)

We are deeply grateful for their work in making fast, accurate phylogenetic inference accessible to the research community.

Citation

If you use phylobuild in your research, please cite the decenttree paper:

Barbetti J, Minh BQ (2023). “Decenttree: Scalable Neighbour-Joining for the Genomic Era.” Bioinformatics, 39(9), btad536. doi:[10.1093/bioinformatics/btad536](https://doi.org/10.1093/bioinformatics/btad536)

@article{barbetti2023decenttree,
  title   = {Decenttree: Scalable Neighbour-Joining for the Genomic Era},
  author  = {Barbetti, James and Minh, Bui Quang},
  journal = {Bioinformatics},
  volume  = {39},
  number  = {9},
  pages   = {btad536},
  year    = {2023},
  doi     = {10.1093/bioinformatics/btad536}
}

For the underlying algorithms, you may also wish to cite:

RapidNJ (Simonsen et al. 2011)

@inproceedings{simonsen2011rapidnj,
  title     = {Inference of Large Phylogenies using Neighbour-Joining},
  author    = {Simonsen, Martin and Mailund, Thomas and Pedersen, Christian N. S.},
  booktitle = {Communications in Computer and Information Science},
  volume    = {127},
  pages     = {334--344},
  year      = {2011},
  publisher = {Springer},
  doi       = {10.1007/978-3-642-18472-7_24}
}

BIONJ (Gascuel 1997)

@article{gascuel1997bionj,
  title   = {BIONJ: An Improved Version of the NJ Algorithm Based on a Simple Model of Sequence Data},
  author  = {Gascuel, Olivier},
  journal = {Molecular Biology and Evolution},
  volume  = {14},
  number  = {7},
  pages   = {685--695},
  year    = {1997},
  doi     = {10.1093/oxfordjournals.molbev.a025808}
}

Contributing

Interested in contributing? See CONTRIBUTING.md for:

Development setup and workflow
Running tests and building the package
Code style guidelines

decenttree — The C++ library powering phylobuild
IQ-TREE — Maximum likelihood phylogenetics (also uses decenttree)
ape — The foundational R package for phylogenetics
phangorn — Phylogenetic reconstruction and analysis

License

GPL (>= 2), consistent with decenttree.

phylobuild 🌲