Internal Algorithm Steps

The individual algorithm components that make up the Squirrel pipeline. These are exposed at the top level of physquirrel and can be used independently for custom workflows.

T* tree and B* splits

physquirrel.algorithms.tstar_tree.bstar(profileset: QuartetProfileSet) → SplitSystem

Compute the B*-set of compatible splits from quartet profiles.

Uses the incremental O(n^5) algorithm from Berry & Gascuel (2000). Only considers trivial (single-quartet), resolved profiles.

Parameters:

profileset (QuartetProfileSet)

Return type:

SplitSystem

physquirrel.algorithms.tstar_tree.tstar_tree(profileset: QuartetProfileSet) → SemiDirectedPhyNetwork

Compute the T* tree from a quartet profile set.

Builds the B*-set of splits then converts to a SemiDirectedPhyNetwork tree.

Parameters:

profileset (QuartetProfileSet)

Return type:

SemiDirectedPhyNetwork

Quartet joining

physquirrel.algorithms.qjoining.adapted_quartet_joining(profileset: QuartetProfileSet, starting_tree: SemiDirectedPhyNetwork) → SemiDirectedPhyNetwork

Adapted quartet joining algorithm starting from an arbitrary tree.

Iteratively refines the tree by joining the best-scoring neighbor pair at each high-degree internal node until the tree is binary.

Parameters:

• profileset (QuartetProfileSet)

• starting_tree (SemiDirectedPhyNetwork)

Return type:

SemiDirectedPhyNetwork

physquirrel.algorithms.qjoining.quartet_joining(profileset: QuartetProfileSet) → SemiDirectedPhyNetwork

Quartet joining algorithm starting from a star tree.

Constructs an initial star tree (all taxa connected to a single center node) and refines it using adapted_quartet_joining.

Parameters:

profileset (QuartetProfileSet)

Return type:

SemiDirectedPhyNetwork

Unresolve tree and split support

physquirrel.algorithms.unresolve_tree.split_support(profileset: QuartetProfileSet, split: Split) → float

Compute quartet support for a split A|B.

All profiles (split and cycle) contribute their profile weight to the denominator. Only trivial (split) profiles whose split agrees with A|B contribute to the numerator. Cycle profiles act as evidence against the split by increasing the denominator only.

Parameters:

• profileset (QuartetProfileSet)

• split (Split)

Return type:

float in [0, 1], or 0.0 if no profiles found.

physquirrel.algorithms.unresolve_tree.unresolve_tree(tree: SemiDirectedPhyNetwork, profileset: QuartetProfileSet) → Iterator[SemiDirectedPhyNetwork]

Yield a sequence of trees by iteratively contracting least-supported splits.

Computes split support for all non-trivial splits once, sorts them by support (lowest first), and contracts them one at a time. Yields after each contraction, starting with the original tree.

Parameters:

• tree (SemiDirectedPhyNetwork)

• profileset (QuartetProfileSet)

Yields:

SemiDirectedPhyNetwork

Cycle resolution

physquirrel.algorithms.cycle_resolution.resolve_cycles(profileset: SqQuartetProfileSet, tree: SemiDirectedPhyNetwork, outgroup: str | None = None, rho: tuple[float, float, float, float] = (0.5, 1.0, 0.5, 1.0), tsp_threshold: int | None = 13, weighted_distance: bool = True, representative_mode: Literal['average', 'best'] = 'best') → SemiDirectedPhyNetwork

Convert a tree to a level-1 network by replacing high-degree vertices with cycles.

For each internal vertex with degree > 3 (processed highest-degree first): 1. Compute the partition induced by that vertex. 2. Solve TSP to get the circular set ordering. 3. Get hybrid ranking from quartet profiles. 4. Insert a directed cycle with the best hybrid configuration.

Parameters:

• profileset (SqQuartetProfileSet)

• tree (SemiDirectedPhyNetwork)

• outgroup (str | None)

• rho (tuple of 4 floats)

• tsp_threshold (int | None) – Max partition size for optimal TSP; larger uses simulated annealing.

• weighted_distance (bool) – If True, profile weights are used to scale TSP distance contributions so that high-confidence profiles pull the circular ordering more than low-confidence ones. Default: False.

• representative_mode ({'average', 'best'}) –

  Controls how profiles within each 4-subpartition are aggregated when building the TSP distance matrix.

  • 'average' (default): average rho-distance over all representative leaf-partitions. Reflects the full distribution of quartet signals.

  • 'best': vote (weighted) for the plurality topology per 4-subpartition and use only that topology’s contributions. Mirrors the v1 behaviour of electing a single representative quarnet per 4-tuple of partition sets.

Return type:

SemiDirectedPhyNetwork

Profile similarity and scoring

physquirrel.algorithms.qsimilarity.sqprofileset_from_network(network: SemiDirectedPhyNetwork) → SqQuartetProfileSet

Compute the SqQuartetProfileSet displayed by a semi-directed level-1 network.

Requires the network to be binary, level-1, and parallel-edge-free.

Parameters:

network (SemiDirectedPhyNetwork)

Return type:

SqQuartetProfileSet

physquirrel.algorithms.qsimilarity.sqprofileset_similarity(profileset1: SqQuartetProfileSet, profileset2: SqQuartetProfileSet, weighted: bool = True) → float

Compute the C-measure (consistency) between two SqQuartetProfileSets.

Two profiles are consistent if they have the same quartets and reticulation_leaf.

Parameters:

• profileset1 (SqQuartetProfileSet)

• profileset2 (SqQuartetProfileSet)

• weighted (bool) – Use profile weights. Default True.

Return type:

float in [0, 1]. Returns 1.0 if profileset1 is empty.

Quartet distance

Quartet distance module.

Provides functions for computing distance matrices from quartet profiles using quartet distance metrics.

physquirrel.algorithms.qdistance.quartet_distance_with_partition(profileset: QuartetProfileSet, partition: Partition, rho: tuple[float, float, float, float] = (0.5, 1.0, 0.5, 1.0), weighted_distance: bool = True, representative_mode: Literal['average', 'best'] = 'best') → DistanceMatrix

Compute a distance matrix between partition sets based on quartet profiles.

For each 4-subpartition of the partition, considers all quartets with one leaf from each set and aggregates their rho-distance contributions. The result is a k×k distance matrix over the k partition sets (TSP input for cycle resolution).

Parameters:

• profileset (QuartetProfileSet) – Must be dense (a profile for every 4-taxon combination).

• partition (Partition) – A partition of the taxa. Distance is computed between the sets.

• rho (tuple[float, float, float, float]) –

  (rho_c, rho_s, rho_a, rho_o) — distance contributions for different quartet topologies. Must satisfy rho_c ≤ rho_s and rho_a ≤ rho_o. Default: (0.5, 1.0, 0.5, 1.0).

  For a split profile (1 quartet), the distance between two leaves is:

  • rho_c — same side of the split

  • rho_s — opposite sides of the split

  For a cycle profile (2 quartets), the distance between two leaves is:

  • rho_a — adjacent in the circular ordering

  • rho_o — opposite in the circular ordering

• weighted_distance (bool) – If True, each profile’s rho-distance contribution is scaled by its profile weight before averaging. High-confidence profiles then pull the distance more than low-confidence ones, mirroring the Kalmanson weighting used in physquirrel v1. Default: False.

• representative_mode ({'average', 'best'}) –

  How profiles within each 4-subpartition are aggregated:

  • 'average' (default): average rho-distance contributions over all representative leaf-partitions (one leaf from each set), then shrink the per-pair mean toward 1.5 by 1 - confidence where confidence is the weight fraction on the most-supported delta value for that pair. Reflects the full empirical distribution of quartet signals while still down-weighting ambiguous pairs (Kalmanson-style shrink, but over all contributing quarnets rather than a single elected representative).

  • 'best': first vote (weighted by profile weight) across all representative leaf-partitions to determine the plurality topology (most common split direction or cycle orientation). Then average contributions from only the profiles that match the winning topology. This mirrors the v1 behaviour of building a single representative quarnet per 4-tuple of partition sets via a plurality vote.

Returns:

k×k symmetric matrix with zero diagonal. Labels are the partition sets (frozensets).

Return type:

DistanceMatrix

Raises:

PhyloZooValueError – If rho constraints are violated, partition elements don’t match profileset taxa, or profileset is not dense.