Prüfer Sequence Encoding of Phylogenetic Trees
A Prüfer sequence encodes a tree on n labelled vertices as a sequence of n-2 integers. On fully labelled trees the encoding is a bijection, which is the standard proof of Cayley's formula.
Phylogenetic trees are leaf-labelled, so the internal nodes have to be numbered before the algorithm can run. net_to_adj does that in a way that depends only on the tree itself, and not on how its Newick string happened to be written.
On leaf-labelled trees the encoding is injective but not surjective: most sequences of the right length decode to a graph that is not a valid phylogenetic tree, so prufer_decode is not the inverse of prufer_encode(::HybridNetwork).
PhyloClustering.net_to_adj — Function
net_to_adj(net::HybridNetwork) -> Vector{Vector{Int}}Convert a phylogenetic tree into a fully labeled adjacency list.
Phylogenetic trees are leaf-labeled: only the tips carry names. Prüfer coding needs every vertex to carry a label, so the internal nodes have to be numbered too, and that numbering has to depend on the tree alone — not on how the Newick string happened to be written.
Numbering
- Leaves take
1:n, by position insort(tiplabels(net)). This is the ruleget_bipartitionuses, so every encoding in this package agrees on leaf numbers;num_to_namerecovers the original names. - Internal nodes take
n+1and up, in the order a traversal first reaches them. The traversal starts at leaf 1 and, at each node, visits neighbours in increasing order of the smallest leaf number below them.
Leaf 1 is fixed by the taxon names, whereas the root of a HybridNetwork read from Newick is an artifact of where the string happened to start — so starting the traversal at leaf 1 is what makes the numbering canonical. Degree-2 nodes, the usual form that artifact takes, are removed first, so that the same unrooted tree always gives the same adjacency list however it was written.
The argument is not modified. Reticulations are not supported.
Example
julia> net = readnewick("(4:4.249,(1:2.457,(2:2.064,3:2.064):0.393):1.793);");
julia> length(net_to_adj(net)) # 4 leaves + 2 internal nodes
6PhyloClustering.prufer_encode — Function
prufer_encode(adj) -> Vector{Int}Encode a tree on n labeled vertices as a sequence of length n−2.
Algorithm: repeat n−2 times — find the smallest-labeled leaf v, append v's only neighbour to the sequence, and remove v.
Example
julia> adj = PhyloClustering.edges_to_adj([(1,4),(2,4),(3,4),(4,5),(5,6)], 6);
julia> prufer_encode(adj)
4-element Vector{Int64}:
4
4
4
5prufer_encode(tree::HybridNetwork) -> Vector{Int}Encode a phylogenetic tree, by way of net_to_adj.
An unrooted binary tree on n leaves has 2n−2 vertices, so the sequence has length 2n−4. Unlike the labeled-tree case this map is injective but not surjective: most sequences of that length decode to a graph that is not a valid phylogenetic tree, since nothing in the sequence forces the internal vertices to degree 3 or the leaf labels to degree 1. prufer_decode is therefore not its inverse. Characterising the image — the validity conditions — is still open; see reading/Prufer/notes.md.
PhyloClustering.prufer_decode — Function
prufer_decode(seq, n) -> Vector{Tuple{Int,Int}}Decode a Prüfer sequence of length n−2 into a tree on n labeled vertices, returned as an edge list (each edge as (u, v) with u < v, sorted globally).
Algorithm: maintain the candidate leaves — labels absent from the remaining sequence and not yet used. At each step take the smallest candidate, join it to the first element of the sequence, then consume that element; if the consumed label no longer appears in the remaining sequence, it becomes a candidate in turn. Once the sequence is exhausted, join the two labels that are left.
Every sequence over 1..n of length n−2 maps to a tree (the map is surjective), so this also serves as a uniform random tree generator: prufer_decode(rand(1:n, n-2), n).