# Mastodon Deep Lineage - a collection of plugins to analyse lineages of tracked objects in Mastodon
## Installation instructions
* Add the listed Mastodon update site in Fiji:
* Help > Update > Manage update sites
* Name: Mastodon
* ![Mastodon Update site](doc/deep_lineage/installation/Mastodon.png)
* Add the unlisted Mastodon Deep Lineage update site in Fiji:
* Help > Update > Manage update sites > Add Unlisted Site
* Name: Mastodon-DeepLineage
* URL: https://sites.imagej.net/Mastodon-DeepLineage/
* ![Mastodon Deep Lineage update site](doc/deep_lineage/installation/Mastodon-DeepLineage.png)
## Numerical Features added to Mastodon
### Spot Features
| **Feature name** | **Projections** | **Description** | **Formula/Visualisation** |
|------------------------------|---------------------------------------------------|-------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------|
| Spot Ellipsoid | Short semi axes, Middle semi axis, Long semi axis | The ellipsoid semi axes in ascending order of length. | The semi axes are computed applying the square root to the eigenvalues of the so-called covariance matrix of the spots |
| | Volume | The volume of the ellipsoid. | $V=\frac{4}{3} \pi a b c$ |
| Spot Ellipsoid Aspect Ratios | Aspect ratio short to middle | The ratio between the short axis and middle axis. | $\frac{\text{short axis}}{\text{middle axis}}$ |
| | Aspect ratio short to long | The ratio between the short axis and long axis. | $\frac{\text{short axis}}{\text{long axis}}$ |
| | Aspect ratio middle to long | The ratio between the middle axis and long axis. | $\frac{\text{middle axis}}{\text{long axis}}$ |
| Spot Branch ID | _idem_ | The ID of the branch spot each spot belongs to. | |
### Branch-spot features
| **Feature name** | **Projections** | **Description** | **Formula/Visualisation** |
|--------------------|-----------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------|
| Branch N Leaves | _idem_ | The total number of leaves of a branch spot in the whole track subtree of this branch spot. | ![](deep_lineage/features/branchNLeaves.png) |
| Branch N Successor | _idem_ | Total number of successors of a branch spot in the whole track subtree of this branch spot. | ![](deep_lineage/features/branchNSuccessors.png) |
| Branch Sinuosity | _idem_ | Computes the sinuosity of a spot during its life cycle (cf. [Sinuosity](https://en.wikipedia.org/wiki/Sinuosity)), i.e. how much the track represented by the branch is curved. Values close to 1: almost straight movement. Values significantly higher than 1: winding or meandering movement. | ![](deep_lineage/features/sinuosityEquation.gif)
i.e.:
![](deep_lineage/features/sinuosityEquation2.gif) |
## Lineage Tree Classification
* This plugin is capable of grouping similar lineage trees together.
* The similarity of a pair of lineage trees is computed based on the Zhang edit distance for unordered
trees ([Zhang, K. Algorithmica 15, 205–222, 1996](https://doi.org/10.1007/BF01975866)). This method captures the cost
of the transformation of one tree into the other.
* The cost function applied for the tree edit distance uses the attribute branch spot duration, which is computed as a
difference of time points between to subsequent divisions reflecting the start and the end of a spot's lifetime.
* Thus, the linage classification operates on Mastodon's branch graph.
* The Zhang unordered edit distance allows the following edit operations:
```
Note: The prefix T may represent a node or a complete subtree. Nodes without this prefix are just nodes.
1. Change label
A A'
/ \ -> / \
TB TC TB TC
2a: Remove subtree (opposite of 2b)
A A
/ \ -> |
TB TC TB
2b: Add new subtree (opposite of 2a)
A A
| -> / \
TB TB TC
3a: Remove subtree but keep one child (opposite of 3b)
A A
/ \ -> / \
B TC TD TC
/ \
TD TE (remove B and TE, keep TD)
3b: Convert existing subtree into child of a newly inserted subtree (opposite of 3a)
A A
/ \ -> / \
TB TC D TC
/ \
TB TE (insert D and TE, keep TB)
4a: Remove subtree (and siblings) but keep all children (opposite of 4b)
A A
/ \ / \
B TC -> TD TE
/ \
TD TE (Subtree B and it's sibling TC are removed, but the children
of B namely TD and TE are kept)
4b: Convert existing subtrees into children of a newly inserted subtree (opposite of 4a)
A A
/ \ / \
TB TC -> D TE
/ \
TB TC (Subtree D and it's sibling TE are newly inserted,
TB and TC are kept as children of D)
```
* A basic example of the tree edit
distance:
```
Tree1
node1(node_weight=13)
┌──────────┴─────────────┐
│ │
node2(node_weight=203) node3(node_weight=203)
```
```
Tree2
node1(node_weight=12)
┌──────────┴─────────────┐
│ │
node2(node_weight=227) node3(node_weight=227)
┌──────────┴─────────────┐
node4(node_weight=10) node5(node_weight=10)
```
* Edit distance of 69, because:
* one node has a difference of 1
* two nodes have a difference of 24 each
* two extra nodes are added with a weight of 10 each
* $\text{Zhang Tree Edit Distance}_{Tree1,Tree2} = 1 + 2 \times 24 + 2 \times 10 = 69$
* The tree edit distances are computed between all possible combinations of lineage trees leading to a two-dimensional
matrix. The values in this matrix are considered to reflect similarities of lineage trees. Low tree edit distances
represent a high similarity between a discrete pair of lineage trees.
* This similarity matrix is then used to perform
an [agglomerative hierarchical clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering) into a specifiable
number of classes.
### Parameters:
* Crop criterion:
* Time point (default)
* Number of spots
* Crop start
* Crop end
* Number of classes (minimum 2)
* Minimum number of divisions
* Similarity measure:
* Normalized Zhang Tree Edit Distance (default). $\frac{distance_{treeA,treeB}}{distance_{treeA,emptyTree} +
distance_
{treeB,emptyTree}}$
* Per Branch Spot Zhang Tree Edit Distance. $\frac{distance_{treeA,treeB}}{numBranchSpotsA + numBranchSpotsB}$
* Zhang Tree Edit Distance as described in ([Zhang](https://doi.org/10.1007/BF01975866)).
* Linkage strategy for hierarchical clustering,
cf. [linkage methods](https://en.wikipedia.org/wiki/Hierarchical_clustering#Cluster_Linkage)
* Average (default)
* Single
* Complete
* Feature:
* Branch duration (default and currently only selectable feature)
* Show dendrogram of clustering
### Example:
* Demo data: [Example data set](deep_lineage/lineage_classification/lineage_classification.mastodon)
* The demo data does not contain any image data.
* The spatial positions of the spots are randomly generated.
* When opening the dataset, you should confirm that you open the project with dummy
images. ![Dummy images](deep_lineage/lineage_classification/dummy.png)
* The track scheme of the demo data containing 8 lineage tree in total. You may see that the "symmetric", the "
asymmetric" and the "single division" trees look
similar to each other, but dissimilar to the other
trees. ![Trackscheme](deep_lineage/lineage_classification/trackscheme.png)
* The lineage classification dialog. ![Settings](deep_lineage/lineage_classification/settings.png)
* The resulting dendrogram. ![Dendrogram](deep_lineage/lineage_classification/dendrogram.png)
* The resulting tag set used for coloring the track
scheme. ![Trackscheme with tags](deep_lineage/lineage_classification/trackscheme_with_tags.png)
* The resulting tag set used for coloring the track scheme branch
view. ![Trackscheme Branch View with tags](deep_lineage/lineage_classification/trackscheme_branch_with_tags.png)
## Label image exporter
* The Label image exporter is capable of saving a label image to a file using the existing ellipsoids in Mastodon.
* For the labels, the _spot ids_, _branch spot ids_ or the _track ids_ that correspond to the spots / ellipsoids may be
used. Since these Ids are counted zero based in Mastodon, an **offset of 1** is added to all Ids so that no label
clashes with the background of zero.
* The recommended export format is '*.tif'-files. However, it should work also for other formats supported by ImageJ.
* The export uses an image with signed integer value space, thus the maximum allowed id is 2.147.483.646.
* Exporter can be found here: ![Plugin Export Menu](deep_lineage/export_label_image/plugin_export_menu.png)
* The dialog: ![Plugin Export Dialog](deep_lineage/export_label_image/plugin_export_dialog.png)
* Label Id: The id that is used for the labels. The default is the Spot track Id.
* The ids correspond to the highlighted columns in the feature
table: ![Feature Table](deep_lineage/export_label_image/plugin_export_table.png)
* Frame rate reduction: Only export every n-th frame. 1 means no reduction. Value must be >= 1.
* The frame number corresponds to the _Spot frame_ column in the feature table.
* Save to: Path to the file to save the label image to.
### Example:
* Demo data: [Example data set](https://github.com/mastodon-sc/mastodon-example-data/tree/master/tgmm-mini)
* The timelapse with the ellipsoids in
BigDataViewer: ![BigDataViewer](deep_lineage/export_label_image/bdv_timelapse.gif)
* The exported tif imported into [Napari](https://napari.org/stable/) 3D
view: ![Napari](deep_lineage/export_label_image/napari_timelapse.gif)