PhyNetPy Documentation

Library for the Development and Use of Phylogenetic Network Methods

ReticulationComparison Module v0.5.0

Reticulation-aware network comparison: tripartition matching, Nakhleh metric, and precision/recall over reticulations.

Author:
Mark Kessler
Source:
ReticulationComparison.py

Constants

JACCARD = 'jaccard'
SYMMETRIC = 'symmetric'

ReticulationTripartition

class ReticulationTripartition

The reticulation tripartition ``theta_h = (A_h, B_h, C_h)`` of a reticulation node ``h`` with parents ``u`` and ``v`` (Definition 1). * ``B = L(h)`` is the cluster of the hybrid (its leaf descendants); * ``A = L(u) \ L(h)`` are the descendants contributed by parent ``u`` other than through ``h``; * ``C = L(v) \ L(h)`` likewise for parent ``v``. Because ``L(h)`` is a subset of both ``L(u)`` and ``L(v)``, the middle block is always disjoint from the outer blocks; the two outer blocks are disjoint iff the parents share no descendant except through ``h`` (Proposition 1). There is no canonical order on the two parents, so the triple is only defined up to the swap ``(A, B, C) <-> (C, B, A)`` (Remark 2); every comparison in this module is invariant under that swap. Attributes: A (FrozenSet[...

Methods

is_proper -> bool

Whether the three blocks are pairwise disjoint (Proposition 1). The tripartition is proper iff the two parents share no descendant outside the hybrid, i.e. ``A`` and ``C`` are disjoint (the middle block is disjoint from the outer blocks unconditionally).

Returns: bool: True if ``A``, ``B``, ``C`` are pairwise disjoint.
swapped -> 'ReticulationTripartition'

Return the parent-swapped tripartition ``(C, B, A)`` (Remark 2).

Returns: ReticulationTripartition: The swapped triple.

NetworkComparison

class NetworkComparison

The result of :func:`compare_networks`: a reticulation-aware comparison of a reference network against an inferred one. Iterating the object yields exactly the ``(D, D_ret_hat, Prec, Rec)`` tuple that Section 9 specifies as the library's score entry point, so:: D, D_ret_hat, prec, rec = compare_networks(reference, inferred) while the remaining fields expose the unnormalized metrics (for callers that rely on the metric axioms; Remark 4), the matching, and the recovery counts. Attributes: D (float): Global metric ``D`` (unnormalized; Equation 5). D_hat (float): Bounded global score ``2 D / (|V1| + |V2|)`` in ``[0, 1]``. D_ret (float): Reticulation dissimilarity ``D_ret`` (unnormalized metric on tripartition multisets; Equation 4). D_ret_hat (float): Normalized reticulation dissimilarity ``D_...

Methods

__iter__

Yield the ``(D, D_ret_hat, Prec, Rec)`` tuple of Section 9.

as_tuple -> Tuple[float, float, float, float]

Return the ``(D, D_ret_hat, Prec, Rec)`` score tuple.

Returns: Tuple[float, float, float, float]: The four headline scores.
combined(lam: float) -> float

The unnormalized convex combination ``D_lambda`` (Equation 6). ``D_lambda = lambda * D_ret + (1 - lambda) * D`` is a metric for every ``lambda < 1`` on any class where ``D`` is a metric, and a pseudometric at ``lambda = 1`` (Proposition 5).

Parameter Type Description
lam float Weight ``lambda`` in ``[0, 1]`` on the reticulation term.
Returns: float: ``D_lambda(N1, N2)``.
combined_normalized(lam: float) -> float

The bounded reporting combination ``lambda * D_ret_hat + (1 - lambda) * D_hat`` (Remark 4). This trades the triangle inequality for a value in ``[0, 1]``.

Parameter Type Description
lam float Weight ``lambda`` in ``[0, 1]`` on the reticulation term.
Returns: float: The bounded combined score.

Module Functions

set_distance(P: FrozenSet[str], Q: FrozenSet[str], kind: str = JACCARD) -> float

Distance between two finite sets of leaf labels (Equations 1--2). Two choices are supported, both of which are metrics on finite sets: * :data:`SYMMETRIC` -- the symmetric-difference cardinality ``|P triangle Q|``; * :data:`JACCARD` -- the normalized Jaccard distance ``|P triangle Q| / |P union Q|`` (0 when both sets are empty), which takes values in ``[0, 1]``.

Parameter Type Description
P FrozenSet[str] First set of leaf labels.
Q FrozenSet[str] Second set of leaf labels.
kind str Either :data:`JACCARD` (default) or :data:`SYMMETRIC`.
Returns: float: The set distance ``d(P, Q)``.
Raises: NetworkError: If ``kind`` is not a recognized distance.
reticulation_tripartitions(net: Network) -> List[ReticulationTripartition]

Compute the reticulation tripartitions of a network (Definition 1). One tripartition ``(A_h, B_h, C_h)`` is produced per reticulation node ``h``. A tree (no reticulations) yields the empty list.

Parameter Type Description
net Network A phylogenetic network. Every reticulation node is assumed binary (in-degree exactly 2).
Returns: List[ReticulationTripartition]: One tripartition per reticulation, as a (multiset-representing) list.
Raises: NetworkError: If a reticulation node does not have exactly two parents, i.e. the binary-network assumption is violated.
tripartition_dissimilarity(theta: ReticulationTripartition, theta_prime: ReticulationTripartition, kind: str = JACCARD, normalize: bool = False) -> float

Tripartition dissimilarity ``delta`` between two reticulations (Equation 3, the leaf-set variant of Sections 4--5). ``delta`` is a metric on tripartitions (up to parent swap) whenever the ground set distance is a metric (Proposition 2). Under the Jaccard ground distance ``delta`` lies in ``[0, 3]``; ``normalize=True`` divides by 3 to give ``delta_bar`` in ``[0, 1]`` (Remark 3).

Parameter Type Description
theta ReticulationTripartition First tripartition.
theta_prime ReticulationTripartition Second tripartition.
kind str Ground set distance, :data:`JACCARD` or :data:`SYMMETRIC`.
normalize bool If True (and ``kind`` is Jaccard), divide by 3 to return ``delta_bar`` in ``[0, 1]``.
Returns: float: ``delta`` (or ``delta_bar`` when normalized).
nakhleh_metric(net1: Network, net2: Network, normalize: bool = False) -> float

Nakhleh's global metric ``D`` on reduced phylogenetic networks (Equation 5). ``D`` is half the cardinality of the symmetric difference of the two multisets of rooted subnetworks (each subnetwork counted with its multiplicity ``kappa``): ``D(N1, N2) = 0.5 * sum_key |kappa_N1(key) - kappa_N2(key)|``. It is a metric on reduced networks, tree-child networks, semibinary tree-sibling time-consistent networks, and multilabeled trees, computable in polynomial time, and reduces on trees to half the symmetric difference of their rooted-subtree multisets. Being global, it separates networks but is dominated by tree-like structure -- which is precisely why the note pairs it with the reticulation-aware :func:`reticulation_dissimilarity`.

Parameter Type Description
net1 Network First network.
net2 Network Second network.
normalize bool If True, return the bounded score ``D_hat = 2 D / (|V1| + |V2|)`` in ``[0, 1]``.
Returns: float: ``D`` (or ``D_hat`` when normalized).
compare_networks(reference: Network, inferred: Network, distance: str = JACCARD, rho: Optional[float] = None, tolerance: float = 0.0, alpha: float = 1.0) -> NetworkComparison

Reticulation-aware comparison of a reference network against an inferred one -- the single score entry point of Section 9. Computes, in one pass over the reticulations, the global metric ``D`` (Eq. 5), the reticulation dissimilarity ``D_ret`` and its normalized form ``D_ret_hat`` (Eq. 4), and reticulation-level precision / recall / F1 (Definition 4). The returned :class:`NetworkComparison` is iterable, yielding the headline ``(D, D_ret_hat, Prec, Rec)`` tuple. Reference / inferred orientation matters for precision and recall: recall is ``g / r(reference)`` (fraction of true events recovered) and precision is ``g / r(inferred)`` (fraction of inferred events that are correct), with the conventions ``Prec = 1`` when ``r(inferred) = 0`` and ``Rec = 1`` when ``r(reference) = 0`` (Definition 4). ``D`` and ``D_ret`` themselves are symmetric. Boundary behaviour (Section 6.1): two trees give ``D_ret_hat = 0``; a network compared against a tree gives ``D_ret_hat = 1`` (every reticulation is unmatched); self-comparison gives all zeros with ``Prec = Rec = 1``.

Parameter Type Description
reference Network The reference (true) network ``N1``.
inferred Network The inferred network ``N2``.
distance str Ground set distance, :data:`JACCARD` (default) or :data:`SYMMETRIC`.
rho Optional[float] Deletion penalty for an unmatched reticulation. Defaults to the maximum real--real ``delta`` (3 under Jaccard), i.e. "maximally wrong".
tolerance float Recovery tolerance ``tau >= 0``; a matched pair counts as recovered iff its cost is ``<= tau``. ``tau = 0`` demands exact recovery of the hybrid and both parents.
alpha float Block weight in ``[0, 1]`` for the topology-aware refinement (Section 8). ``alpha = 1`` (default) is the leaf-set measure; ``alpha < 1`` mixes in the induced sub-network distance ``D``.
Returns: NetworkComparison: The bundled scores and optimal matching.
Raises: NetworkError: If a distance name is unrecognized, if ``alpha`` / ``tolerance`` are out of range, or if a reticulation is not binary.
reticulation_dissimilarity(net1: Network, net2: Network, distance: str = JACCARD, rho: Optional[float] = None, alpha: float = 1.0, normalize: bool = True) -> float

Reticulation dissimilarity ``D_ret`` between two networks (Equation 4). A convenience wrapper over :func:`compare_networks` that returns just the scalar. ``D_ret`` is a pseudometric on networks (a metric on reticulation-tripartition multisets) under the penalty condition of Proposition 3, and is deliberately blind to tree-only differences.

Parameter Type Description
net1 Network First network.
net2 Network Second network.
distance str Ground set distance, :data:`JACCARD` or :data:`SYMMETRIC`.
rho Optional[float] Deletion penalty; see :func:`compare_networks`.
alpha float Block weight for the topology-aware refinement.
normalize bool If True (default), return the bounded ``D_ret_hat`` in ``[0, 1]``; otherwise the unnormalized metric ``D_ret``.
Returns: float: ``D_ret_hat`` (normalized) or ``D_ret`` (unnormalized).
reticulation_precision_recall(reference: Network, inferred: Network, distance: str = JACCARD, rho: Optional[float] = None, tolerance: float = 0.0, alpha: float = 1.0) -> Tuple[float, float, float]

Reticulation precision, recall, and F1 (Definition 4). A convenience wrapper over :func:`compare_networks`. With ``reference`` the true network and ``inferred`` the estimate, recall is the fraction of true reticulations recovered and precision the fraction of inferred reticulations that are correct, where "recovered" means matched at cost ``<= tolerance``.

Parameter Type Description
reference Network The reference (true) network.
inferred Network The inferred network.
distance str Ground set distance.
rho Optional[float] Deletion penalty; see :func:`compare_networks`.
tolerance float Recovery tolerance ``tau >= 0``.
alpha float Block weight for the topology-aware refinement.
Returns: Tuple[float, float, float]: ``(precision, recall, f1)``.
combined_dissimilarity(net1: Network, net2: Network, lam: float = 0.5, distance: str = JACCARD, rho: Optional[float] = None, alpha: float = 1.0, normalize: bool = False) -> float

The convex combination ``D_lambda`` of the reticulation and global terms (Equation 6). ``D_lambda = lambda * D_ret + (1 - lambda) * D`` interpolates between the global comparison (``lambda -> 0``) and the reticulation-aware one (``lambda -> 1``). On any class where ``D`` is a metric it is a metric for every ``lambda < 1`` and a pseudometric at ``lambda = 1`` (Proposition 5).

Parameter Type Description
net1 Network First network.
net2 Network Second network.
lam float Weight ``lambda`` in ``[0, 1]`` on the reticulation term.
distance str Ground set distance.
rho Optional[float] Deletion penalty; see :func:`compare_networks`.
alpha float Block weight for the topology-aware refinement.
normalize bool If True, combine the bounded scores ``lambda * D_ret_hat + (1 - lambda) * D_hat`` in ``[0, 1]`` (Remark 4); otherwise the unnormalized metrics.
Returns: float: ``D_lambda`` (unnormalized) or its bounded reporting form.
Raises: NetworkError: If ``lam`` is outside ``[0, 1]``.

Navigation

Modules

This Page