Library for the Development and Use of Phylogenetic Network Methods
Network decomposition, distances, and structural edits: blobs, tree-of-blobs, cluster/mu/tripartition distances, reticulation-aware comparison, and ASCII rendering.
Compile the set of clusters that make up this network. Ie: for a graph ((A, B)C, D); , set of all clusters is {(A,B), (A,B,C)}. A cluster is the set of leaves below some non-root node. Clusters of size 1 can optionally be included. Note that clusters are sets of :class:`~phynetpy.Network.Node` objects belonging to *this* network, so they cannot be compared across networks; use :func:`network_clusters` for that.
| Parameter | Type | Description |
|---|---|---|
| net | Network | the network to operate on |
| include_trivial | bool | If set to True, includes clusters of size 1. Defaults to False. |
Compute the minimally sized subnetwork of a network such that the leaf set of the subnetwork is a subset of the original network's leaf set.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network |
| leaf_set | list[Node] | A set of leaf nodes of the given network |
Generate all possible trees that can be derived from the given network by removing hybrid edges and creating copies with subtrees that start at each non-reticulation node.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object |
Generate the dominant tree from a given network by retaining only the reticulation edges with the highest inheritance probability and removing all other reticulation edges.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object |
Count the number of reticulation nodes in a network.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
Add a hybrid (reticulation) edge between two existing edges, raising the network level by one. This is a structural edit, not a Metropolis-Hastings proposal: it mutates ``net`` in place and reports no Hastings ratio. Samplers should use the :class:`~.ModelMove.AddReticulation` move instead, which carries the reversible-jump proposal math. How it works (normal case, ``source != destination``):: BEFORE AFTER a x a x | | | | | | n1 -------> n2 (new hybrid edge) | | | | b y b y Two fresh internal nodes (n1, n2) are inserted by splitting the ``source`` and ``destination`` edges respectively. n2 is flagged as a reticulation node, and a directed edge n1 -> n2 is added. When ``source`` and ``destination`` are the *same* edge, two parallel edges with equal inheritance probabilities (gamma = 0.5) are created between two new internal nodes, modeling a whole-genome duplication ("bubble") event.
| Parameter | Type | Description |
|---|---|---|
| net | Network | The network to modify in place. |
| source | Edge | The edge that will donate the new outgoing lineage. |
| destination | Edge | The edge that will receive the incoming hybrid lineage. |
| t_src | float, optional | Divergence time for the new source-side node. Defaults to None. |
| t_dest | float, optional | Divergence time for the new reticulation node. Defaults to None. |
Compute pairwise distances between leaves on the underlying undirected graph. If use_branch_lengths is True, sum edge lengths; otherwise, use unit weights.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
| use_branch_lengths | bool | Whether to sum edge lengths. |
Compute bridges and articulation points on the underlying undirected graph using Tarjan's algorithm.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
Return the biconnected components ("blobs") of the underlying undirected graph.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
Decompose a phylogenetic network into its biconnected components (blobs). Each blob is a maximal biconnected subgraph of the underlying undirected graph. Returns a list of Network objects, one per biconnected component, containing copies of the original nodes and directed edges. Node names are preserved but all objects are distinct from the original network.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A phylogenetic network. |
Compute the level of a phylogenetic network. The level is the maximum number of reticulation nodes contained in any biconnected component ("blob") of the underlying undirected graph. Returns 0 for trees.
| Parameter | Type | Description |
|---|---|---|
| net | Network | Input network. |
Estimate the number of displayed trees of a network. Computed as the product, over reticulation nodes, of their inbound edge counts (typically 2). For general networks, this is an upper bound when some choices may be incompatible; for level-1 networks this often matches the exact count.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
Check whether a network is a tree (i.e., has no reticulation nodes).
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
Construct the subnetwork induced by a set of leaf labels. The induced subnetwork is formed by taking the MRCA of the target leaves and retaining only those descendant branches that lead to at least one target leaf. Node/edge attributes (gamma, length) are copied where applicable.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A network object. |
| taxa | list[str] | List of leaf labels to induce on. |
NetworkError: If any leaf name is not found in the network.Returns True, if net1 and net2 are topologically identical networks. Even if branch lengths are different, or node labels are different, networks can be isomorphic. ie-- all trees with 3 taxa are isomorphic. quartet trees have only a few different variations. Networks of any size, have infinitely many possible topologies. (A,B)C; is isomorphic with (D,E)F; (A,B),(C,D); is not isomorphic with ((A,B)C, D);
| Parameter | Type | Description |
|---|---|---|
| net1 | Network | A Network object |
| net2 | Network | Another Network object |
The set of non-trivial leaf-label clusters induced by a network's nodes. Label-based rather than node-based, so clusters are comparable *across* networks -- which :func:`get_all_clusters` is not, since it returns sets of :class:`~phynetpy.Network.Node` objects belonging to one graph.
| Parameter | Type | Description |
|---|---|---|
| net | Network | The network to summarise. |
Hardwired cluster distance between two phylogenetic networks. The hardwired cluster of a node v is the set of all leaf labels reachable from v by following every directed edge. The distance is the cardinality of the symmetric difference of the two hardwired cluster sets: d_HC(N1, N2) = |HC(N1) triangle HC(N2)| When *normalize* is True the result is divided by |HC(N1) | HC(N2)|, yielding a value in [0, 1]. Reference --------- Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Return a value in [0, 1] instead of a raw count. |
Softwired cluster distance between two phylogenetic networks. The softwired cluster set of a network is the union of cluster sets across all of its displayed trees. The distance is the cardinality of the symmetric difference: d_SC(N1, N2) = |SC(N1) triangle SC(N2)| .. note:: This enumerates all 2^k displayed trees where k is the number of reticulations. For networks with many reticulations the cost is exponential. When *normalize* is True the result is divided by |SC(N1) | SC(N2)|, yielding a value in [0, 1]. Reference --------- Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Return a value in [0, 1] instead of a raw count. |
Mu-representation distance between two phylogenetic networks. For every node v in a network with leaf set X = {l_1, ..., l_n} the *mu-vector* is mu(v) = (m(v, l_1), ..., m(v, l_n)) where m(v, l_i) is the number of directed paths from v to leaf l_i. The *mu-representation* of a network is the multiset of mu-vectors over all nodes. The distance is the size of the multiset symmetric difference of the two mu-representations. This is a metric on the space of *reduced* phylogenetic networks (networks with no degree-2 tree nodes and no parallel edges). It is also referred to as the *topological distance for reduced networks*. For trees it reduces to the Robinson--Foulds distance. Both networks must share the same leaf label set. Reference --------- Cardona, Llabres, Rossello & Valiente. *Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric*. IEEE/ACM Trans. Comput. Biol. Bioinformatics **6** (2009), 46--61.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. |
NetworkError: If the two networks have different leaf label sets.Tripartition-based distance between two phylogenetic networks. For each tree node u with exactly two children c_1, c_2 the tripartition is (desc(c_1), desc(c_2), X \ (desc(c_1) | desc(c_2))) where X is the full leaf set. The distance is the cardinality of the symmetric difference of the tripartition sets: d_T(N1, N2) = |T(N1) triangle T(N2)| Reticulation nodes (in-degree >= 2) are excluded from tripartition generation. When *normalize* is True the result is divided by |T(N1) | T(N2)|, yielding a value in [0, 1]. Reference --------- Moret *et al.*; Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Return a value in [0, 1] instead of a raw count. |
Tree-based distance between two phylogenetic networks. Each network's set of unique displayed-tree topologies (identified by cluster representation) is computed. The distance is the cardinality of the symmetric difference: d_DT(N1, N2) = |DT(N1) triangle DT(N2)| .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. When *normalize* is True the result is divided by |DT(N1) | DT(N2)|, yielding a value in [0, 1].
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Return a value in [0, 1] instead of a raw count. |
Robinson--Foulds distance between two phylogenetic trees or networks. For rooted trees the RF distance equals the cardinality of the symmetric difference of the non-trivial cluster sets (clusters of size >= 2 and < n, where n is the number of leaves). For networks the function uses hardwired clusters, which is the natural generalization of RF to DAGs. Both inputs must share the same leaf label set. When *normalize* is True the result is divided by |C(N1)| + |C(N2)| (the maximum possible RF for the given cluster counts), yielding a value in [0, 1]. Reference --------- Robinson & Foulds. *Comparison of Phylogenetic Trees*. Mathematical Biosciences **53** (1981), 131--147. Cardona, Llabres, Rossello & Valiente. *Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric*. IEEE/ACM Trans. Comput. Biol. Bioinformatics **6** (2009), 46--61.
| Parameter | Type | Description |
|---|---|---|
| net1 | First tree / network. | |
| net2 | Second tree / network. | |
| normalize | Return a value in [0, 1] instead of a raw count. |
NetworkError: If the two inputs have different leaf label sets.Average Path Distance (APD) between two phylogenetic networks. For each network a pairwise leaf distance matrix is computed by averaging the path lengths across all displayed trees (uniform weighting). The APD is the L1 norm of the difference between the two matrices: APD(N1, N2) = sum_{i<j} |D_N1(l_i,l_j) - D_N2(l_i,l_j)| When *normalize* is True the sum is divided by the number of leaf pairs C(n, 2). Branch lengths on every edge are required. .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. Reference --------- Yakici, Ogilvie & Nakhleh. *Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into Account*. RECOMB-CG 2022, LNCS 13234, pp. 86--102.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Divide by C(n, 2) to get a per-pair average. |
NetworkError: If the two networks have different leaf label sets.Weighted Average Path Distance (WAPD) between two networks. Identical to :func:`average_path_distance` except that the average over displayed trees is weighted by each tree's probability (the product of the gamma values of the kept reticulation edges). WAPD(N1, N2) = sum_{i<j} |WD_N1(l_i,l_j) - WD_N2(l_i,l_j)| When *normalize* is True the sum is divided by the number of leaf pairs C(n, 2). Branch lengths and gamma values on every reticulation edge are required. .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. Reference --------- Yakici, Ogilvie & Nakhleh. *Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into Account*. RECOMB-CG 2022, LNCS 13234, pp. 86--102.
| Parameter | Type | Description |
|---|---|---|
| net1 | First network. | |
| net2 | Second network. | |
| normalize | Divide by C(n, 2) to get a per-pair average. |
NetworkError: If the two networks have different leaf label sets.Prints out an ascii art depiction of this Network object as a vertical tree/network with the root at the top and leaves at the bottom.
| Parameter | Type | Description |
|---|---|---|
| net | Network | A Network |
| show_edge_lengths | bool | If True, display edge lengths. Defaults to False. |