Comparing Networks

How to measure the distance between two phylogenetic networks in PhyNetPy, and a walkthrough of the joint reticulation-and-tree dissimilarity introduced in version 0.7.0.

Why compare networks?

Almost every use of a phylogenetic network method ends with a comparison. A simulation study checks an inferred network against the network that generated the data; a bootstrap or a posterior sample asks how much a set of networks disagree; two methods run on the same data return two answers. Each of these needs a number that says how far apart two networks are.

For trees, the Robinson–Foulds distance is the standard answer. Networks are harder. The classical network measures (cluster distances, the mu-distance, displayed-tree distances) compare a network in bulk, and because nearly all of a network is tree-like, a misplaced hybrid edge barely moves them. The hybrid edges are usually the reason the analysis was run, so PhyNetPy 0.7.0 adds a measure that scores them separately: the joint reticulation-and-tree dissimilarity.

Comparing networks in PhyNetPy

Every comparison measure takes two Network objects on the same taxon set and is importable from the top-level phynetpy namespace. read_newick reads extended Newick, where a #H label marks a reticulation.

from phynetpy import read_newick, joint_dissimilarity, mu_distance, hybrid_ancestry_error

estimate = read_newick("((A,(B)#H1),(#H1,C));")
truth = read_newick("(((A)#H1,B),(#H1,C));")

joint_dissimilarity(estimate, truth).D_joint_normalized   # in [0, 1]
mu_distance(estimate, truth)                              # a count
hybrid_ancestry_error(estimate, truth)                    # asymmetric: estimate first
FunctionWhat it compares
joint_dissimilarityMatched reticulations plus the reticulation-free remainders. New in 0.7.0; described below.
mu_distanceMultisets of path-count vectors (Cardona et al., 2009). A metric on reduced networks.
hardwired_cluster_distance
softwired_cluster_distance
Symmetric difference of the cluster sets, hardwired or pooled over all displayed trees.
tripartition_distance
displayed_tree_distance
robinson_foulds_distance
Symmetric difference of tree-node tripartitions, of displayed-tree topologies, or of non-trivial clusters.
average_path_distance
weighted_average_path_distance
Branch-length-aware leaf-to-leaf path differences averaged over displayed trees (Yakici, Ogilvie & Nakhleh, 2022).
hybrid_ancestry_errorBalanced false-positive and false-negative rate of the set of taxa below a reticulation. Asymmetric: pass the estimate first.
compare_networksReticulation precision, recall and F1 from a tripartition matching, alongside a global metric.
is_isomorphicExact topological identity, ignoring labels and branch lengths.

The symmetric-difference measures accept normalize=True to return a value in [0, 1]. The displayed-tree measures enumerate up to 2k trees for k reticulations, so keep them to small networks.

The joint dissimilarity

Take two rooted networks N1 and N2 on the same taxa, with r1 and r2 reticulations, and let m = max(r1, r2). The measure has two parts.

  1. Reticulations. Every reticulation h is summarised by a tripartition (A, B, C): B is the block below h, and A and C are the blocks below its two parents once h is deleted. Two tripartitions cost d(B, B') + min(d(A, A') + d(C, C'), d(A, C') + d(C, A')), a number in [0, 3] that does not care which parent is called A. The shorter list is padded with dummies to length m, a real–dummy pair costs 3, and D_ret is the cost of the cheapest one-to-one matching (one Hungarian solve).
  2. Remainder. Deleting the block below every reticulation and hanging one marker leaf per surviving parent edge, labelled by the taxa that were below the reticulation, leaves a tree-like remainder T(N). D_tree is the dissimilarity of the two remainders.
D_joint = D_ret + 3 · D_tree

D_ret_normalized = D_ret / 3m (0 when both are trees) and D_joint_normalized = D_joint / 3(m + 1) both lie in [0, 1].

The structure dissimilarity d used on blocks and remainders is chosen by the kind argument, from coarse to fine:

  • "leaf": Jaccard distance of the two leaf-label sets.
  • "cluster": multiset dissimilarity of the hardwired clusters, one per vertex.
  • "nakhleh" (default): multiset dissimilarity of Nakhleh's vertex-equivalence classes (Nakhleh, 2010), which sees the full shape of each structure.

Under every instantiation the measure is symmetric, is 0 on identical networks, and is a metric on the tripartition and remainder representations. Branch lengths, inheritance probabilities and internal-node labels are ignored. Each network must have one root, labelled leaves with no label used twice, and reticulations with exactly two distinct parents and one child; anything else raises NetworkError rather than being scored silently.

A worked example

A B C #H1 N1 = ((A,(B)#H1),(#H1,C)); tripartition: ( {A} | {B} | {C} ) B A C #H1 N2 = (((A)#H1,B),(#H1,C)); tripartition: ( {B} | {A} | {C} )
Two one-reticulation networks on A, B and C. Dashed orange edges are the hybrid edges; the networks differ only in which taxon the reticulation delivers.

Under kind="leaf", the hybrid blocks {B} and {A} are disjoint, so d(B, B') = 1. The cheaper pairing of the parent sides matches {A} with {B} (cost 1) and {C} with {C} (cost 0), so the tripartition cost is 2 and D_ret = 2. Each remainder keeps the taxa outside its hybrid block plus a marker for the reticulation, giving label sets {A, C, m(B)} and {B, C, m(A)}: four of the five labels differ, so D_tree = 0.8. Then D_joint = 2 + 3 × 0.8 = 4.4, and dividing by 3(m + 1) = 6 gives D_joint_normalized = 0.733. The script below reproduces these numbers and shows the finer instantiations on the same pair.

Reading the result

joint_dissimilarity returns a frozen JointDissimilarityResult:

FieldMeaning
kindThe instantiation used.
r1, r2, mReticulation numbers of the two networks and their maximum.
D_retMatching cost of the tripartitions, in [0, 3m].
D_treeDissimilarity of the two remainders, in [0, 1].
D_jointD_ret + 3 D_tree, in [0, 3(m + 1)].
D_ret_normalized, D_joint_normalizedThe two terms rescaled into [0, 1].

The same call is available as a method, net1.joint_dissimilarity(net2, kind).

Example script

The script below is self-contained: it needs PhyNetPy and nothing else, since the networks are written inline. Copy it, download it, or open it in Google Colab, which installs PhyNetPy and runs the same code in your browser.

Download .py Run in Google Colab Also in the PhyNetPy repository as examples/joint_dissimilarity_demo.py.
"""
joint_dissimilarity_demo.py -- compare two phylogenetic networks with PhyNetPy.

Runs anywhere PhyNetPy is installed and needs no other files:

    pip install phynetpy
    python joint_dissimilarity_demo.py

The joint dissimilarity scores two rooted networks on the same taxa in two
parts.  Every reticulation is summarised by a tripartition (the block below
it and the two parent blocks with it deleted), and D_ret is the cost of the
best one-to-one matching of the two tripartition collections, with an
unmatched reticulation charged 3.  Deleting every reticulation block leaves a
tree-like remainder in each network, and D_tree compares those.  Then

    D_joint = D_ret + 3 * D_tree

with normalised forms in [0, 1].  Blocks and remainders are compared by one
of three structure dissimilarities: "leaf" (which taxa), "cluster" (which
clusters) or "nakhleh" (which vertex-equivalence classes; the default).
"""

import warnings

from phynetpy import read_newick, joint_dissimilarity

# The reader warns once per node when a Newick string carries no branch
# lengths.  The measure ignores lengths, so the warning is noise here.
warnings.filterwarnings("ignore", message="No branch length")


def report(title, r):
    """Print every field of a JointDissimilarityResult."""
    print(title)
    print(f"  reticulations        r1 = {r.r1}, r2 = {r.r2}   (m = {r.m})")
    print(f"  D_ret   (matching)   {r.D_ret:.3f}   normalised {r.D_ret_normalized:.3f}")
    print(f"  D_tree  (remainder)  {r.D_tree:.3f}")
    print(f"  D_joint              {r.D_joint:.3f}   normalised {r.D_joint_normalized:.3f}")
    print()


# Two one-reticulation networks on taxa A, B, C.  They differ only in which
# taxon the hybrid edge delivers: B in the estimate, A in the truth.
estimate = read_newick("((A,(B)#H1),(#H1,C));")
truth = read_newick("(((A)#H1,B),(#H1,C));")

# 1. The headline call.  Order does not matter: the measure is symmetric.
report("estimate vs truth", joint_dissimilarity(estimate, truth))

# 2. The three instantiations differ only in how two structures are compared.
#    Under "leaf", the hybrid blocks {B} and {A} cost 1 and the parent sides
#    cost 1 more, so D_ret = 2; the remainders share one of five labels, so
#    D_tree = 0.8 and D_joint = 2 + 3 * 0.8 = 4.4.
for kind in ("leaf", "cluster", "nakhleh"):
    r = joint_dissimilarity(estimate, truth, kind=kind)
    print(f"kind = {kind:8s}  D_ret = {r.D_ret:.3f}  D_tree = {r.D_tree:.3f}"
          f"  D_joint_normalized = {r.D_joint_normalized:.3f}")
print()

# 3. A tree has no reticulation, so the network's one is left unmatched and
#    charged the full cost of 3: the normalised reticulation term is 1.
tree = read_newick("((A,B),C);")
report("tree vs estimate", joint_dissimilarity(tree, estimate))

# 4. Identical topologies score 0.  Branch lengths, inheritance probabilities
#    and internal labels are ignored.
same = read_newick("((A:0.1,(B:0.2)#H1[&gamma=0.6]:0.3)X:0.4,(#H1:0.5,C:0.6)Y:0.7)Root;")
report("estimate vs itself, with branch lengths", joint_dissimilarity(estimate, same))

# 5. The same measure is available as a Network method.
r = estimate.joint_dissimilarity(truth, kind="cluster")
print(f"method form, kind = cluster:  D_joint_normalized = {r.D_joint_normalized:.3f}")

Running it locally

In a fresh virtual environment with a C compiler available:

pip install phynetpy
python joint_dissimilarity_demo.py

Expected output

estimate vs truth
  reticulations        r1 = 1, r2 = 1   (m = 1)
  D_ret   (matching)   2.000   normalised 0.667
  D_tree  (remainder)  0.923
  D_joint              4.769   normalised 0.795

kind = leaf      D_ret = 2.000  D_tree = 0.800  D_joint_normalized = 0.733
kind = cluster   D_ret = 2.000  D_tree = 0.923  D_joint_normalized = 0.795
kind = nakhleh   D_ret = 2.000  D_tree = 0.923  D_joint_normalized = 0.795

tree vs estimate
  reticulations        r1 = 0, r2 = 1   (m = 1)
  D_ret   (matching)   3.000   normalised 1.000
  D_tree  (remainder)  0.800
  D_joint              5.400   normalised 0.900

estimate vs itself, with branch lengths
  reticulations        r1 = 1, r2 = 1   (m = 1)
  D_ret   (matching)   0.000   normalised 0.000
  D_tree  (remainder)  0.000
  D_joint              0.000   normalised 0.000

method form, kind = cluster:  D_joint_normalized = 0.795

References

  • L. Nakhleh. Reticulation-Aware Dissimilarity for Phylogenetic Networks. Manuscript, 2026.
  • L. Nakhleh. A metric on the space of reduced phylogenetic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 7 (2010), 218–222.
  • G. Cardona, M. Llabrés, F. Rosselló and G. Valiente. Metrics for phylogenetic networks I: generalizations of the Robinson–Foulds metric. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6 (2009), 46–61.
  • B. Yakici, H. Ogilvie and L. Nakhleh. Phylogenetic network dissimilarity measures that take branch lengths into account. RECOMB-CG 2022, LNCS 13234, 86–102.
  • PhyNetPy on PyPI and GitHub; release notes for 0.7.0 are in the repository.