Vector Encoding of Phylogenetic Trees by Ordered Leaf Attachment

David Harry Richman, Cheng Zhang, Frederick A. MatsenBulletin 2026 · DOI

TL;DR

This paper introduces the "ordered leaf attachment" (OLA) method, a novel and efficient way to represent phylogenetic trees as integer vectors. This encoding is unique for its linear time complexity and a simple, convex set of resulting vectors, enabling new tree distance metrics that show promising relationships with established phylogenetic distances.

What Problem Does This Paper Address?

Phylogenetic trees are fundamental to understanding evolutionary relationships, but their complex, discrete structure makes them challenging to integrate with modern machine learning techniques, which often rely on vector representations. Existing methods for encoding trees into vectors have been computationally expensive or have resulted in complex vector spaces. This paper addresses the need for a simple, efficient, and mathematically well-behaved vector encoding of phylogenetic trees that can facilitate their analysis with machine learning and provide new ways to measure distances between trees.

Methods

The core contribution is the Ordered Leaf Attachment (OLA) encoding. The OLA method represents a rooted, binary phylogenetic tree with n leaves as an integer vector of length n-1. The encoding works by conceptually building the tree leaf by leaf. For each leaf added, the method records the label of its sister node. To handle internal nodes, a canonical labeling scheme is introduced where internal nodes are assigned negative integers. This process is described as a bijection between the set of rooted binary trees with a linear leaf ordering and a specific convex set of integer vectors. The authors also define an OLA distance between trees, which is simply the Hamming distance between their OLA vector encodings.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic properties rather than empirical evaluation on specific biological datasets.

Key Insights and Ideas

  • Linear Time Encoding: The OLA encoding and decoding algorithms are remarkably efficient, operating in linear time with respect to the number of leaves. This is a significant improvement over some previous methods.
  • Simple, Convex Vector Space: The set of all possible OLA vectors for n leaves forms a convex set defined by simple inequalities. This mathematical tractability is a key advantage for theoretical analysis and potential use in optimization.
  • Induced Tree Distance: The OLA vector encoding naturally induces a distance metric on trees. This OLA distance is shown to be related to established phylogenetic distances like NNI (nearest neighbor interchange) and SPR (subtree prune-regraft), offering a new perspective on tree similarity.
  • NNI vs. SPR Behavior: The OLA distance can be large for trees that differ by a single NNI move in the worst case, but its expected distance is bounded. For SPR moves, the OLA distance is bounded by a factor of the tree's height, suggesting a more consistent relationship.

Key Results

  • Bijection: The OLA encoding and decoding algorithms are proven to be inverse bijections between the set of rooted, binary, leaf-ordered trees and the defined set of integer vectors.
  • Linear Time Complexity: Both encoding and decoding algorithms are confirmed to have linear time complexity.
  • OLA Distance Bounds:
    • The expected OLA distance between a tree and its random NNI neighbor is bounded by 4.
  • The OLA distance between a tree and its SPR neighbor is bounded by twice the tree's height.
  • Empirical Support: Computational experiments support the theoretical bounds, showing that the OLA distance behaves reasonably well in relation to NNI and SPR moves, especially when averaged over leaf orderings.

Limitations and Future Work

  • Leaf Ordering Dependence: The OLA distance, like other vector-based distances, depends on the ordering of the leaves. The authors suggest that averaging over multiple leaf orderings can mitigate this, leading to "mean OLA distance" which shows improved correlation with SPR distance.
  • Extension to Unrooted Trees: While the definition is for rooted trees, the authors note it can be extended to unrooted trees by arbitrarily picking a root, though this introduces asymmetry.
  • Multifurcating Trees: The current OLA encoding is for binary trees. The authors mention that extensions to multifurcating trees have been explored by others.
  • Future Questions: The paper poses open questions about the expected number of negative entries in OLA encodings for different tree shapes and the variation of OLA distance under leaf shuffling. Further work is suggested to quantify how these encodings describe tree space and to extend the encoding to trees with branch lengths (which is briefly illustrated in the appendix).

Summary updated

Abstract

As part of work to connect phylogenetics with machine learning, there has been considerable recent interest in vector encodings of phylogenetic trees. We present a simple new "ordered leaf attachment" (OLA) method for uniquely encoding a binary, rooted phylogenetic tree topology as an integer vector. OLA encoding and decoding take linear time in the number of leaf nodes, and the set of vectors corresponding to trees is a simply-described subset of integer sequences. The OLA encoding is unique compared to other existing encodings in having these properties. The integer vector encoding induces a distance on the set of trees, and we investigate this distance in relation to the NNI and SPR distances.
BibTeX
@article{richman2026vector,
  author = {David Harry Richman and Cheng Zhang and Frederick A. Matsen},
  title = {{Vector Encoding of Phylogenetic Trees by Ordered Leaf Attachment}},
  journal = {Bulletin},
  year = {2026},
  doi = {10.1007/s11538-026-01611-9},
}
Figure