lineagetree.tree_approximation

Classes:

Name	Description
TreeApproximationTemplate	Template class to produce different tree styles to comapare LineageTrees.
downsample_tree	Downsamples a tree so every n nodes are being used as one.
full_tree	No approximations the whole tree is used here. Perfect accuracy, but heavy on ram and speed.
mini_tree	Each branch is converted to a node of length 1, it is useful for comparing synchronous developing cells, extremely fast.
simple_tree	Each branch is converted to one node with length the same as the life cycle of the cell.

TreeApproximationTemplate

TreeApproximationTemplate(
    lT: LineageTree,
    root: int,
    downsample: int | None = None,
    end_time: int | None = None,
    time_scale: int = 1,
)

Bases: ABC

Template class to produce different tree styles to comapare LineageTrees. To add a new style you need to inherit this class or one of its children and add them to the tree_style enum, or use it immediately on the function called. The main products of this class are: - tree constructor (get_tree) that produces one dictionary that contains arbitary unique labels and one dictionary that contains the duration of each node. - delta function: A function that handles the cost of comparing nodes to each other. - normalization function, a function that returns the length of the tree or any interger.

Methods:

Name	Description
delta	The distance of two nodes inside a tree. Behaves like a staticmethod.
get_norm	Returns the valid value for normalizing the edit distance.
get_tree	Get a tree version of the tree spawned by the node r
handle_resolutions	Handle different time resolutions.

Source code in src/lineagetree/tree_approximation.py

def __init__(
    self,
    lT: LineageTree,
    root: int,
    downsample: int | None = None,
    end_time: int | None = None,
    time_scale: int = 1,
):
    self.lT: LineageTree = lT
    self.internal_ids = max(self.lT.nodes)
    self.root: int = root
    self.downsample: int = downsample
    self.end_time: int = end_time if end_time else self.lT.t_e
    self.time_scale: int = int(time_scale) if time_scale else 1
    if time_scale <= 0:
        raise Exception("Please use a valid time_scale (Larger than 0)")
    self.tree: tuple = self.get_tree()
    self.edist = self._edist_format(self.tree[0])

delta abstractmethod

delta(
    x: int,
    y: int,
    corres1: dict[int, int],
    corres2: dict[int, int],
    times1: dict[int, float],
    times2: dict[int, float],
) -> int | float

The distance of two nodes inside a tree. Behaves like a staticmethod. The corres1/2 and time1/2 should always be provided and will be handled accordingly by the specific delta of each tree style.

Parameters:

Name	Type	Description	Default
x	int	The first node to compare, takes the names provided by the edist.	required
y	int	The second node to compare, takes the names provided by the edist	required
corres1	dict	Dictionary mapping node1 ids to the corresponding id in the original tree.	required
corres2	dict	Dictionary mapping node2 ids to the corresponding id in the original tree.	required
times1	dict	The dictionary of the chain lengths of the tree that n1 is spawned from.	required
times2	dict	The dictionary of the chain lengths of the tree that n2 is spawned from.	required

Returns:

Type	Description
int or float	The distance between 'x' and 'y'.

Source code in src/lineagetree/tree_approximation.py

@abstractmethod
def delta(
    self,
    x: int,
    y: int,
    corres1: dict[int, int],
    corres2: dict[int, int],
    times1: dict[int, float],
    times2: dict[int, float],
) -> int | float:
    """The distance of two nodes inside a tree. Behaves like a staticmethod.
        The corres1/2 and time1/2 should always be provided and will be handled accordingly by the specific
        delta of each tree style.

    Parameters
    ----------
    x : int
        The first node to compare, takes the names provided by the edist.
    y : int
        The second node to compare, takes the names provided by the edist
    corres1 : dict
        Dictionary mapping node1 ids to the corresponding id in the original tree.
    corres2 : dict
        Dictionary mapping node2 ids to the corresponding id in the original tree.
    times1 : dict
        The dictionary of the chain lengths of the tree that n1 is spawned from.
    times2 : dict
        The dictionary of the chain lengths of the tree that n2 is spawned from.

    Returns
    -------
    int or float
        The distance between 'x' and 'y'.
    """
    if x is None and y is None:
        return 0
    if x is None:
        return times2[corres2[y]]
    if y is None:
        return times1[corres1[x]]
    len_x = times1[corres1[x]]
    len_y = times2[corres2[y]]
    return np.abs(len_x - len_y)

get_norm abstractmethod

get_norm(root: int) -> int | float

Returns the valid value for normalizing the edit distance.

Parameters:

Name	Type	Description	Default
root	int	The starting node of the subtree.	required

Returns:

Type	Description
int or float	The number of nodes of each tree according to each style, or the sum of the length of all the nodes in a tree.

Source code in src/lineagetree/tree_approximation.py

@abstractmethod
def get_norm(self, root: int) -> int | float:
    """
    Returns the valid value for normalizing the edit distance.

    Parameters
    ----------
    root : int
        The starting node of the subtree.

    Returns
    -------
    int or float
        The number of nodes of each tree according to each style, or the sum of the length of all the nodes in a tree.
    """

get_tree abstractmethod

get_tree() -> tuple[dict, dict]

Get a tree version of the tree spawned by the node r

Returns:

Type	Description
dict mapping an int to a list of int	an adjacency dictionnary where the ids are the ids of the cells in the original tree at their first time point (except for the cell r if it was not the first time point).
dict mapping an int to a float	life time duration of the key cell m

Source code in src/lineagetree/tree_approximation.py

@abstractmethod
def get_tree(self) -> tuple[dict, dict]:
    """
    Get a tree version of the tree spawned by the node `r`

    Returns
    -------
    dict mapping an int to a list of int
        an adjacency dictionnary where the ids are the ids of the
        cells in the original tree at their first time point
        (except for the cell `r` if it was not the first time point).
    dict mapping an int to a float
        life time duration of the key cell `m`
    """

handle_resolutions abstractmethod staticmethod

handle_resolutions(
    time_resolution1: float | int,
    time_resolution2: float | int,
    gcd: int,
    downsample: int,
) -> tuple[int | float, int | float]

Handle different time resolutions.

Parameters:

Name	Type	Description	Default
time_resolution1	int or float	Time resolution of the first dataset. (Extracted from lT._time_resolution)	required
time_resolution2	int or float	Time resolution of the second dataset. (Extracted from lT._time_resolution)	required

Returns:

Type	Description
int or float	The time resolution fix for the first dataset
int or float	The time resolution fix for the second dataset

Source code in src/lineagetree/tree_approximation.py

@staticmethod
@abstractmethod
def handle_resolutions(
    time_resolution1: float | int,
    time_resolution2: float | int,
    gcd: int,
    downsample: int,
) -> tuple[int | float, int | float]:
    """Handle different time resolutions.

    Parameters
    ----------
    time_resolution1 : int or float
        Time resolution of the first dataset. (Extracted from lT._time_resolution)
    time_resolution2 : int or float
        Time resolution of the second dataset. (Extracted from lT._time_resolution)

    Returns
    -------
    int or float
        The time resolution fix for the first dataset
    int or float
        The time resolution fix for the second dataset
    """

downsample_tree

downsample_tree(**kwargs)

Bases: TreeApproximationTemplate

Downsamples a tree so every n nodes are being used as one.

Source code in src/lineagetree/tree_approximation.py

def __init__(self, **kwargs):
    super().__init__(**kwargs)
    if self.downsample == 0:
        raise Exception("Please use a valid downsampling rate")
    if self.downsample == 1:
        warnings.warn(
            "Downsampling rate of 1 is identical to the full tree.",
            stacklevel=1,
        )

full_tree

full_tree(
    lT: LineageTree,
    root: int,
    downsample: int | None = None,
    end_time: int | None = None,
    time_scale: int = 1,
)

Bases: TreeApproximationTemplate

No approximations the whole tree is used here. Perfect accuracy, but heavy on ram and speed. Not recommended to use on napari.

Source code in src/lineagetree/tree_approximation.py

def __init__(
    self,
    lT: LineageTree,
    root: int,
    downsample: int | None = None,
    end_time: int | None = None,
    time_scale: int = 1,
):
    self.lT: LineageTree = lT
    self.internal_ids = max(self.lT.nodes)
    self.root: int = root
    self.downsample: int = downsample
    self.end_time: int = end_time if end_time else self.lT.t_e
    self.time_scale: int = int(time_scale) if time_scale else 1
    if time_scale <= 0:
        raise Exception("Please use a valid time_scale (Larger than 0)")
    self.tree: tuple = self.get_tree()
    self.edist = self._edist_format(self.tree[0])

_edist_format

_edist_format(
    adj_dict: dict,
) -> tuple[list, list[list], dict[int, int]]

Formating the custom tree style to the format needed by edist. .. warning:: Modifying this function might break your code.

Returns:

Type	Description
list[int]	The list of the new nodes to be used for edist list[list] The adjacency list of these nodes dict[int,int] The correspondance between the nodes used in edist and LineageTree

Source code in src/lineagetree/tree_approximation.py

def _edist_format(
    self, adj_dict: dict
) -> tuple[list, list[list], dict[int, int]]:
    """Formating the custom tree style to the format needed by edist.
    .. warning:: Modifying this function might break your code.

    Parameters
    ----------
        adj_dict : dict
            The adjacency dictionary produced by 'get_tree'

    Returns
    -------
        list[int]
            The list of the new nodes to be used for edist
        list[list]
            The adjacency list of these nodes
        dict[int,int]
            The correspondance between the nodes used in edist and LineageTree
    """
    inv_adj = {vi: k for k, v in adj_dict.items() for vi in v}
    roots = set(adj_dict).difference(inv_adj)
    nid2list = {}
    list2nid = {}
    nodes = []
    adj_list = []
    curr_id = 0
    to_update = {}
    for r in roots:
        to_do = [r]
        while to_do:
            curr = to_do.pop(0)
            nid2list[curr] = curr_id
            list2nid[curr_id] = curr
            if curr in self.corres_added_nodes:
                to_update[curr_id] = self.corres_added_nodes[curr]
            nodes.append(curr_id)
            to_do = adj_dict.get(curr, []) + to_do
            curr_id += 1
        adj_list = [
            [nid2list[d] for d in adj_dict.get(list2nid[_id], [])]
            for _id in nodes
        ]
        list2nid.update(to_update)
    return nodes, adj_list, list2nid

mini_tree

mini_tree(**kwargs)

Bases: TreeApproximationTemplate

Each branch is converted to a node of length 1, it is useful for comparing synchronous developing cells, extremely fast. Mainly used for testing.

Source code in src/lineagetree/tree_approximation.py

def __init__(self, **kwargs):
    super().__init__(**kwargs)

simple_tree

simple_tree(**kwargs)

Bases: TreeApproximationTemplate

Each branch is converted to one node with length the same as the life cycle of the cell. This method is fast, but imprecise, especialy for small trees (recommended height of the trees should be 100 at least). Use with CAUTION.

Source code in src/lineagetree/tree_approximation.py

def __init__(self, **kwargs):
    super().__init__(**kwargs)