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
| Function | What it compares |
|---|---|
joint_dissimilarity | Matched reticulations plus the reticulation-free remainders. New in 0.7.0; described below. |
mu_distance | Multisets of path-count vectors (Cardona et al., 2009). A metric on reduced networks. |
hardwired_cluster_distancesoftwired_cluster_distance | Symmetric difference of the cluster sets, hardwired or pooled over all displayed trees. |
tripartition_distancedisplayed_tree_distancerobinson_foulds_distance | Symmetric difference of tree-node tripartitions, of displayed-tree topologies, or of non-trivial clusters. |
average_path_distanceweighted_average_path_distance | Branch-length-aware leaf-to-leaf path differences averaged over displayed trees (Yakici, Ogilvie & Nakhleh, 2022). |
hybrid_ancestry_error | Balanced false-positive and false-negative rate of the set of taxa below a reticulation. Asymmetric: pass the estimate first. |
compare_networks | Reticulation precision, recall and F1 from a tripartition matching, alongside a global metric. |
is_isomorphic | Exact 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.
-
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, andD_retis the cost of the cheapest one-to-one matching (one Hungarian solve). -
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_treeis the dissimilarity of the two remainders.
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
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:
| Field | Meaning |
|---|---|
kind | The instantiation used. |
r1, r2, m | Reticulation numbers of the two networks and their maximum. |
D_ret | Matching cost of the tripartitions, in [0, 3m]. |
D_tree | Dissimilarity of the two remainders, in [0, 1]. |
D_joint | D_ret + 3 D_tree, in [0, 3(m + 1)]. |
D_ret_normalized, D_joint_normalized | The 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.
"""
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.