Repository: cogent3/cogent3
Pull request #1664 (2023-12-11 00:06:23)

DEV: add support for more tree distance metrics
Addresses #1644 and #1590.

Also fixes issues in the cookbook documentation for `simple_trees.rst` where examples that used `make_tree` imported `load_tree` instead.


Patch:
diff --git a/doc/cookbook/simple_trees.rst b/doc/cookbook/simple_trees.rst
index 1a08d670e..97b13644f 100644
--- a/doc/cookbook/simple_trees.rst
+++ b/doc/cookbook/simple_trees.rst
@@ -400,7 +400,7 @@ Add internal nodes so that every node has 2 or fewer children.
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tree_string = "(B:0.2,H:0.2,(C:0.3,D:0.4,E:0.1)F:0.5)G;"
     tr = make_tree(tree_string)
@@ -437,12 +437,61 @@ Branch lengths don't matter.
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tr1 = make_tree("(B:0.2,(C:0.2,D:0.2)F:0.2)G;")
     tr2 = make_tree("((C:0.1,D:0.1)F:0.1,B:0.1)G;")
     tr1.same_topology(tr2)
 
+Measure topological distances between two trees
+"""""""""""""""""""""""""""""""""""""""""""""""
+
+A number of topological tree distance metrics are available. They include:
+
+* The Robinson-Foulds Distance for rooted trees.
+* The Matching Cluster Distance for rooted trees.
+* The Robinson-Foulds Distance for unrooted trees.
+* The Lin-Rajan-Moret Distance for unrooted trees.
+
+There are several variations of the Robinson-Foulds metric in the literature. The definition used by ``cogent3`` is the
+cardinality of the symmetric difference of the sets of clades/splits in the two rooted/unrooted trees. Other definitions sometimes
+divide this by two, or normalise it to the unit interval. 
+
+The Robinson-Foulds distance is quick to compute, but is known to saturate quickly. Moving a single leaf in a tree can maximise this metric.
+
+The Matching Cluster and Lin-Rajan-Moret are two matching-based distances that are more statistically robust. 
+Unlike the Robinson-Foulds distance which counts how many of the splits/clades are not exactly same, the matching-based distances
+measures the degree by which the splits/clades are different. The matching-based distances solve a min-weight matching problem,
+which for large trees may take longer to compute.
+
+.. jupyter-execute::
+
+    # Distance metrics for rooted trees
+    from cogent3 import make_tree
+
+    tr1 = make_tree(treestring="(a,(b,(c,(d,e))));")
+    tr2 = make_tree(treestring="(e,(d,(c,(b,a))));")
+    
+    mc_distance = tr1.tree_distance(tr2, method="matching_cluster") # or method="mc" or method="matching"
+    rooted_rf_distance = tr1.tree_distance(tr2, method="rooted_robinson_foulds") # or method="rrf" or method="rf"
+
+    print("Matching Cluster Distance:", mc_distance)
+    print("Rooted Robinson Foulds Distance:", rooted_rf_distance)
+
+.. jupyter-execute::
+
+    # Distance metrics for unrooted trees
+    from cogent3 import make_tree
+    
+    tr1 = make_tree(treestring="(a,b,(c,(d,e)));")
+    tr2 = make_tree(treestring="((a,c),(b,d),e);")
+    
+    lrm_distance = tr1.tree_distance(tr2, method="lin_rajan_moret") # or method="lrm" or method="matching"
+    unrooted_rf_distance = tr1.tree_distance(tr2, method="unrooted_robinson_foulds") # or method="urf" or method="rf"
+    
+    print("Lin-Rajan-Moret Distance:", lrm_distance)
+    print("Unrooted Robinson Foulds Distance:", unrooted_rf_distance)
+
 Calculate each node's maximum distance to a tip
 """""""""""""""""""""""""""""""""""""""""""""""
 
@@ -451,7 +500,7 @@ the distance from that node to its most distant tip.
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tr = make_tree("(B:0.2,(C:0.3,D:0.4)F:0.5)G;")
     print(tr.ascii_art())
@@ -467,7 +516,7 @@ Scale branch lengths in place to integers for ascii output
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tr = make_tree("(B:0.2,(C:0.3,D:0.4)F:0.5)G;")
     print(tr)
@@ -484,7 +533,7 @@ and a list of the tip nodes.
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tr = make_tree("(B:3,(C:2,D:4)F:5)G;")
     d, tips = tr.tip_to_tip_distances()
@@ -504,7 +553,7 @@ Note: automatically strips out the names that don't match.
 
 .. jupyter-execute::
 
-    from cogent3 import load_tree
+    from cogent3 import make_tree
 
     tr1 = make_tree("(B:2,(C:3,D:4)F:5)G;")
     tr2 = make_tree("(C:2,(B:3,D:4)F:5)G;")
diff --git a/src/cogent3/core/tree.py b/src/cogent3/core/tree.py
index 84efc41ab..2a76d50e5 100644
--- a/src/cogent3/core/tree.py
+++ b/src/cogent3/core/tree.py
@@ -40,6 +40,7 @@ from numpy import argsort, ceil, log, zeros
 
 from cogent3._version import __version__
 from cogent3.maths.stats.test import correlation
+from cogent3.phylo.tree_distance import get_tree_distance_measure
 from cogent3.util.io import atomic_write, get_format_suffixes
 from cogent3.util.misc import get_object_provenance
 
@@ -1598,7 +1599,70 @@ class TreeNode(object):
         tip = self.get_node_matching_name(outgroup_name)
         return tip.parent.unrooted_deepcopy()
 
-    def lin_rajan_moret(self, tree2) -> float:
+    def tree_distance(self, other: TreeNode, method: str | None = None) -> int:
+        """Return the specified tree distance between this and another tree.
+
+        Defaults to the Lin-Rajan-Moret distance on unrooted trees.
+        Defaults to the Matching Cluster distance on rooted trees.
+
+        Parameters
+        ----------
+        other: TreeNode
+            The other tree to calculate the distance between.
+        method: str | None
+            The tree distance metric to use.
+
+            Options are:
+            "rooted_robinson_foulds": The Robinson-Foulds distance for rooted trees.
+            "unrooted_robinson_foulds": The Robinson-Foulds distance for unrooted trees.
+            "matching_cluster": The Matching Cluster distance for rooted trees.
+            "lin_rajan_moret": The Lin-Rajan-Moret distance for unrooted trees.
+            "rrf": An alias for rooted_robinson_foulds.
+            "urf": An alias for unrooted_robinson_foulds.
+            "mc": An alias for matching_cluster.
+            "lrm": An alias for lin_rajan_moret.
+            "rf": The unrooted/rooted Robinson-Foulds distance for unrooted/rooted trees.
+            "matching": The Lin-Rajan-Moret/Matching Cluster distance for unrooted/rooted trees.
+
+            Default is "matching".
+
+        Returns
+        -------
+        int
+            the chosen distance between the two trees.
+
+        Notes
+        -----
+        The Lin-Rajan-Moret distance [2]_ and Matching Cluster distance [1]_
+        display superior statistical properties than the Robinson-Foulds
+        distance [3]_ on unrooted and rooted trees respectively.
+
+        References
+        ----------
+        .. [1] Bogdanowicz, D., & Giaro, K. (2013).
+           On a matching distance between rooted phylogenetic trees.
+           International Journal of Applied Mathematics and Computer Science, 23(3), 669-684.
+        .. [2] Lin et al. 2012
+           A Metric for Phylogenetic Trees Based on Matching
+           IEEE/ACM Transactions on Computational Biology and Bioinformatics
+           vol. 9, no. 4, pp. 1014-1022, July-Aug. 2012
+        .. [3] Robinson, David F., and Leslie R. Foulds.
+           Comparison of phylogenetic trees.
+           Mathematical biosciences 53.1-2 (1981): 131-147.
+        """
+
+        if method is None:
+            method = "matching"
+
+        is_rooted = len(self) == 2
+        if is_rooted and len(other) != 2 or not is_rooted and len(other) == 2:
+            raise ValueError(
+                "Both trees must be rooted or both trees must be unrooted."
+            )
+
+        return get_tree_distance_measure(method, is_rooted)(self, other)
+
+    def lin_rajan_moret(self, tree2) -> int:
         """return the lin-rajan-moret distance between trees
 
         float
diff --git a/src/cogent3/phylo/tree_distance.py b/src/cogent3/phylo/tree_distance.py
index 657b42012..f976e65d1 100644
--- a/src/cogent3/phylo/tree_distance.py
+++ b/src/cogent3/phylo/tree_distance.py
@@ -1,31 +1,104 @@
 from itertools import product
-from typing import List
+from typing import TYPE_CHECKING
 
-import numpy
+import numpy as np
 
 from scipy.optimize import linear_sum_assignment
 
+if TYPE_CHECKING:
+    from cogent3.core.tree import TreeNode
 
-def lin_rajan_moret(tree1: "PhyloNode", tree2: "PhyloNode") -> float:
-    """calculate the lin-rajan-moret distance (matching distance) between trees
 
-    trees should have matching tips and must not be rooted.
+def get_tree_distance_measure(method: str, is_rooted: bool):
+    if method in _TREE_DISTANCE_FUNCTIONS:
+        return _TREE_DISTANCE_FUNCTIONS[method]
+
+    if is_rooted and method in _ROOTED_TREE_DISTANCE_FUNCTIONS:
+        return _ROOTED_TREE_DISTANCE_FUNCTIONS[method]
+
+    if not is_rooted and method in _UNROOTED_TREE_DISTANCE_FUNCTIONS:
+        return _UNROOTED_TREE_DISTANCE_FUNCTIONS[method]
+
+    raise ValueError(
+        f"Tree distance method '{method}' is not supported for {'' if is_rooted else 'un'}rooted trees."
+    )
+
+
+def unrooted_robinson_foulds(tree1: "TreeNode", tree2: "TreeNode") -> int:
+    """Calculate the Robinson-Foulds distance between two unrooted trees.
+
+    Parameters
+    ----------
+    tree1, tree2: TreeNode
+        Trees to calculate the distance between.
+
+    Returns
+    -------
+    int
+        The unrooted Robinson-Foulds distance.
+
+    Notes
+    -----
+    For unrooted trees, the Robinson-Foulds distance [1]_ is defined
+    as the cardinality of the symmetric difference of the set of splits
+    for the two trees.
+
+    Trees should have matching tips and must not be rooted.
+
+    References
+    ----------
+    .. [1] Robinson, David F., and Leslie R. Foulds.
+       Comparison of phylogenetic trees.
+       Mathematical biosciences 53.1-2 (1981): 131-147.
+    """
+
+    names = tree1.get_tip_names()
+
+    if set(names) != set(tree2.get_tip_names()):
+        raise ValueError("tree tip names must match")
+    if len(tree1.children) == 2 or len(tree2.children) == 2:
+        raise ValueError("trees must be unrooted")
+
+    tree1_clusters = tree1.subsets()
+    tree2_clusters = tree2.subsets()
+
+    tree1_splits = _compute_splits(tree1_clusters, names)
+    tree2_splits = _compute_splits(tree2_clusters, names)
+
+    return len(tree1_splits.symmetric_difference(tree2_splits))
+
+
+def lin_rajan_moret(tree1: "TreeNode", tree2: "TreeNode") -> int:
+    """Calculate the Lin-Rajan-Moret distance (matching distance)
+    between two unrooted trees.
 
     Parameters
     ----------
-    tree1, tree2: PhyloNode
-        trees to calculate distance between
+    tree1, tree2: TreeNode
+        Trees to calculate the distance between.
 
     Returns
     -------
-    float
-        the Lin-Rajan-Moret distance
+    int
+        The Lin-Rajan-Moret distance.
 
     Notes
     -----
-    see: Lin et al. 2012 A Metric for Phylogenetic Trees Based on Matching
-    IEEE/ACM Transactions on Computational Biology and Bioinformatics
-    vol. 9, no. 4, pp. 1014-1022, July-Aug. 2012
+    The Lin-Rajan-Moret distance [1]_ displays superior statistical
+    properties than the Robinson-Foulds distance [2]_
+    on unrooted trees.
+
+    Trees should have matching tips and must not be rooted.
+
+    References
+    ----------
+    .. [1] Lin et al. 2012
+       A Metric for Phylogenetic Trees Based on Matching
+       IEEE/ACM Transactions on Computational Biology and Bioinformatics
+       vol. 9, no. 4, pp. 1014-1022, July-Aug. 2012
+    .. [2] Robinson, David F., and Leslie R. Foulds.
+       Comparison of phylogenetic trees.
+       Mathematical biosciences 53.1-2 (1981): 131-147.
     """
     names = tree1.get_tip_names()
 
@@ -41,16 +114,115 @@ def lin_rajan_moret(tree1: "PhyloNode", tree2: "PhyloNode") -> float:
 
     matching_distance = _matched_distance(vector1, vector2)
 
-    return float(matching_distance)
+    return matching_distance
+
+
+def rooted_robinson_foulds(tree1: "TreeNode", tree2: "TreeNode") -> int:
+    """Calculate the Robinson-Foulds distance between two rooted trees.
+
+    Parameters
+    ----------
+    tree1, tree2: TreeNode
+        Trees to calculate the distance between.
+
+    Returns
+    -------
+    int
+        The rooted Robinson-Foulds distance
+
+    Notes
+    -----
+    For rooted trees, the Robinson-Foulds distance [1]_ is defined as the
+    cardinality of the symmetric difference of the set of clades for
+    the two trees.
+
+    Trees should have matching tips and must be rooted.
+
+    References
+    ----------
+    .. [1] Robinson, David F., and Leslie R. Foulds.
+       Comparison of phylogenetic trees.
+       Mathematical biosciences 53.1-2 (1981): 131-147.
+    """
+    if set(tree1.get_tip_names()) != set(tree2.get_tip_names()):
+        raise ValueError("tree tip names must match")
+    if len(tree1.children) != 2 or len(tree2.children) != 2:
+        raise ValueError("trees must be rooted")
+
+    tree1_clusters = tree1.subsets()
+    tree2_clusters = tree2.subsets()
+
+    return len(tree1_clusters.symmetric_difference(tree2_clusters))
+
+
+def matching_cluster_distance(tree1: "TreeNode", tree2: "TreeNode") -> int:
+    """Calculate the Matching Cluster distance between two rooted trees.
+
+    Parameters
+    ----------
+    tree1, tree2: TreeNode
+        Trees to calculate the distance between.
+
+    Returns
+    -------
+    int
+        The Matching Cluster distance.
+
+    Notes
+    -----
+    The Matching Cluster distance [1]_ is a similar metric
+    to the beta-distance [2]_.
+
+    The Matching Cluster distance [1]_ displays superior statistical
+    properties than the Robinson-Foulds distance [3]_ on rooted trees.
 
+    Trees should have matching tips and must be rooted.
 
-def _convert_tree_to_vectors(tree: "PhyloNode", tip_names: List) -> numpy.ndarray:
+    References
+    ----------
+    .. [1] Bogdanowicz, D., & Giaro, K. (2013).
+       On a matching distance between rooted phylogenetic trees.
+       International Journal of Applied Mathematics and Computer Science, 23(3), 669-684.
+    .. [2] Boorman, S. A., & Olivier, D. C. (1973).
+       Metrics on spaces of finite trees.
+       Journal of Mathematical Psychology, 10(1), 26-59.
+    .. [3] Robinson, David F., and Leslie R. Foulds.
+       Comparison of phylogenetic trees.
+       Mathematical biosciences 53.1-2 (1981): 131-147.
+    """
+
+    if set(tree1.get_tip_names()) != set(tree2.get_tip_names()):
+        raise ValueError("tree tip names must match")
+    if len(tree1.children) != 2 or len(tree2.children) != 2:
+        raise ValueError("trees must be rooted")
+
+    tree1_clusters = list(tree1.subsets())
+    tree2_clusters = list(tree2.subsets())
+
+    while len(tree1_clusters) < len(tree2_clusters):
+        tree1_clusters.append(set())
+    while len(tree2_clusters) < len(tree1_clusters):
+        tree2_clusters.append(set())
+
+    adjacency = np.zeros(shape=(len(tree1_clusters), len(tree2_clusters)))
+
+    for i, cluster_1 in enumerate(tree1_clusters):
+        for j, cluster_2 in enumerate(tree2_clusters):
+            adjacency[i, j] = len(cluster_1.symmetric_difference(cluster_2))
+
+    row_ind, col_ind = linear_sum_assignment(adjacency)
+    distance = int(adjacency[row_ind, col_ind].sum())
+
+    return distance
+
+
+def _convert_tree_to_vectors(tree: "TreeNode", tip_names: list) -> np.ndarray:
     ref_tip = tip_names[0]
     name_set = set(tip_names)
     name_index = {n: i for i, n in enumerate(tip_names)}
     # we get the tree as a set of splits.
     splits = tree.subsets()
-    rows = numpy.zeros((len(splits), len(tip_names)), dtype=bool)
+    rows = np.zeros((len(splits), len(tip_names)), dtype=bool)
     for i, split in enumerate(splits):
         row = rows[i]
         # Cogent only returns one side of a
@@ -64,25 +236,60 @@ def _convert_tree_to_vectors(tree: "PhyloNode", tip_names: List) -> numpy.ndarra
     return rows
 
 
-def _hamming(vector1: numpy.ndarray, vector2: numpy.ndarray) -> int:
+def _hamming(vector1: np.ndarray, vector2: np.ndarray) -> int:
     return (vector1 != vector2).sum()
 
 
-def _weight(vector1: numpy.ndarray, vector2: numpy.ndarray) -> int:
+def _weight(vector1: np.ndarray, vector2: np.ndarray) -> int:
     return min(_hamming(vector1, vector2), _hamming(vector1, 1 - vector2))
 
 
-def _bipartite_graph(vector1: numpy.ndarray, vector2: numpy.ndarray) -> numpy.ndarray:
+def _bipartite_graph(vector1: np.ndarray, vector2: np.ndarray) -> np.ndarray:
     if not len(vector1) == len(vector2):
         raise ValueError("number of edges must be equal")
 
-    B = numpy.empty([len(vector1)] * 2, int)
+    B = np.empty([len(vector1)] * 2, int)
     for i, j in product(*[range(len(vector1))] * 2):
         B[i, j] = _weight(vector1[i], vector2[j])
     return B
 
 
-def _matched_distance(vector1: numpy.ndarray, vector2: numpy.ndarray) -> int:
+def _matched_distance(vector1: np.ndarray, vector2: np.ndarray) -> int:
     B = _bipartite_graph(vector1, vector2)
     matching = linear_sum_assignment(B)
     return B[matching].sum()
+
+
+def _compute_splits(clades: frozenset[frozenset], tip_names: list) -> set[frozenset]:
+    ref_tip = tip_names[0]
+    name_set = frozenset(tip_names)
+
+    splits = set()
+    for clade in clades:
+        if ref_tip in clade:
+            splits.add(clade)
+        else:
+            splits.add(name_set - clade)
+    return splits
+
+
+_TREE_DISTANCE_FUNCTIONS = {
+    "rooted_robinson_foulds": rooted_robinson_foulds,
+    "unrooted_robinson_foulds": unrooted_robinson_foulds,
+    "matching_cluster": matching_cluster_distance,
+    "lin_rajan_moret": lin_rajan_moret,
+    "rrf": rooted_robinson_foulds,
+    "urf": unrooted_robinson_foulds,
+    "mc": matching_cluster_distance,
+    "lrm": lin_rajan_moret,
+}
+
+_ROOTED_TREE_DISTANCE_FUNCTIONS = {
+    "rf": rooted_robinson_foulds,
+    "matching": matching_cluster_distance,
+}
+
+_UNROOTED_TREE_DISTANCE_FUNCTIONS = {
+    "rf": unrooted_robinson_foulds,
+    "matching": lin_rajan_moret,
+}


Test patch:
diff --git a/tests/test_core/test_tree.py b/tests/test_core/test_tree.py
index baa764b58..34b016dae 100644
--- a/tests/test_core/test_tree.py
+++ b/tests/test_core/test_tree.py
@@ -2196,6 +2196,100 @@ def test_get_distances_endpoints(num_tips):
     assert len(dists) == (num**2 - num)
 
 
+@pytest.mark.parametrize(
+    "method,expected",
+    (
+        ("lin_rajan_moret", 3),
+        ("lrm", 3),
+        ("matching", 3),
+        (None, 3),
+        ("unrooted_robinson_foulds", 4),
+        ("urf", 4),
+        ("rf", 4),
+    ),
+)
+def test_tree_distance_unrooted(method, expected):
+    tree1 = make_tree(treestring="(a,b,(c,(d,e)));")
+    tree2 = make_tree(treestring="((a,c),(b,d),e);")
+
+    assert tree1.tree_distance(tree2, method=method) == expected
+
+
+@pytest.mark.parametrize(
+    "method,expected",
+    (
+        ("matching_cluster", 10),
+        ("mc", 10),
+        ("matching", 10),
+        (None, 10),
+        ("rooted_robinson_foulds", 6),
+        ("rrf", 6),
+        ("rf", 6),
+    ),
+)
+def test_tree_distance_rooted(method, expected):
+    tree1 = make_tree(treestring="(a,(b,(c,(d,e))));")
+    tree2 = make_tree(treestring="(e,(d,(c,(b,a))));")
+
+    assert tree1.tree_distance(tree2, method=method) == expected
+
+
+@pytest.mark.parametrize(
+    "bad_method",
+    (
+        "matching_cluster ",
+        "m",
+        "mcc",
+        "rr",
+        "rff",
+        "ur",
+        "match",
+        " matching",
+        "robinson_foulds",
+        "None",
+    ),
+)
+def test_tree_distance_method_does_not_exist(bad_method):
+    unrooted1 = make_tree(treestring="(a,b,(c,(d,e)));")
+    unrooted2 = make_tree(treestring="((a,c),(b,d),e);")
+
+    with pytest.raises(ValueError):
+        unrooted1.tree_distance(unrooted2, method=bad_method)
+
+    rooted1 = make_tree(treestring="(a,(b,(c,(d,e))));")
+    rooted2 = make_tree(treestring="(e,(d,(c,(b,a))));")
+
+    with pytest.raises(ValueError):
+        rooted1.tree_distance(rooted2, method=bad_method)
+
+
+@pytest.mark.parametrize(
+    "method",
+    (
+        "matching_cluster",
+        "lin_rajan_moret",
+        "rooted_robinson_foulds",
+        "unrooted_robinson_foulds",
+        "mc",
+        "lrm",
+        "rrf",
+        "urf",
+        "matching",
+        "rf",
+        None,
+    ),
+)
+def test_tree_distance_incompatible_trees(method):
+    unrooted = make_tree(treestring="(a,b,(c,(d,e)));")
+    rooted = make_tree(treestring="(a,(b,(c,(d,e))));")
+
+    with pytest.raises(ValueError):
+        rooted.tree_distance(unrooted, method=method)
+
+    with pytest.raises(ValueError):
+        unrooted.tree_distance(rooted, method=method)
+
+
 def test_lrm_method():
     # this test just exercises the method, the tests on the underlying
     # function are in test_tree_distance.py
diff --git a/tests/test_tree_distance.py b/tests/test_tree_distance.py
index ec206b7cc..48a7caaa3 100644
--- a/tests/test_tree_distance.py
+++ b/tests/test_tree_distance.py
@@ -3,17 +3,101 @@ import pathlib
 import pytest
 
 from cogent3 import make_tree
-from cogent3.phylo.tree_distance import lin_rajan_moret
+from cogent3.phylo.tree_distance import (
+    lin_rajan_moret,
+    matching_cluster_distance,
+    rooted_robinson_foulds,
+    unrooted_robinson_foulds,
+)
+
+ROOTED_DISTANCE_MEASURES = matching_cluster_distance, rooted_robinson_foulds
+UNROOTED_DISTANCE_MEASURES = lin_rajan_moret, unrooted_robinson_foulds
+
+
+# unrooted rf distance
+def test_unrooted_rf_different_trees():
+    a = make_tree(treestring="(a, b, (c, (d, e)));")
+
+    # There are two splits not in common for the two trees
+    # abc-de in tree a, and ad-dce in tree b.
+    b = make_tree(treestring="(a, b, (d, (c, e)));")
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 2
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    # Identical unrooted tree as before, but a different orientation.
+    b = make_tree(treestring="((a, b), d, (c, e));")
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 2
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    # Identical unrooted tree as before, but a different orientation.
+    b = make_tree(treestring="(((a, b), d), c, e);")
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 2
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    a = make_tree(treestring="(a, (b, (c, d)), (e, (f, (g, h))));")
+    b = make_tree(treestring="(a, (c, (b, d)), (h, (f, (g, e))));")
 
+    # There are six splits not in common.
+    # For tree a they are cd-abefgh, abcdef-gh, and abcde-fgh
+    # For tree b they are bd-acefgh, abcdhf-ge, and abcdh-fge
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 6
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 6
 
-def test_different_trees():
+
+def test_unrooted_rf_same_tree():
+    # Topology of the unrooted trees are identical
+    # though they are stored in different orientations.
+    a = make_tree(treestring="(a, b, (c, d));")
+    b = make_tree(treestring="(c, d, (a, b));")
+
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 0
+
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 0
+
+
+def test_unrooted_rf_distance_multifurcation():
+    a = make_tree(treestring="(a, b, (c, (d, e)));")
+    b = make_tree(treestring="(a, b, (c, d, e));")
+
+    # There is one split not in common.
+    # Tree a: abc-de
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 1
+
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 1
+
+    a = make_tree(treestring="(a, b, (((c1, c2), (d1, (d2, d3))), (e1, (e2, e3))));")
+    b = make_tree(treestring="(a, b, ((c1, c2), (d2, (d1, d3)), (e1, e2, e3)));")
+
+    # There are four splits not in common
+    # Tree a: e1-others, d2,d3-others, c's and d's - others
+    # Tree b: d1,d3-others
+    distance = unrooted_robinson_foulds(a, b)
+    assert distance == 4
+    distance = unrooted_robinson_foulds(b, a)
+    assert distance == 4
+
+
+# lin_rajan_moret distance
+def test_lrm_different_trees():
     a = make_tree(treestring="(1,(((2,3),4),(5,((6,(7,(8,9))),(10,11)))),12);")
     b = make_tree(treestring="(1,((((2,3),4),5),((6,7),((8,9),(10,11)))),12);")
     distance = lin_rajan_moret(a, b)
     assert distance == 8
 
 
-def test_dist_matches_original_implementation_small_tree(DATA_DIR):
+def test_lrm_matches_original_implementation_small_tree(DATA_DIR):
     path, expect = DATA_DIR / "match_dist_100.tree", 1402
     data = path.read_text().splitlines()
     t1 = make_tree(data[0])
@@ -24,7 +108,7 @@ def test_dist_matches_original_implementation_small_tree(DATA_DIR):
 
 
 @pytest.mark.slow
-def test_dist_matches_original_implementation_bigtree(DATA_DIR):
+def test_lrm_matches_original_implementation_big_tree(DATA_DIR):
     path, expect = DATA_DIR / "match_dist_2000.tree", 17037
     data = pathlib.Path(path).read_text().splitlines()
     t1 = make_tree(data[0])
@@ -34,40 +118,255 @@ def test_dist_matches_original_implementation_bigtree(DATA_DIR):
     assert distance == expect
 
 
-def test_same_tree():
+def test_lrm_same_tree():
+    # Topology of the unrooted trees are identical
+    # though they are stored in different orientations.
     a = make_tree(treestring="(a, b, (c, d));")
     b = make_tree(treestring="(c, d, (a, b));")
+
     distance = lin_rajan_moret(a, b)
     assert distance == 0
 
+    distance = lin_rajan_moret(b, a)
+    assert distance == 0
+
+
+# rooted rf distance
+def test_rooted_rf_multifurcation():
+    a = make_tree(treestring="((a, b), (c, d));")
+    b = make_tree(treestring="((a, c, b), d);")
+
+    # There are three clades not in common
+    # Tree a: ab, cd
+    # Tree b: acb
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 3
+
+    distance = rooted_robinson_foulds(b, a)
+    assert distance == 3
+
+
+def test_rooted_rf_different_trees():
+    a = make_tree(
+        treestring="((((a1,a2),(b1,b2,b3),x),(c1,c2,c3),(d1,d2)),(e1,(e2,e3)));"
+    )
+    b = make_tree(
+        treestring="((((a1,a2),(b1,b2,b3)),x,(c1,c2,c3),(d1,d2)),(e1,(e2,e3)));"
+    )
+
+    # Moving the single x up one level creates two clades that are not in common.
+    # Tree a: ABx
+    # Tree b: AB
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 2
+
+    distance = rooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    a = make_tree(treestring="((a,b),c);")
+    b = make_tree(treestring="((a,c),b);")
+
+    # There are two clades not in common
+    # Tree a: ab
+    # Tree b: ac
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 2
+
+    distance = rooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    a = make_tree(treestring="((a,(b1,(b2,b3))),((c1,c2),(c3,c4)));")
+    b = make_tree(treestring="((a,((c1,c2),(c3,c4))),(b1,(b2,b3)));")
+
+    # There are two clades not in common
+    # Tree a: aB
+    # Tree b: aC
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 2
+
+    distance = rooted_robinson_foulds(b, a)
+    assert distance == 2
+
+    a = make_tree(treestring="(a,(b,(c,(d,(e,f)))));")
+    b = make_tree(treestring="(a,(f,(c,(d,(b,e)))));")
+
+    # There are six clades not in common
+    # Tree a: ef, def, cdef
+    # Tree b: be, bde, bcde
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 6
+
+    distance = rooted_robinson_foulds(b, a)
+    assert distance == 6
+
+
+def test_rooted_rf_same_tree():
+    a = make_tree(treestring="((a, b), (c, d));")
+    b = make_tree(treestring="((c, d), (a, b));")
+
+    # The distance between trees of the same topology is 0
+    distance = rooted_robinson_foulds(a, b)
+    assert distance == 0
+
+
+# matching cluster distance
+def test_matching_cluster_distance_multifurcation():
+    # The basic example from the matching cluster distance paper
+    # see reference in matching_cluster_distance
+    a = make_tree(treestring="((a, b), (c, d));")
+    b = make_tree(treestring="((a, c, b), d);")
+
+    distance = matching_cluster_distance(a, b)
+    assert distance == 3
+
+    distance = matching_cluster_distance(b, a)
+    assert distance == 3
+
+
+def test_matching_cluster_distance_properties():
+    # Test properties of the matching cluster distance paper shown as exampels
+    # see reference in matching_cluster_distance
+    a = make_tree(
+        treestring="((((a1,a2),(b1,b2,b3),x),(c1,c2,c3),(d1,d2)),(e1,(e2,e3)));"
+    )
+    b = make_tree(
+        treestring="((((a1,a2),(b1,b2,b3)),x,(c1,c2,c3),(d1,d2)),(e1,(e2,e3)));"
+    )
+
+    distance = matching_cluster_distance(a, b)
+    assert distance == 1
+
+    distance = matching_cluster_distance(b, a)
+    assert distance == 1
+
+    a = make_tree(treestring="((a,b),c);")
+    b = make_tree(treestring="((a,c),b);")
+
+    distance = matching_cluster_distance(a, b)
+    assert distance == len(a.tips()) - 1
+
+    distance = matching_cluster_distance(b, a)
+    assert distance == len(a.tips()) - 1
+
+    a = make_tree(treestring="((a,(b1,(b2,b3))),((c1,c2),(c3,c4)));")
+    b = make_tree(treestring="((a,((c1,c2),(c3,c4))),(b1,(b2,b3)));")
+
+    distance = matching_cluster_distance(a, b)
+    assert distance == len(a.tips()) - 1
+
+    distance = matching_cluster_distance(b, a)
+    assert distance == len(a.tips()) - 1
+
+
+def test_matching_cluster_distance_same_tree():
+    a = make_tree(treestring="((a, b), (c, d));")
+    b = make_tree(treestring="((c, d), (a, b));")
+
+    # The distance between trees of the same topology is 0
+    distance = matching_cluster_distance(a, b)
+    assert distance == 0
+
 
+# different tips
 @pytest.mark.parametrize(
     "b",
     (
         "(e, d, (a, b));",
-        "(a, d, (a, b))",
+        "(a, d, (a, b));",
+        "(a, b, (c, (d, e)));",
+    ),
+)
+def test_unrooted_rf_fails_different_tips(b):
+    t1 = make_tree(treestring="(a, b, (c, d));")
+    t2 = make_tree(treestring=b)
+    with pytest.raises(ValueError):
+        unrooted_robinson_foulds(t1, t2)
+    with pytest.raises(ValueError):
+        unrooted_robinson_foulds(t2, t1)
+
+
+@pytest.mark.parametrize(
+    "b",
+    (
         "(e, d, (a, b));",
-        "((e, d), (a, b));",
-        "((e, d), (a, b));",
+        "(a, d, (a, b));",
+        "(a, b, (c, (d, e)));",
     ),
 )
-def test_fails_different_tips(b):
+def test_lrm_fails_different_tips(b):
     t1 = make_tree(treestring="(a, b, (c, d));")
     t2 = make_tree(treestring=b)
     with pytest.raises(ValueError):
         lin_rajan_moret(t1, t2)
+    with pytest.raises(ValueError):
+        lin_rajan_moret(t2, t1)
 
 
+@pytest.mark.parametrize(
+    "b",
+    (
+        "((e, d), (a, b));",
+        "((a, d), (a, b));",
+        "(a, (b, (c, (d, e))));",
+    ),
+)
+def test_rooted_rf_fails_different_tips(b):
+    t1 = make_tree(treestring="((a, b), (c, d));")
+    t2 = make_tree(treestring=b)
+    with pytest.raises(ValueError):
+        rooted_robinson_foulds(t1, t2)
+    with pytest.raises(ValueError):
+        rooted_robinson_foulds(t2, t1)
+
+
+@pytest.mark.parametrize(
+    "b",
+    (
+        "((e, d), (a, b));",
+        "((a, d), (a, b));",
+        "(a, (b, (c, (d, e))));",
+    ),
+)
+def test_matching_cluster_fails_different_tips(b):
+    t1 = make_tree(treestring="((a, b), (c, d));")
+    t2 = make_tree(treestring=b)
+    with pytest.raises(ValueError):
+        matching_cluster_distance(t1, t2)
+    with pytest.raises(ValueError):
+        matching_cluster_distance(t2, t1)
+
+
+# unrooted distance measures applied to examples with rooted trees
 @pytest.mark.parametrize(
     "a,b",
     (
-        ("((a, b), (c, d));", "(e, d, (a, b));"),
-        ("(a, b, (c, d));", "((e, d), (a, b));"),
-        ("((a, b), (c, d));", "((e, d), (a, b));"),
+        ("((a, b), (c, d));", "(d, c, (a, b));"),
+        ("(a, b, (c, d));", "((d, c), (a, b));"),
+        ("((a, b), (c, d));", "((a, c), (b, d));"),
     ),
 )
-def test_fails_unrooted(a, b):
+def test_unrooted_dist_fails_rooted_trees(a, b):
     t1 = make_tree(treestring=a)
     t2 = make_tree(treestring=b)
-    with pytest.raises(ValueError):
-        lin_rajan_moret(t1, t2)
+
+    for unrooted_distance_measure in UNROOTED_DISTANCE_MEASURES:
+        with pytest.raises(ValueError):
+            unrooted_distance_measure(t1, t2)
+
+
+# rooted distance measures applied to examples with unrooted trees
+@pytest.mark.parametrize(
+    "a,b",
+    (
+        ("((a, b), (c, d));", "(d, c, (a, b));"),
+        ("(a, b, (c, d));", "((d, c), (a, b));"),
+        ("(a, b, (c, d));", "(d, c, (a, b));"),
+    ),
+)
+def test_rooted_dist_fails_unrooted_trees(a, b):
+    t1 = make_tree(treestring=a)
+    t2 = make_tree(treestring=b)
+
+    for rooted_distance_measure in ROOTED_DISTANCE_MEASURES:
+        with pytest.raises(ValueError):
+            rooted_distance_measure(t1, t2)