cassiopeia.data.CassiopeiaTree

class cassiopeia.data.CassiopeiaTree(character_matrix=None, missing_state_indicator=- 1, cell_meta=None, character_meta=None, priors=None, tree=None, dissimilarity_map=None, root_sample_name=None)

Basic tree object for Cassiopeia.

This object stores the key attributes and functionalities a user might want for working with lineage tracing experiments. At its core, it stores three main items - a tree, a character matrix, and meta data associated with the data.

The tree can be fed into the object via Ete3, Networkx, or can be inferred using one of the CassiopeiaSolver algorithms in the solver module. The tree here is only used for obtaining the _topology_ of the tree.

A character matrix can be stored in the object, containing the states observed for each cell. In typical lineage tracing experiments, these are integer representations of the indels observed at each unique cut site. We track both an unmodified version of the character matrix (obtainable via the get_original_character_matrix method) that does not maintain consistency with the character states of the leaves, and a working character matrix (obtainable via the get_current_character_matrix method) that is updated when the character states of leaves are changed.

Some reconstruction algorithms will make use of dissimilarities between cells. To this end, we store these dissimilarity maps in the CassiopeiaTree class itself. For users trying to diagnose the reconstruction accuracy with a known groundtruth, they can compare this dissimilarity map to the phylogenetic distance on the tree.

Meta data for cells or characters can also be stored in this object. These items can be categorical or numerical in nature. Common examples of cell meta data are the cluster identity, tissue identity, or number of target-site UMIs per cell. These items can be used in downstream analyses, for example the FitchCount algorithm which infers the number of transitions between categorical variables (e.g., tissues). Common examples of character meta data are the proportion of missing data for each character or the entropy of states. These are good statistics to have for feature selection.

TODO(rzhang): Add check upon initialization that input tree is valid tree. TODO(mattjones315): Add experimental meta data as arguments. TODO(mattjones315): Add utility methods to compute the colless index

and the cophenetic correlation wrt to some cell meta item

TODO(mattjones315): Add bulk set_states method. TODO(mattjones): Add boolean to get_tree_topology which will include

all attributes (e.g., node times)

Parameters

character_matrix : DataFrame, NoneOptional[DataFrame] (default: None)

The character matrix for the lineage.

missing_state_indicator : intint (default: -1)

An indicator for missing states in the character matrix.

cell_meta : DataFrame, NoneOptional[DataFrame] (default: None)

Per-cell meta data

character_meta : DataFrame, NoneOptional[DataFrame] (default: None)

Per-character meta data

priors : {int: {int: float}}, NoneOptional[Dict[int, Dict[int, float]]] (default: None)

A dictionary storing the probability of each character mutating to a particular state.

tree : str, TreeNode, DiGraph, NoneUnion[str, TreeNode, DiGraph, None] (default: None)

A tree for the lineage.

dissimilarity_map : DataFrame, NoneOptional[DataFrame] (default: None)

An NxN dataframe storing the pairwise dissimilarities between samples.

root_sample_name : str, NoneOptional[str] (default: None)

The name of the sample to treat as the root. This is not always used, but will be added if needed during tree reconstruction. If the user already has a sample in the character matrix or dissimilarity map that they would like to use as the phylogenetic root, they can specify it here.

Methods

populate_tree(tree, layer=None)

Populates a tree object in CassiopeiaTree.

Accepts a tree topology and introduces the topology into the object. In doing so, this function will also append character states to the leaves of the tree topology, if possible, and instantiate edge lengths by default to be length 1. Node times will be instantiated as well, corresponding to their tree depth.

Parameters

tree : str, TreeNode, DiGraphUnion[str, TreeNode, DiGraph]

A tree topology specified as a networkx DiGraph, a newick string, or an ete3 Tree.

layer : str, NoneOptional[str] (default: None)

Layer to use for character matrix. If this is None, then the current character_matrix variable will be used.

Return type

NoneNone

property layers: cassiopeia.data.Layers.Layers

Dictionary object storing versions of character matrices.

Layers in this CassiopeiaTree object are inspired by AnnData’s layers functionality. All layers have the same number of samples as the tree and character_matrix.

Return the layer named “missing”::

cas_tree.layers[“missing”]

Create or replace the “merged” layer::

cas_tree.layers[“merged”] = …

Delete the “missing” layer::

del cas_tree.layers[“missing”]

Return type

LayersLayers

property character_matrix: pandas.core.frame.DataFrame

Return type

DataFrameDataFrame

set_character_states_at_leaves(character_matrix=None, layer=None)

Populates character states at leaves.

Assigns character states to the leaves of the tree. This function must have a character state assignment to all leaves of the tree. If no argument is passed, the default character_matrix is used to set character states at the leaves.

Parameters

character_matrix : DataFrame, Dict, NoneUnion[DataFrame, Dict, None] (default: None)

A separate character matrix to use for setting character states at the leaves. This character matrix is not stored in the object afterwards. If this is None, uses the default character matrix stored in character_matrix

layer : str, NoneOptional[str] (default: None)

Layer to use for resetting character information at leaves. If this is None, uses the default character matrix stored in character_matrix.

Raises

CassiopeiaTreeError if not all leaves are accounted for or if the – tree has not been initialized.

Return type

NoneNone

set_all_character_states(character_state_mapping, add_layer=None)

Populates character states across the tree.

Assigns character states to all of the nodes in the tree. The mapping must have an entry for every node in the tree.

Parameters

character_state_mapping : {str: List[int]}Dict[str, List[int]]

A mapping containing character state assignments for every node

add_layer : str, NoneOptional[str] (default: None)

Layer to which to add the new character matrix. If this is None, then the specified character matrix will be set to the default matrix in this object.

Raises

CassiopeiaTreeError if the tree is not initialized or if the – character_state_mapping does not contain assignments for every node.

Return type

NoneNone

freeze_character_matrix(add_layer)

Freezes character matrix in specified layer.

Adds a new layer the CassiopeiaTree object corresponding to the current version of the character matrix.

Parameters

add_layer : strstr

Layer to create.

Raises

• CassiopeiaTreeError if no character matrix exists to freeze. –

• CassiopeiaTreeWarning if layer already exists. –

property n_cell: int

Returns number of cells in tree.

Raises

• CassiopeiaTreeError if the object is empty (i.e. no tree or –

• character matrix) –

Return type

intint

property n_character: int

Returns number of characters in character matrix.

Raises

• CassiopeiaTreeError if the object is empty (i.e. no tree or –

• character matrix) or if the character states have not been –

• initialized. –

Return type

intint

property root: str

Returns root of tree.

Return type

strstr

Returns

The root.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

property leaves: List[str]

Returns leaves of tree.

Return type

List[str]List[str]

Returns

The leaves of the tree.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

property internal_nodes: List[str]

Returns internal nodes in tree (including the root).

Return type

List[str]List[str]

Returns

The internal nodes of the tree (i.e. all nodes not at the leaves)

Raises

CassiopeiaTreeError if the tree has not been initialized. –

property nodes: List[str]

Returns all nodes in tree.

Return type

List[str]List[str]

Returns

All nodes of the tree (internal + leaves)

Raises

CassiopeiaTreeError if the tree has not been initialized. –

property edges: List[Tuple[str, str]]

Returns all edges in the tree.

Return type

List[Tuple[str, str]]List[Tuple[str, str]]

Returns

All edges of the tree.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

is_leaf(node)

Returns whether or not the node is a leaf.

Return type

boolbool

Returns

Whether or not the node is a leaf.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

is_root(node)

Returns whether or not the node is the root.

Return type

boolbool

Returns

Whether or not the node is the root.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

is_internal_node(node)

Returns whether or not the node is an internal node.

Return type

boolbool

Returns

Whether or not the node is an internal node (i.e. out degree is greater than 0). In this case, the root is considered an internal node.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

is_ambiguous(node)

Returns whether the node is ambiguous.

This is detected by checking if any of the characters are tuples.

Parameters

node : strstr

Name of the node to check if it has ambiguous character(s)

Return type

boolbool

Returns

True if the node is ambiguous, False otherwise.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

collapse_ambiguous_characters()

Only retain unique characters for ambiguous nodes.

Ambiguous nodes have character strings represented as a list of tuples of integers. The inner list may contain multiple of the same states, encoding the relative abundance of a certain state in the ambiguous state distribution. Calling this function removes such duplicates and only retains unique characters. This function is idempotent and does nothing for trees that have no ambiguous characters.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

resolve_ambiguous_characters(resolve_function=<function resolve_most_abundant>)

Resolve all nodes with ambiguous characters.

A custom resolve_function may be provided to perform the resolution. By default, the most abundant state is selected. One is randomly selected on ties. Modifies the tree in-place.

Parameters

resolve_function : Callable[[Tuple[int, …]], int]Callable[[Tuple[int, …]], int] (default: <function resolve_most_abundant at 0x7f6b485e3048>)

Function that performs character resolution. This function is called once per ambiguous character state, and thus takes a single integer tuple as its argument and returns the resolved character state.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

reconstruct_ancestral_characters()

Reconstruct ancestral character states.

Reconstructs ancestral states (i.e., those character states in the internal nodes) using the Camin-Sokal parsimony criterion (i.e., irreversibility). Operates on the tree in place.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

parent(node)

Gets the parent of a node.

Parameters

node : strstr

A node in the tree

Return type

strstr

Returns

The parent of the node.

Raises

CassiopeiaTreeError if the tree is not initialized. –

children(node)

Gets the children of a given node.

Parameters

node : strstr

A node in the tree.

Return type

List[str]List[str]

Returns

A list of nodes that are direct children of the input node.

Raises

CassiopeiaTreeError if the tree is not initialized. –

set_time(node, new_time)

Sets the time of a node.

Importantly, this maintains consistency with the rest of the tree. In other words, setting the time of a particular node will change the length of the edge leading into the node and the edges leading out. This function requires monotonicity of times are maintained (i.e. no negative branch lengths).

Parameters

node : strstr

Node in the tree

new_time : floatfloat

New time for the node.

Raises

CassiopeiaTreeError if the tree is not initialized, if the new – time is less than the time of the parent, or if monotonicity is not maintained.

Return type

NoneNone

set_times(time_dict)

Sets the time of all nodes in the tree.

Importantly, this maintains consistency with the rest of the tree. In other words, setting the time of all nodes will change the length of the edges too. This function requires monotonicity of times are maintained (i.e. no negative branch lengths).

Parameters

time_dict : {str: float}Dict[str, float]

Dictionary mapping nodes to their time.

Raises

• CassiopeiaTreeError if the tree is not initialized, or if the time –

• of any parent is greater than that of a child. –

Return type

NoneNone

get_time(node)

Gets the time of a node.

Returns the time of a node, defined as the sum of edge lengths from the root to the node.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

floatfloat

get_times()

Gets the times of all nodes.

Returns the times of all nodes, defined as the sum of edge lengths from the root to that node.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

{str: float}Dict[str, float]

set_branch_length(parent, child, length)

Sets the length of a branch.

Adjusts the branch length of the specified parent-child relationship. This procedure maintains the consistency with the rest of the times in the tree. Namely, by changing the branch length here, it will change the times of all the nodes below the parent of interest, relative to the difference between the old and new branch length.

Parameters

parent : strstr

Parent node of the edge

child : strstr

Child node of the edge

length : floatfloat

New edge length

Raises

CassiopeiaTreeError if the tree is not initialized, if the edge – does not exist, or if the edge length is negative.

Return type

NoneNone

set_branch_lengths(branch_length_dict)

Sets the length of multiple branches on a tree.

Adjusts the branch length of specified parent-child relationships. This procedure maintains the consistency with the rest of the times in the tree. Namely, by changing branch lengths here, it will change the times of all the nodes in the tree such that the times are representative of the new branch lengths.

Parameters

branch_dict

A dictionary of edges to updated branch lengths

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

get_branch_length(parent, child)

Gets the length of a branch.

Raises

CassiopeiaTreeError if the tree has not been initialized or if the – branch does not exist in the tree.

Return type

floatfloat

set_character_states(node, states, layer=None)

Sets the character states for a particular node.

Parameters

node : strstr

Node in the tree

states : List[int], List[Tuple[int, …]]Union[List[int], List[Tuple[int, …]]]

A list of states to add to the node.

layer : str, NoneOptional[str] (default: None)

Name of layer to modify. If the layer is not specified, character_matrix is modifed directly.

Raises

CassiopeiaTreeError if the character vector is the incorrect length, – or if the node of interest is a leaf that has not been instantiated.

Return type

NoneNone

get_character_states(node)

Gets all the character states for a particular node.

Parameters

node : strstr

Node in the tree.

Return type

List[int], List[Tuple[int, …]]Union[List[int], List[Tuple[int, …]]]

Returns

The full character state array of the specified node.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

get_all_ancestors(node, include_node=False)

Gets all the ancestors of a particular node.

Nodes that are closest to the given node appear first in the list. The ancestors, including those of all intermediate nodes, are cached.

Parameters

node : strstr

Node in the tree

include_node : boolbool (default: False)

Whether or not to include the node itself in the list of ancestors. If True, the first element of the list is the node itself.

Return type

List[str]List[str]

Returns

The list of nodes along the path from the root to the node.

depth_first_traverse_nodes(source=None, postorder=True)

Nodes from depth first traversal of the tree.

Returns the nodes from a DFS on the tree.

Parameters

source : int, NoneOptional[int] (default: None)

Where to begin the depth first traversal.

postorder : boolbool (default: True)

Return the nodes in postorder. If False, returns in preorder.

Return type

Iterator[str]Iterator[str]

Returns

A list of nodes from the depth first traversal.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

depth_first_traverse_edges(source=None)

Edges from depth first traversal of the tree.

Returns the edges from a DFS on the tree.

Parameters

source : int, NoneOptional[int] (default: None)

Where to begin the depth first traversal.

Return type

Iterator[Tuple[str, str]]Iterator[Tuple[str, str]]

Returns

A list of edges from the depth first traversal.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

leaves_in_subtree(node)

Get leaves in subtree below a given node.

Parameters

node

Root of the subtree.

Return type

List[str]List[str]

Returns

A list of the leaves in the subtree rooted at the specified node.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

get_newick(record_branch_lengths=False)

Returns newick format of tree.

Parameters

record_branch_lengths

Whether to record branch lengths on the tree

the newick string : in

Return type

strstr

Returns

The tree in the form of a newick string

Raises

CassiopeiaTreeError if the tree has not been initialized. –

get_tree_topology()

Returns the tree in Networkx format.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

DiGraphDiGraph

get_mean_depth_of_tree()

Computes mean depth of tree.

Returns the mean depth of the tree. If branch lengths have not been estimated, depth is by default the number of edges in the tree.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

floatfloat

get_max_depth_of_tree()

Computes the max depth of the tree.

Returns the maximum depth of the tree. If branch lengths have not been estimated, depth is by default the number of edges in the tree.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

floatfloat

get_mutations_along_edge(parent, child)

Gets the mutations along an edge of interest.

Returns a list of tuples (character, state) of mutations that occur along an edge. Characters are 0-indexed.

Parameters

parent : strstr

parent in tree

child : strstr

child in tree

Return type

List[Tuple[int, int]]List[Tuple[int, int]]

Returns

A list of (character, state) tuples indicating which character

mutated and to which state.

Raises

CassiopeiaTreeError if the edge does not exist or if the tree is – not initialized.

relabel_nodes(relabel_map)

Relabels the nodes in the tree.

Renames the nodes in the tree according to the relabeling map. Modifies the tree in-place.

Parameters

relabel_map : {str: str}Dict[str, str]

A mapping of old names to new names.

Raises

CassiopeiaTreeError if the tree is not initialized. –

Return type

NoneNone

add_leaf(parent, node, states=None, time=None, branch_length=None, dissimilarity=None)

Add a leaf to the given parent node.

The parent node may NOT also be a leaf, as this makes bookkeeping the character, dissimilarity and cell meta quite complicated. Also, adding a leaf to an existing leaf is probably not a common use case.

Optional arguments states, time, branch_length, dissimilarity may be provided to initialize the character string, time, branch length, dissimilarity, and cell meta for this leaf respectively. See __register_data_with_tree() for default values that are used when any of these are not provided.

Note that only one of time and branch_length may be provided, and when neither are provided, the new leaf is added at the same time as the parent.

Parameters

parent : strstr

Parent node, to which to connect the leaf

node : strstr

Name of the leaf to add

states : List[int], List[Tuple[int, …]], NoneUnion[List[int], List[Tuple[int, …]], None] (default: None)

Character states to initialize the new leaf with

time : float, NoneOptional[float] (default: None)

Time to place the new leaf

dissimilarity : {str: float}, NoneOptional[Dict[str, float]] (default: None)

Indel dissimilarity between the new leaf and all other leaves

meta

Cell metadata

Raises

CassiopeiaTreeError if parent does not exist or node – already exists, if parent is a leaf, if the tree has not been initialized, or if both time and branch_length are provided.

Return type

NoneNone

remove_leaf_and_prune_lineage(node)

Removes a leaf from the tree and prunes the lineage.

Removes a leaf and all ancestors of that leaf that are no longer the ancestor of any leaves. In the context of a phylogeny, this prunes the lineage of all nodes no longer relevant to observed samples. Additionally, maintains consistency with the updated tree by removing the node from all leaf data.

Parameters

node : strstr

The leaf node to be removed

Raises

• CassiopeiaTreeError if the tree is not initialized or input node is –

• not a leaf –

Return type

NoneNone

collapse_unifurcations(source=None)

Collapses unifurcations on the tree.

Removes all internal nodes that have in degree and out degree of 1, connecting their parent and children nodes by branchs with lengths equal to the total time elapsed from parent to each child. Therefore preserves the times of nodes that are not removed.

Parameters

source : int, NoneOptional[int] (default: None)

The node at which to begin the tree traversal

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

collapse_mutationless_edges(infer_ancestral_characters)

Collapses mutationless edges in the tree in-place.

Uses the internal node annotations of a tree to collapse edges with no mutations. The introduction of a missing data event is considered a mutation in this context. Either takes the existing character states on the tree or infers the annotations bottom-up from the samples obeying Camin-Sokal Parsimony. Preserves the times of nodes that are not removed by connecting the parent and children of removed nodes by branchs with lengths equal to the total time elapsed from parent to each child.

Parameters

tree

A networkx DiGraph object representing the tree

infer_ancestral_characters : boolbool

Infer the ancestral characters states of the tree

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

get_dissimilarity_map()

Gets the dissimilarity map.

Return type

DataFrameDataFrame

set_dissimilarity_map(dissimilarity_map)

Sets the dissimilarity map variable in this object.

Parameters

dissimilarity_map : DataFrameDataFrame

Dissimilarity map relating all N x N distances between leaves.

Return type

NoneNone

get_dissimilarity(node)

Get the dissimilarity of a single leaf to all other leaves.

Parameters

node : strstr

Name of the leaf node to get the dissimilarity to/from

Raises

CassiopeiaTreeError if the dissimilarity map is not defined or the – provided node is not in the dissimilarity map

Return type

{str: float}Dict[str, float]

set_dissimilarity(node, dissimilarity)

Set the dissimilarity of a single leaf.

This function may be used only when a dissimilarity map already exists.

Parameters

node : strstr

Name of the leaf node to set the dissimilarity to/from

dissimilarity : {str: float}Dict[str, float]

Dictionary containing other leaf names as keys and dissimilarities as values

Raises

CassiopeiaTreeError if the dissimilarity map does not exist, if – the dissimilarity dictionary does not contain all other leaves,

Return type

NoneNone

compute_dissimilarity_map(dissimilarity_function=None, prior_transformation='negative_log', layer=None)

Computes a dissimilarity map.

Given the dissimilarity function passed in, the pairwise dissimilarities will be computed over the samples in the character matrix. Populates the dissimilarity_map attribute in the object.

If any of the leaves have ambiguous character states (detected by checking if any of the states are lists), then cassiopeia.solver.dissimilarity_functions.cluster_dissimilarity() is called instead, with the provided dissimilarity_function as the first argument.

Parameters

dissimilarity_function : Callable[[array, array, int, Dict[int, Dict[int, float]]], float], NoneOptional[Callable[[array, array, int, Dict[int, Dict[int, float]]], float]] (default: None)

A function that will take in two character vectors and priors and produce a dissimilarity.

prior_transformation : strstr (default: 'negative_log')

A function defining a transformation on the priors in forming weights. Supports the following transformations:

”negative_log”: Transforms each probability by the negative

log

”inverse”: Transforms each probability p by taking 1/p “square_root_inverse”: Transforms each probability by the

the square root of 1/p

layer : str, NoneOptional[str] (default: None)

Character matrix layer to use. If not specified, use the default character_matrix.

Return type

NoneNone

set_attribute(node, attribute_name, value)

Sets an attribute in the tree.

Parameters

node : strstr

Node name

attribute_name : strstr

Name for the new attribute

value : AnyAny

Value for the attribute.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

Return type

NoneNone

get_attribute(node, attribute_name)

Retrieves the value of an attribute for a node.

Parameters

node : strstr

Node name

attribute_name : strstr

Name of the attribute.

Return type

AnyAny

Returns

The value of the attribute for that node.

Raises

CassiopeiaTreeError if the attribute has not been set for this node. –

filter_nodes(condition)

Return type

List[str]List[str]

find_lcas_of_pairs(pairs=None)

Finds LCAs of all (provided) pairs.

Parameters

pairs : Iterator[Tuple[str, str]], List[Tuple[str, str]], NoneUnion[Iterator[Tuple[str, str]], List[Tuple[str, str]], None] (default: None)

Pairs of nodes for which to find LCAs. If not provided, LCAs of all pairs are computed. Defaults to None.

Return type

Iterator[Tuple[Tuple[str, str], str]]Iterator[Tuple[Tuple[str, str], str]]

Returns

A generator of ((u, v), LCA) tuples.

Raises

CassiopeiaTreeError if the tree has not been initialized. –

find_lca(*nodes)

Finds the LCA of all provided nodes.

Internally, this function calls get_all_ancestors() for each provided node and finds the deepest node that is shared.

Parameters

*nodes

Nodes for which to find the LCA. At least two must be provided.

Return type

strstr

Returns

The LCA node

Raises

• CassiopeiaTreeError if less than two nodes were provided or if the –

• tree has not been initialized. –

get_distance(node1, node2)

Compute the branch distance between two nodes.

Internally, this function converts the tree to an undirected graph and finds the shortest path by calling nx.shortest_path_length().

Parameters

node1 : strstr

First node

node2 : strstr

Second node

Return type

floatfloat

Returns

The branch distance between the two nodes

Raises

CassiopeiaTreeError if the tree has not been initialized. –

get_distances(node, leaves_only=False)

Compute the distances between the given node and every other node.

Internally, this function converts the tree to an undirected graph and finds the shortest path by calling nx.shortest_path_length().

Parameters

node : strstr

Node from which to compute distance to all other nodes

leaves_only : boolbool (default: False)

Calculate distances to leaves only and not internal nodes. Defaults to False.

Return type

{str: float}Dict[str, float]

Returns

Dictionary of distances

Raises

CassiopeiaTreeError if the tree has not been initialized. –