skbio.tree.BPTree#

class skbio.tree.BPTree(B, lengths=None, names=None, edges=None)[source]#

A balanced parentheses succinct data structure tree representation.

The basis for this implementation is the data structure described by Cordova and Navarro [1]. In some instances, some docstring text was copied verbatim from the manuscript. This does not implement the bucket-based trees.

A node in this data structure is represented by 2 bits, an open parenthesis and a close parenthesis. The implementation uses a NumPy uint8 type where an open parenthesis is a 1 and a close is a 0. In general, operations on this tree are best suited for passing in the opening parenthesis index, so for instance, if you’d like to use BPTree.is_tip to determine if a node is a leaf, the operation is defined only for using the opening parenthesis. At this time, there is some ambiguity over what methods can handle a closing parenthesis.

Node attributes, such as names, are stored external to this data structure.

The motivator for this data structure is pure performance both in space and time. As such, there is minimal sanity checking. It is advised to use this structure with care, and ideally within a framework which can assure sanity.

Parameters:

Barray of uint8: The parentheses bit array encoding the tree topology, where an open parenthesis is 1 and a close parenthesis is 0. A bool array is also accepted, and is viewed as uint8. It may belong to any array API backend (e.g., CuPy, PyTorch or JAX) and live on any device; see Notes.
lengthsnumpy.ndarray of float64, optional: Branch length per parenthesis (read at opening parentheses). Defaults to 0.
namesnumpy.ndarray of object, optional: Node name per parenthesis (read at opening parentheses). Defaults to None.
edgesnumpy.ndarray of int32, optional: Edge number per parenthesis (read at opening parentheses). Defaults to 0, without an edge-number lookup.

Attributes:

dataarray of uint8: The parentheses bit array (1 = open, 0 = close).

Notes

The tree’s arrays, including the navigation index built from data, are held by this Python object. Operations on them are computed by a compiled (Cython) engine: per-node navigation methods (e.g., parent, lca) are bound directly to the engine when the tree is created, so they run at compiled speed.

The navigation methods take positions in data, from 0 to data.size - 1. For any other position, e.g. the -1 that parent returns for the root, they return -1 (is_tip and is_ancestor return False) rather than read outside the tree’s arrays, so a -1 passed from one method to another gives -1 again.

A tree created from a non-NumPy B, e.g. a CuPy array or a PyTorch tensor on a GPU, keeps B as its data and a host copy of it, from which it is built and navigated as any other tree. The node attributes (lengths, names, edges) are NumPy arrays on the host. A tree created otherwise, e.g. read from a file, is moved to a GPU (or any backend and device) with to_device, which rebuilds nothing.

The batch operations (e.g. lca_batch) and cophenet with engine="numba" run on the GPU if B is on a CUDA or ROCm device and a Numba GPU extension for it is installed (numba-cuda-mlir, or the deprecated numba-cuda, on CUDA; numba-hip on ROCm). Otherwise, or if the GPU kernel cannot be built on the system (which is warned about once), they run on the host. A call that runs out of device memory runs on the host, with a warning, and later calls still run on the GPU.
On a GPU, they run on the device of data, whichever device is current; queries on another GPU raise a ValueError.
The batch operations return their result in the array backend and on the device of their queries, and cophenet a distance matrix in those of data.
Operations creating a new tree (shear, collapse, pickling) and those exporting it (to_array, to_npz) work on the host copy, and create NumPy trees and arrays.

The fast engine. The batch operations and cophenet run the same algorithm, with bit-identical results, on either engine, so engine="fast" is chosen from where the tree is and how scikit-bio was built, rather than fixed:

"numba" if the tree’s data is on a GPU the Numba kernels can use (see above).
Otherwise "cython" if scikit-bio was built with OpenMP, as it is with GCC on Linux: its kernels are multithreaded, and compile nothing at the first call, where Numba compiles each kernel.
Otherwise "numba" if Numba is installed, as the Cython kernels then run on a single thread.
Otherwise "cython".

After a GPU kernel has failed on the system, "fast" follows rules 2-4.

References

[1] http://www.dcc.uchile.cl/~gnavarro/ps/tcs16.2.pdf

Attributes

`data`	The parentheses bit array (1 = open, 0 = close).
`default_write_format`
`edges`	Edge number per parenthesis (read at opening parentheses).
`lengths`	Branch length per parenthesis (read at opening parentheses).

Tree IO

`read`	Create a new `BPTree` instance from a file.
`write`	Write an instance of `BPTree` to a file.
`to_npz`	Save the tree to a compressed NumPy `.npz` archive.
`from_npz`	Load a tree from a NumPy `.npz` archive written by `to_npz`.

Tree navigation

`root`	The index of the root node of the tree.
`parent`	The parent of node.
`first_child`	Index of the first (leftmost) child of a node.
`last_child`	Index of the last (rightmost) child of a node.
`next_sibling`	Index of the next (right) sibling of a node.
`previous_sibling`	Index of the previous (left) sibling of a node.
`lca`	The lowest common ancestor of two nodes.
`is_ancestor`	Whether a node is an ancestor of another node.
`deepest_node`	Index of the deepest node descending from a node.

Tree traversal

`preorder_rank`	Preorder rank of a node.
`postorder_rank`	Postorder rank of a node.
`preorder_select`	Index of the node with a given preorder rank.
`postorder_select`	Index of the node with a given postorder rank.
`level_ancestor`	Index of the ancestor a given number of levels above a node.
`level_next`	Index of the next node at the same depth.

Tree analysis

`is_tip`	Whether the node is a tip of a tree.
`depth`	The depth of given node.
`height`	The height of node i with respect to its deepest descendent
`count`	Get the count of nodes in the subtree rooted at a node.

Batch operations

`close_batch`	Matching closing parenthesis of each position in a batch.
`parent_batch`	Parent of each node in a batch.
`lca_batch`	Lowest common ancestor of each pair of nodes in a batch.
`level_ancestor_batch`	Ancestor a given number of levels above each node in a batch.
`cophenet`	Return a distance matrix between each pair of tips in the tree.

Node positions and compiled kernels

`tip_positions`	Positions of the tips, in tree order.
`positions`	Positions of named nodes.
`name`	Name of a node.
`numba_arrays`	The tree's arrays, for the Numba navigation functions.

Tree manipulation

`shear`	Remove all nodes from the tree except tips and ancestors of tips.
`collapse`	Collapse single-child internal nodes.

Tree conversion

`from_treenode`	Construct a BPTree from a `TreeNode`.
`to_array`	Return an array representation of the tree.
`to_device`	Return this tree with its data in an array backend and on a device.

Special methods

`__len__`	The number of nodes in the tree.
`__str__`	Return a concise summary of the tree.

Special methods (inherited)

`__eq__`	Return self==value.
`__ge__`	Return self>=value.
`__getstate__`	Helper for pickle.
`__gt__`	Return self>value.
`__hash__`	Return hash(self).
`__le__`	Return self<=value.
`__lt__`	Return self<value.
`__ne__`	Return self!=value.

Details

data#

The parentheses bit array (1 = open, 0 = close).

It is in the array backend and on the device of the array the tree was created from. For a NumPy array, it is a read-only view: the topology cannot change once the tree exists, as the navigation index is built from it. The tree keeps the array it was created from, without a copy, so that array must not be changed either.

default_write_format = 'newick'#

edges#

Edge number per parenthesis (read at opening parentheses).

A read-only view: use set_edges to change the edge numbers. It is a NumPy array on the host, whatever the backend of data.

lengths#

Branch length per parenthesis (read at opening parentheses).

A read-only view: use set_lengths to change the lengths. It is a NumPy array on the host, whatever the backend of data.

__len__()[source]#: The number of nodes in the tree.

__str__()[source]#

Return a concise summary of the tree.

Implements the abstract __str__ required of scikit-bio objects.