Given a number of tips, permutes all rooted unlabelled multifurcating trees (i.e., treeshapes).
permute_treeshapes(n_tips, sort_by_resolution = TRUE)If sort_by_resolution = TRUE then returns a list of length N - 1, where each element is a character vector of treeshapes in Newick-style number format with that many internal nodes. I.e., the first value will always be the star tree. If sort_by_resolution = FALSE then will just be a character vector of treeshapes in Newick-style number format.
The number of tips required. Note that it may be very slow or not run at all if this value is too large.
Whether or not to sort the output by number of internal nodes (from 1 to N - 1). Defaults to TRUE.
Graeme T. Lloyd graemetlloyd@gmail.com
A treeshape is essentially an unlabelled phylogenetic tree. Like other phylogenetic trees it has a root and tips, but (as you might expect) because it is unlabelled the tips have no specific identity. Thus the only information it contains is its' "shape" - the number of internal nodes and their descendants. This function permutes all unique treeshapes and allows for multifurcations.
Note that unique means it excludes alternative rotations of individual branch points. For example, the trees ((2),1); and (1,(2)); are identical in information content and this function would only permute one of them.
The algorithm used here is loosely based on the partitions approach suggested in Felsenstein (2004), although to the best of my knowledge nobody else has formally created an algorithm to do this. (Felsenstein also lays out the expected number of such treeshapes for each value of N.)
Here treeshapes are encoded and output in a pseudo-Newick style format where labels are replaced with the number of tips, e.g.:
(((3),1),(1,(2)));
Thus each pair of parentheses represents an internal node, each number the number of tips, each comma separates sets of tips, and the semicolon denotes the root clade.
Felsenstein, J., 2004. Inferring Phylogenies. Sinauer Associates, Inc., Sunderland.
# Permute all treeshapes of six tips:
permute_treeshapes(n_tips = 6)
Run the code above in your browser using DataLab