graph_utilities.py

High-level description

This code defines functions for constructing and manipulating graphs used in phylogenetic tree reconstruction. It includes functions for building connectivity graphs based on shared mutations, similarity graphs based on a given similarity function, and optimizing graph partitions using hill-climbing procedures.

Code Structure

The code consists of several functions that are used to construct and manipulate graphs for phylogenetic tree reconstruction. The construct_connectivity_graph and construct_similarity_graph functions are used to build different types of graphs, while max_cut_improve_cut and spectral_improve_cut are used to optimize partitions on these graphs. The check_if_cut function is a utility function used by the optimization functions.

References

This code references the solver_utilities module for converting sample names to indices.

Symbols

check_if_cut

Description

This function checks if two nodes are on opposite sides of a graph partition.

Inputs

Name	Type	Description
u	int	The index of the first node.
v	int	The index of the second node.
cut	List[int]	A list of node indices representing one side of the partition.

Outputs

Name	Type	Description
	bool	True if nodes u and v are on opposite sides of the partition, False otherwise.

Internal Logic

The function simply checks if one node is in the cut list and the other is not.

construct_connectivity_graph

Description

This function constructs a connectivity graph for a set of samples based on their observed mutations. The edge weights represent the tendency of two samples to be grouped together or separated based on their shared and differing mutations.

Inputs

Name	Type	Description
character_matrix	pd.DataFrame	The character matrix of observed character states for all samples.
mutation_frequencies	Dict[int, Dict[int, int]]	A dictionary containing the frequencies of each character/state pair.
missing_state_indicator	int	The character representing missing values.
samples	List[str]	A list of sample names to include in the graph.
weights	Optional[Dict[int, Dict[int, float]]]	Optional weights for character/state pairs.

Outputs

Name	Type	Description
G_names	nx.Graph	The constructed connectivity graph with sample names as nodes.

Internal Logic

The function iterates through all pairs of samples and calculates a score based on their shared and differing mutations. The score is positive if the samples share mutations and negative if they have different mutations. The absolute value of the score is higher for mutations that are less frequent in the dataset. The scores are then used as edge weights in the graph.

max_cut_improve_cut

Description

This function implements a greedy hill-climbing procedure to optimize a partition for the max-cut criterion on a graph.

Inputs

Name	Type	Description
G	nx.Graph	The graph to optimize the partition on.
cut	List[str]	A list of nodes representing one side of the initial partition.

Outputs

Name	Type	Description
new_cut	List[str]	A new partition that is a local maximum to the max-cut criterion.

Internal Logic

The function iteratively moves nodes between the two sides of the partition, choosing the move that maximizes the weight of edges across the cut. The procedure terminates when no further improvement can be made or a maximum number of iterations is reached.

construct_similarity_graph

Description

This function constructs a similarity graph for a set of samples based on a given similarity function.

Inputs

Name	Type	Description
character_matrix	pd.DataFrame	The character matrix of observed character states for all samples.
missing_state_indicator	int	The character representing missing values.
samples	List[str]	A list of sample names to include in the graph.
similarity_function	Callable	A function that calculates a similarity score between two samples.
threshold	int	A minimum similarity threshold to include an edge in the graph.
weights	Optional[Dict[int, Dict[int, float]]]	Optional weights for character/state pairs.

Outputs

Name	Type	Description
G_names	nx.Graph	The constructed similarity graph with sample names as nodes.

Internal Logic

The function iterates through all pairs of samples and calculates their similarity using the provided similarity_function. If the similarity score is above the given threshold, an edge is added between the corresponding nodes in the graph with the weight equal to the similarity score.

spectral_improve_cut

Description

This function implements a greedy hill-climbing procedure to optimize a partition for a modified normalized cut criterion on a graph.

Inputs

Name	Type	Description
G	nx.Graph	The graph to optimize the partition on.
cut	List[str]	A list of nodes representing one side of the initial partition.

Outputs

Name	Type	Description
new_cut	List[str]	A new partition that is a local minimum to the objective function.

Internal Logic

The function iteratively moves nodes between the two sides of the partition, choosing the move that minimizes the ratio of the weight of edges across the cut to the minimum of the sum of edge weights within each side of the cut. The procedure terminates when no further improvement can be made or a maximum number of iterations is reached.