phylo2vec: a library for vector-based phylogenetic tree manipulation
Neil Scheidwasser, Ayush Nag, Matthew J Penn, Anthony MV Jakob, Frederik Mølkjær Andersen, Mark P Khurana, Landung Setiawan, Madeline Gordon, David A Duchêne, Samir Bhatt · 2025
Read phylo2vec: a library for vector-based phylogenetic tree manipulation by Neil Scheidwasser, Ayush Nag, Matthew J Penn, Anthony MV Jakob, Frederik Mølkjær Andersen, Mark P Khurana, Landung Setiawan, Madeline Gordon, David A Duchêne, Samir Bhatt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19490.txt.
Introduction
Neil Scheidwasser and co-authors release a software library in a 2025 paper on family trees of species. Phylogenies, the branching trees of evolution, now grow huge in the age of genome scale data and virus tracking. The old text format for trees, nested brackets in a long string, gets unwieldy at that size.
Newer schemes encode a tree as a short vector of whole numbers instead. The library wraps that encoding for daily work: building trees, editing them, and converting between formats. Number vectors are fast to store, compare, and feed to other programs. The tool targets pipelines that juggle thousands of trees at once.
Catalog record
| CREATOR | Neil Scheidwasser, Ayush Nag, Matthew J Penn, Anthony MV Jakob, Frederik Mølkjær Andersen, Mark P Khurana, Landung Setiawan, Madeline Gordon, David A Duchêne, Samir Bhatt |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 7 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-19490
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
phylo2vec: a library for vector-based phylogenetic tree manipulation
Neil Scheidwasser, Ayush Nag, Matthew J Penn, Anthony MV Jakob, Frederik Mølkjær Andersen, Mark P Khurana, Landung Setiawan, Madeline Gordon, David A Duchêne, Samir Bhatt
Abstract
Summary
Phylogenetics is a fundamental component of many analysis frameworks in
biology (
[
ref-yang2014
]
) as well as linguistics
(
[
ref-atkinson2005
]
) to study the
evolutionary relationships of different entities. Recently, the advent
of large-scale genomics and the SARS-CoV-2 pandemic has underscored the
necessity for phylogenetic software to handle large datasets of genomes
or phylogenetic trees (
[
ref-attwood2022
]
;
[
ref-kapli2020
]
;
[
ref-khurana2024
]
;
[
ref-kraemer2025
]
). While significant
efforts have focused on scaling optimisation algorithms
(
[
ref-demaio2023
]
;
[
ref-sanderson2021
]
;
[
ref-turakhia2021
]
), visualization
(
[
ref-sanderson2022
]
), and lineage
identification (
[
ref-mcbroome2024
]
), an
emerging body of research has been dedicated to efficient
representations of data for genomes
(
[
ref-deorowicz2023
]
) and phylogenetic
trees such as phylo2vec (
[
ref-chauve2025
]
;
[
ref-penn2024
]
;
[
ref-richman2025
]
). Compared to
traditional tree representations such as the Newick format
(
[
ref-felsenstein2004
]
), which represents
trees using strings of nested parentheses, modern representations of
phylogenetic trees utilize integer vectors to define the tree topology
traversal. This approach offers several advantages, including easier
manipulability, increased memory efficiency, and applicability to
downstream tasks such as machine learning.
Here, we present the latest release of
phylo2vec
(or
Phylo2Vec), a high-performance software package for encoding,
manipulating, and analysing binary phylogenetic trees. At its core, the
package is based on the phylo2vec (
[
ref-penn2024
]
) representation of binary trees, which defines a bijection from
any tree topology with
n
leaves into an integer vector of size
n-1
. Compared to the traditional Newick format, phylo2vec is
designed to enable fast sampling and comparison of binary trees. This
release features a core implementation in Rust, providing significant
performance improvements and memory efficiency
(
Figure 1
), while remaining available in Python
(superseding the release described in the original paper
(
[
ref-penn2024
]
)) and R via dedicated
wrappers, making it accessible to a broad audience in the bioinformatics
community.
Figure 1:
Benchmark times for converting a phylo2vec vector to a Newick
string (left) and vice versa (right). For each size, we evaluated the
execution time for a minimum of 20 rounds using
pytest-benchmark
. We compare the execution time of the Python
functions in the latest release, which rely on Rust bindings via
PyO3
, with the previous release
(
[
ref-penn2024
]
), which make use of
just-in-time (JIT) compilation of Python functions using
Numba
(
[
ref-lam2015
]
). Execution times were
benchmarked on an AMD Ryzen Threadripper PRO 5995WX with a 64-core CPU @
7 GHz and 256 GB of RAM.
Statement of need
The purpose of the
phylo2vec
library is threefold. First, the
core of the library aims at providing a robust phylogenetic tree
manipulation library in Rust, complementing other efforts such as
light_phylogeny
(
[
ref-duchemin2018
]
), which focuses on tree visualization and manipulation of
reconciled phylogenies (
[
ref-nakhleh2013
]
), and
rust-bio
(
[
ref-koster2016
]
), a
comprehensive bioinformatics library which does not yet cover
phylogenetics. Second,
phylo2vec
aims at complementing existing
phylogenetic libraries such as
ape
(
[
ref-paradis2019
]
) in R, and
ete3
(
[
ref-huerta2016
]
) and
DendroPy
(
[
ref-Moreno2024
]
) in
Python, by providing fast tree sampling, fast tree comparison and
efficient tree data compression (
[
ref-penn2024
]
). Third, the inherent tree representation of phylo2vec offers a
pathway to several optimisation frameworks for phylogenetic inference. A
notable example is GradME (
[
ref-penn2023
]
),
a gradient descent-based algorithm which uses a relaxed representation
of phylo2vec into a continuous space.
Features
The presented release of
phylo2vec
addresses several
limitations of (
[
ref-penn2024
]
). From an
optimisation perspective, it introduces efficient
\mathcal{O}(n\log n)
implementations for both vector-to-Newick and
Newick-to-vector conversions, leveraging Adelson-Velsky and Landis (AVL)
trees (
[
ref-adelson1962
]
) and Fenwick trees (
[
ref-fenwick1994
]
),
respectively.
In terms of new features, it supports branch length annotations by
extending the vector representation of size
n-1
to a matrix of size
(n-1)\times 3
, where
n
denotes the number of leaves (or taxa)
in a tree (
Figure 2
). Further enhancements include
several leaf-level operations (pruning, placement, MRCA identification),
fast cophenetic distance matrix calculation, and various optimisation
schemes based on phylo2vec tree representations, notably hill-climbing
and GradME (
[
ref-penn2023
]
). Bayesian
phylogenetic inference via Markov Chain Monte Carlo (MCMC) with
phylo2vec matrices is also made possible by a likelihood function that
leverages tree representation similarities between phylo2vec and
BEAGLE
, a highly optimised library that underpins a number of
phylogenetic software (
[
ref-ayres2012
]
;
[
ref-suchard2009
]
). Finally,
user-friendliness is enhanced by step-by-step demos of the inner
workings of phylo2vec’s representations and their conversion to commonly
used phylogenetic tree formats (e.g., Newick string, list of edges).
Figure 2:
Recovering a tree from a phylo2vec vector: example for
\boldsymbol{v}=[0,2,0,4]
. (a) Main algorithm for leaf placement
described in (
[
ref-penn2024
]
). (b)
Augmenting the phylo2vec vector into a matrix
\boldsymbol{m}
with
branch lengths. We use an intermediary ancestry matrix whereby each row
describes a cherry (two children nodes and the parent node), which we
augment with two columns of branch lengths. The node with the smallest
descendant will have the branch length in the 2nd column, and the other
the branch length in the 3rd column.
Maintenance
With Phylo2Vec, we aim to support long-term maintenance through
implementing recommended software practices explicitly into the
structure of the project and development workflow. More specifically, we
have structured the project such that the Rust API contains the core
algorithms, and all other language components are APIs that bind to the
Rust functions. This avoids tight coupling, as it allows for the
possibility of adding new languages to bind to the Rust API’s, without
needing to change anything in the Rust project itself. Additionally, we
have established a robust continuous integration (CI) pipeline using
GitHub Actions, which features:
•
Unit test frameworks for Rust (
cargo
),
Python (
pytest
), and R
(testthat (
[
ref-wickham2011
]
))
•
Benchmarking on the Rust code
(
criterion
) and its
Python bindings
(
pytest-benchmark
)
Lastly, to complement Jupyter Notebook demos, comprehensive
documentation is provided using
Jupyter
Book
and
Read The Docs