Stably encoding phylogenetic trees with folios of leaf addresses

As genome sequencing data continue to expand, a persistent research challenge is to accommodate the growth of a phylogeny. This situation arises in molecular epidemiology, for example, where new taxonomic groups can appear in real time as pathogen isolates are sequenced. Efficient computational methods have been developed to place new leaves in existing trees, which removes the need to reconstruct trees from scratch. But for these tree extensions to be fully integrated with classification schemes requires a stable encoding of trees that keeps existing tree structures intact as new branches appear. Here, we propose a tree encoding, which we call a folio, that records the path from a reference vertex to each leaf, giving each leaf an address. We present a simple set of rules to assign new addresses to added leaves. The encoding is stable in the sense that it does not change as further leaf addresses are added to the folio. The tree can be uniquely recovered from a folio of addresses. We illustrate the methods using Salmonella genome data. Due to the properties of our encoding framework, we anticipate that it can be used for a range of different phylogenetic analyses.