MaxCutGreedySolver.py

​

High-level description

The MaxCutGreedySolver class, inheriting from GreedySolver, implements a phylogenetic tree reconstruction algorithm that combines a greedy approach with a max-cut optimization. It recursively partitions samples based on the most frequent mutation and then refines the split using a hill-climbing method to maximize the weight of edges cut in a connectivity graph built from shared mutations.

​

Code Structure

The MaxCutGreedySolver class overrides the perform_split method of its parent class, GreedySolver. It leverages the compute_mutation_frequencies method from the parent class and utilizes functions like construct_connectivity_graph and max_cut_improve_cut from the graph_utilities module.

​

References

This code references the following symbols from other files:

• GreedySolver (from cassiopeia/solver/GreedySolver.py)
• missing_data_methods (from cassiopeia/solver/missing_data_methods.py)
• solver_utilities (from cassiopeia/solver/solver_utilities.py)
• graph_utilities (from cassiopeia/solver/graph_utilities.py)

​

Symbols

​

MaxCutGreedySolver

​

Description

This class implements the MaxCut Greedy algorithm for phylogenetic tree reconstruction. It extends the basic GreedySolver by adding a max-cut optimization step to each split.

​

Inputs

Name	Type	Description
missing_data_classifier	Callable	Function to handle missing data during character splits (default: missing_data_methods.assign_missing_average).
prior_transformation	str	Transformation function for converting priors to weights (default: "negative_log").

​

Outputs

This class doesn’t directly return any output. It populates a CassiopeiaTree object during the solve method (inherited from GreedySolver).

​

Internal Logic

The core logic resides in the perform_split method:

1. Identify Splitting Character/State: It identifies the most frequent character/state pair, considering potential weights derived from priors.
2. Initial Split: Samples are initially partitioned based on the chosen character/state.
3. Handle Missing Data: The missing_data_classifier function is used to assign samples with missing data to either side of the partition.
4. Construct Connectivity Graph: A connectivity graph is built where nodes represent samples and edge weights reflect the similarity based on shared mutations.
5. Max-Cut Optimization: The max_cut_improve_cut function refines the initial split by iteratively moving nodes between partitions to maximize the weight of edges cut, effectively grouping samples with similar mutations.
6. Return Refined Split: The optimized left and right partitions are returned.

​

perform_split

​

Description

This method partitions a set of samples based on the most frequent mutation and optimizes the split using the max-cut criterion.

​

Inputs

Name	Type	Description
character_matrix	pd.DataFrame	Character matrix containing character states for each sample.
samples	List[int]	List of samples to be partitioned.
weights	Optional[Dict[int, Dict[int, float]]]	Weights for each (character, state) pair, usually derived from priors.
missing_state_indicator	int	Character representing missing data (default: -1).

​

Outputs

Name	Type	Description
improved_left_set	List[str]	List of samples in the left partition after optimization.
improved_right_set	List[str]	List of samples in the right partition after optimization.

​

Internal Logic

See the ‘Internal Logic’ section of the MaxCutGreedySolver class description.

​

Side Effects

The perform_split method modifies the input left_set and right_set lists in-place during the missing data imputation and max-cut optimization steps.

​

Dependencies

This code depends on the following external libraries:

Dependency	Purpose
pandas	Handling and manipulating character matrices.
networkx	Constructing and manipulating graphs for representing relationships between samples.
numpy	Numerical operations, particularly in calculating scores and frequencies.

​

Error Handling

This code does not implement specific error handling beyond what is inherited from the parent class GreedySolver.