Implementation of Zhang Tree Edit Distance for unordered trees

[stefanhahmann]

Story

Users would like to be able to determine the similarity of a sub-tree of a lineage tree with other sub-trees of the same or a different lineage tree. For this purpose, it is needed to have an algorithm implemented that computes the similarity between parts of lineage trees based on the tree similarity algorithm between unordered labeled trees.

Acceptance criteria

1. An function exists that creates a view on a ModelBranchGraph based on a (root-)branchSpot and an endtimepoint
   • This view should itself be a ReadOnlyGraph<BranchSpot, BranchLink>
2. A function that can take the follwing inputs:
   • ReadOnlyGraph<BranchSpot, BranchLink>
   • ReadOnlyGraph<BranchSpot, BranchLink>
   • Cost function
3. The function returns the resulting tree similarity value
4. The tree similarity function can take a cost function
5. The cost function can take a List of attributes into account
6. The cost function for the lifespan exists as an example cost function

Tasks

• [x] Unit tests with basic examples
• [x] Evaluate copy to JGraphT and potentially adapt acceptance criteria to a JGraphT implementation
• [x] Function to create a ReadOnlyGraph from a ModelBranchGraph and a BranchSpot and endtimepoint
• [x] Implementation of Zhang (1996) edit distance
• [x] Example cost function for lifespan

Algorithm:

• Algorithm: Zhang (1996): A constrained edit distance between unordered labeled trees https://link.springer.com/article/10.1007/BF01975866
• Python implementation: https://gitlab.inria.fr/mosaic/treex/-/blob/master/src/treex/analysis/edit_distance/zhang_labeled_trees.py

Context

The similarity measurement shall be used to perform hierarchical clustering for all sub-trees of the root-nodes in a lineage tree. User may enter the starting timepoint and the ending timepoint and the number of classes that should be produced. The result should be available as tag set.

Findings from Tests

• Tests performed with networkx and treex library in Python
  • networkx
  • https://networkx.org/documentation/stable/reference/algorithms/similarity.html
  • too slow (-)
  • Python (-)
  • treex (recommended by Christophe Godin)
  • https://joss.theoj.org/papers/10.21105/joss.01351.pdf
  • implements zhang (1996) edit distance for unordered trees
  • reasonable performance (+)
  • fulfills requirements regarding tree similarity measurement (+)
  • may not be used for lineage tree registration without root nodes (-)
  • python bridge required (-)
  • JGraphT
  • https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/similarity/ZhangShashaTreeEditDistance.html
  • implements zhang & shasha (1989) edit distance for ordered trees
  • reasonable performance (+)
  • does not fully fulfill requirements regarding tree similarity, i.e. order of nodes influences the similarity measurement (-)
  • may be used for lineage tree registration without labeled root nodes (+)
  • Java - integration into Mastodon relatively easy (+)
  • Tree Edit distance
  • http://tree-edit-distance.dbresearch.uni-salzburg.at
  • does not fully fulfill requirements regarding tree similarity, i.e. order of nodes influences the similarity measurement (-)

Additional Information

• Tracking Accurary Measurement (TRA)

  • https://github.com/CellTrackingChallenge/measures/
  • http://celltrackingchallenge.net/evaluation-methodology/
  • https://github.com/CellTrackingChallenge/measures/blob/master/src/main/java/net/celltrackingchallenge/measures/TRA.java
  • https://github.com/mastodon-sc/mastodon-ctc/blob/master/src/main/java/org/mastodon/ctc/TRAreviewPlugin.java

• Vladimir Ulman:

[maarzt]

Here is an attempt to visualize the edit operations that are allowed by the Zhang unordered tree edit distance. As ascii art.

1. Change label

      A         A'
     / \  ->   / \
    TB TC     TB TC                            

2a: Remove subtree

      A         A                                               
     / \   ->   |                                                    
    TB TC       TB

2b: Add new subtree

      A          A
      |    ->   / \
      TB       TB TC

3a: Remove subtree but keep one child

      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
      A             A
     / \    ->     / \
    TB TC         D  TC
                 / \
        TB TE       (insert D and TE, keep TD)

4a: Remove subtree (and siblings) but keep all children
      A               A
     / \             / \
    B  TC   ->      TD TE
   / \
  TD TE            (Subtree B and it's sibling TE are removed, but the children
                    of B namely TD and TE are kept)

4b: Opposite of 4a

Maybe this could become part of the javadoc?