TreeTools (version 0.1.3)

TreeNumber: Unique integer indices for bifurcating tree topologies

Description

Functions converting between phylogenetic trees and their unique decimal representation.

Usage

as.TreeNumber(x, ...)
# S3 method for phylo
as.TreeNumber(x, ...)
# S3 method for multiPhylo
as.TreeNumber(x, ...)
# S3 method for character
as.TreeNumber(x, nTip, tipLabels = TipLabels(nTip),
  ...)
# S3 method for numeric
as.phylo(x, nTip = attr(x, "nTip"),
  tipLabels = attr(x, "tip.label"), ...)
# S3 method for TreeNumber
as.phylo(x, nTip = attr(x, "nTip"),
  tipLabels = attr(x, "tip.label"), ...)

Arguments

x

Integer identifying the tree (see details).

…

Additional parameters for consistency with S3 methods (unused).

nTip

Integer specifying number of tips in the tree.

tipLabels

Character vector listing the labels assigned to each tip in a tree, perhaps obtained using TipLabels.

Value

as.phylo.numeric returns a tree of class phylo.

as.TreeNumber returns an object of class TreeNumber, which comprises a numeric vector, whose elements represent successive nine-digit chunks of the decimal integer corresponding to the tree topology (in big endian order). The TreeNumber object has attributes nTip and tip.labels.

Details

There are NUnrooted(n) unrooted trees with n tips. As such, each n-tip tree can be uniquely identifyed by a non-negative integer x < NUnrooted(n).

This integer can be converted by a tree by treating it as a mixed-base number, with bases 1, 3, 5, 7, ... (2_n_ - 5).

Each digit of this mixed base number corresponds to a tip, and determines the location on a growing tree to which that tip should be added.

We start with a two-tip tree, and treat 0 as the origin of the tree.

0 ---- 1

We add tip 2 by breaking an edge and inserting a node (numbered 2 + nTip - 1). In this example, we'll work up to a six-tip tree; this node will be numbered 2 + 6 - 1 = 7. There is only one edge on which tip 2 can be added. Let's add node 7 and tip 2:

0 ---- 7 ---- 1
       |
       |
       2

There are now three edges on which tip 3 can be added. Our options are: Option 0: the edge leading to 1; Option 1: the edge leading to 2; Option 2: the edge leading to 7.

If we select option 1, we produce:

0 ---- 7 ---- 1
       |
       |
       8 ---- 2
       |
       |
       3

1 is now the final digit of our mixed-base number

There are five places to add tip 4: Option 0: the edge leading to 1; Option 1: the edge leading to 2; Option 2: the edge leading to 3; Option 3: the edge leading to 7; Option 4: the edge leading to 8.

If we chose option 3, then 3 would be the penultimate digit of our mixed-base number

If we chose option 0 for the next two additions, we could specify this tree with the mixed-base number 0021. We can convert this into decimal:

0 <U+00D7> (1 <U+00D7> 3 <U+00D7> 5 <U+00D7> 9) +

0 <U+00D7> (1 <U+00D7> 3 <U+00D7> 5) +

3 <U+00D7> (1 <U+00D7> 3) +

1 <U+00D7> (1)

= 10

Note that the hyperexponential nature of tree space means that there are > 2^30 unique 12-tip trees. As integers > 2^31 are not supported by R, numbers representing larger trees are represented internally as a vector of nine-digit integer 'chunks' and passed to the underlying C code, where they are combined into a single 64-bit integer. This allows trees with up to 42 tips to be accommodated.

References

Based on a concept by John Tromp, employed in Li et al. 1996.

Li1996TreeTools

See Also

TreeShape

Other tree generation functions: BalancedTree, NJTree, PectinateTree, RandomTree, SingleTaxonTree

Examples

# NOT RUN {
tree <- as.phylo(10, nTip = 6)
plot(tree)
as.TreeNumber(tree)

# Larger trees:
as.TreeNumber(BalancedTree(19))

# If > 9 digits, represent the tree number as a string.
treeNumber <- as.TreeNumber("1234567890123", nTip = 14)
tree <- as.phylo(treeNumber)

as.phylo(0:2, nTip = 6, tipLabels = letters[1:6])

# }