Directed Network (Advanced Features)#

The phylozoo.core.network.dnetwork module provides advanced features, transformations, and analysis capabilities for DirectedPhyNetwork. This page covers network features, classifications, transformations, derivations, and isomorphism checking. For the DirectedPhyNetwork class and its properties, see Directed Network Class.

Structural Features#

The features module provides functions to extract advanced structural properties of directed networks. These include LSA (Least Stable Ancestor) nodes, blobs (maximal biconnected components), omnian nodes, and cut edges/vertices that characterize network topology.

LSA Node

The lsa_node() function finds the Least Stable Ancestor node, which is the lowest node through which all root-to-leaf paths pass. The LSA is a fundamental concept in phylogenetic network analysis, representing the most recent common ancestor of all leaves. For convenience, this function is also available as the cached LSA_node property on the DirectedPhyNetwork class.

from phylozoo.core.network.dnetwork import features

# Find LSA (Least Stable Ancestor) node
lsa = features.lsa_node(network)

Blobs

The blobs() function extracts all blobs (maximal biconnected components) in the network, represented by sets of nodes. Blobs represent the reticulate structure of the network, where cycles and hybrid nodes create biconnected regions. The function can optionally exclude trivial (single-node) blobs and/or blobs that contain only leaves.

# Get all blobs (including trivial and leaf blobs)
all_blobs = features.blobs(network)

# Get only non-trivial blobs (excluding single-node blobs)
non_trivial_blobs = features.blobs(network, trivial=False)

# Get blobs excluding leaf-only blobs
internal_blobs = features.blobs(network, leaves=False)

k-Blobs

The k_blobs() function gets blobs with exactly \(k\) incident edges, represented by sets of nodes. An incident edge is any edge that connects a node inside the blob to a node outside the blob.

# Get 2-blobs (blobs with exactly 2 incident edges)
k2_blobs = features.k_blobs(network, k=2)

Omnians

The omnians() function finds omnian nodes, which are nodes with every child being a hybrid node [Jetten and van Iersel, 2016].

# Find omnians (nodes that are ancestors of all leaves)
omnians_set = features.omnians(network)

Cut Edges and Vertices

The cut_edges() and cut_vertices() functions identify edges and vertices whose removal disconnects the network. These are important for understanding network connectivity and decomposition.

# Get cut edges and cut vertices
cut_edges = features.cut_edges(network)
cut_vertices = features.cut_vertices(network)

Classifications#

The classifications module provides functions to determine various mathematical and phylogenetic properties of networks. These include level (number of reticulations), network types (LSA, galled, tree-child, tree-based, normal), and structural properties like binary resolution and ultrametricity.

Basic Network Properties#

Phylogenetic Trees

The is_tree() function checks if the network is a rooted phylogenetic tree (no hybrid nodes). For convenience, this function is also available as a class method on the DirectedPhyNetwork class:

# Check if network is a tree
is_tree = network.is_tree()
# or
is_tree = classifications.is_tree(network)

Binary Networks

The is_binary() function checks if the network is binary (all internal nodes have degree 3, except for the root node which must have degree 2).

# Check if network is binary
is_binary = classifications.is_binary(network)

Simple Networks

The is_simple() function checks if the network is simple: containing exactly one non-leaf blob.

# Check if network is simple
is_simple = classifications.is_simple(network)

LSA Networks

The is_lsa_network() function checks if the network is an LSA network, meaning the root equals the LSA node. This is a desirable property for many network analyses.

# Check if network is LSA network
is_lsa = classifications.is_lsa_network(network)

Parallel Edges

The has_parallel_edges() function checks if the network contains parallel edges (multiple edges between the same pair of nodes).

# Check for parallel edges
has_parallel = classifications.has_parallel_edges(network)

Network Classes#

Reticulation Number

The reticulation_number() function calculates the reticulation number, which is the total number of hybrid edges minus the total number of hybrid nodes.

# Calculate reticulation number
reticulation_number = classifications.reticulation_number(network)

Level and Vertex Level

The level() and vertex_level() functions calculate the level and vertex level of the network, respectively.

The level is the maximum over all blobs of (number of hybrid edges minus number of hybrid nodes) in that blob. The vertex level is the maximum over all blobs of the number of hybrid nodes in that blob. Note that the vertex level is always less than or equal to the level and they coincide for binary networks.

# Calculate level and vertex level
level = classifications.level(network)
vertex_level = classifications.vertex_level(network)

Stack-Free Networks

The is_stackfree() function checks if the network is stack-free, meaning no two hybrid nodes share a common parent.

# Check if network is stack-free
is_stackfree = classifications.is_stackfree(network)

Tree-Child Networks

The is_treechild() function checks if the network is tree-child, meaning each internal node has at least one tree child. This property ensures that the network has a tree-like structure.

# Check if network is tree-child
is_treechild = classifications.is_treechild(network)

Tree-Based Networks

The is_treebased() function checks if the network is tree-based.

# Check if network is tree-based
is_treebased = classifications.is_treebased(network)

Galled Networks

The is_galled() function checks if the network is galled, meaning each reticulation is in its own cycle. Galled networks have special properties that make them easier to analyze.

# Check if network is galled
is_galled = classifications.is_galled(network)

Normal Networks

The is_normal() function checks if the network is normal, meaning it is tree-child without shortcuts. Normal networks have additional structural constraints.

# Check if network is normal
is_normal = classifications.is_normal(network)

Ultrametric Networks

The is_ultrametric() function checks if all root-to-leaf distances are equal, using the branch lengths of the edges.

# Check if network is ultrametric
is_ultrametric = classifications.is_ultrametric(network)

Transformations#

The transformations module provides functions to modify network structures. These include converting to LSA form, binary resolution of high-degree nodes, identifying parallel edges, and suppressing 2-blobs.

LSA Network Conversion

The to_lsa_network() function converts a network to LSA form by removing all nodes above the LSA.

from phylozoo.core.network.dnetwork import transformations

# Convert to LSA network
lsa_net = transformations.to_lsa_network(network)

Parallel Edge Identification

The identify_parallel_edges() function identifies parallel edges by replacing all parallel edges between the same pair of nodes with a single edge, and suppressing all resulting degree-2 nodes.

# Identify parallel edges
identified_net = transformations.identify_parallel_edges(network)

Suppressing 2-Blobs

The suppress_2_blobs() function suppresses all 2-blobs and the resulting degree-2 nodes.

# Suppress 2-blobs
simplified = transformations.suppress_2_blobs(network)

Binary Resolution

The binary_resolution() function resolves high-degree nodes to binary form using caterpillar structures, preserving gamma values and branch lengths. This transformation is useful for algorithms that require binary networks.

# Binary resolution (resolve high-degree nodes)
binary_net = transformations.binary_resolution(network)

Derivations#

The derivations module provides functions to extract derived structures from networks, including conversion to semi-directed networks, tree-of-blobs, subnetworks for specific taxa sets, displayed trees, and induced splits and quartets.

Phylogenetic Trees#

Tree-of-Blobs

The tree_of_blobs() function extracts the tree structure of blobs, representing the high-level topology of the network. This simplifies the network by collapsing each blob into a single node.

# Extract tree of blobs
tob = derivations.tree_of_blobs(network)

Displayed Trees

The displayed_trees() function generates all displayed trees (trees embedded in the network). A displayed tree is obtained by taking a switching (deleting all but one parent edge per hybrid node), then removing degree-1 nodes and suppressing degree-2 nodes. Optionally the probability of each displayed tree is stored in the network’s ‘probability’ attribute.

# Get displayed trees without probabilities
for tree in derivations.displayed_trees(network):
    # Process each displayed tree
    pass

# Get displayed trees with probabilities
for tree in derivations.displayed_trees(network, probability=True):
    prob = tree.get_network_attribute('probability')
    print(f"Tree probability: {prob}")

Phylogenetic Networks#

Subnetworks

The subnetwork() function extracts a subnetwork induced by a specific set of taxa. The subnetwork is defined as the union of all directed paths from the requested leaves up to the root (i.e., all their ancestors and the leaves themselves). The induced subgraph is taken, then degree-2 internal nodes are suppressed.

The function has three post-processing options: it can suppress 2-blobs, identify/merge parallel edges, and/or convert the result to an LSA-network (with the LSA as root).

# Get basic subnetwork
subnetwork = derivations.subnetwork(network, taxa=["A", "B", "C"])

k-Taxon Subnetworks

The k_taxon_subnetworks() function generates all subnetworks induced by exactly k taxa. For each combination of k taxa, the corresponding subnetwork is computed using the subnetwork function.

# Get all 4-taxon subnetworks
k_subnets = derivations.k_taxon_subnetworks(network, k=4)

Conversion to Semi-Directed Network

The to_sd_network() function converts a directed network to a SemiDirectedPhyNetwork by undirecting non-hybrid edges and suppressing the root node.

from phylozoo.core.network.dnetwork import derivations

# Convert to semi-directed network
sd_net = derivations.to_sd_network(network)

Pairwise Distances#

The distances() function computes pairwise distances between taxa. The function can compute shortest, longest, or probability-weighted average distances across all displayed trees of the network. This returns a DistanceMatrix object.

# Compute distance matrix with average distances
from phylozoo.core.network.dnetwork.derivations import distances
distance_matrix = distances(network, mode='average')  # or 'shortest', 'longest'

Partitions and Splits#

Partition from Blob

The partition_from_blob() function extracts the partition of taxa induced by removing a specific blob from the network.

# Extract partition from specific blob
from phylozoo.core.network.dnetwork.features import blobs
blob = list(blobs(network))[0]
partition = derivations.partition_from_blob(network, blob)

Split from Cut-Edge

The split_from_cutedge() function extracts the split induced by a specific cut edge. The split is the 2-partition of taxa obtained when removing the edge from the network.

# Extract split from specific cut edge
from phylozoo.core.network.dnetwork.features import cut_edges
cut_edge = list(cut_edges(network))[0]
split = derivations.split_from_cutedge(network, cut_edge)

Induced Splits

The induced_splits() function extracts all splits induced by cut-edges of the network. This returns a SplitSystem object.

# Extract induced splits
splits = derivations.induced_splits(network)

Displayed Splits

The displayed_splits() function extracts all splits induced by all displayed trees, weighted by their probabilities. This returns a WeightedSplitSystem object.

# Extract displayed splits
displayed_splits = derivations.displayed_splits(network)

Quartets#

The displayed_quartets() function extracts quartet profiles from displayed trees. This returns a QuartetProfileSet object.

# Extract displayed quartets
quartets = derivations.displayed_quartets(network)

Isomorphism Checking#

The isomorphism module provides functions to check if two networks have the same topological structure.

The is_isomorphic() function checks if two networks are isomorphic. Labels are always checked, and additional attributes can be specified for comparison.

from phylozoo.core.network.dnetwork import isomorphism

# Check isomorphism (labels are always checked)
are_isomorphic = isomorphism.is_isomorphic(net1, net2)

# Check with additional attributes
are_isomorphic = isomorphism.is_isomorphic(
    net1, net2,
    node_attrs=["custom_attr"],
    edge_attrs=["branch_length"]
)