DistanceSolver.py

​

High-level description

The DistanceSolver class is a base class for distance-based phylogenetic tree solvers in Cassiopeia. It provides a general framework for solving trees using a dissimilarity map, iteratively joining samples into cherries and updating the map. Subclasses like NeighborJoiningSolver and UPGMASolver implement specific cherry-finding and map-updating logic.

​

Code Structure

The DistanceSolver class defines the general structure and common methods for distance-based solvers. It relies on abstract methods like find_cherry and update_dissimilarity_map to be implemented by subclasses. The solve method orchestrates the tree-solving process, while helper methods like get_dissimilarity_map and setup_dissimilarity_map manage the dissimilarity matrix.

​

References

• CassiopeiaSolver: The parent class defining the general solver interface.
• solver_utilities: Provides utility functions for tree manipulation and data handling.
• dissimilarity_functions: Offers various dissimilarity functions for comparing samples.

​

Symbols

​

DistanceSolver

​

Description

This class provides a general framework for distance-based phylogenetic tree solvers. It defines the overall structure and common methods, leaving the specific cherry-finding and dissimilarity map updating logic to be implemented by subclasses.

​

Inputs

Name	Type	Description
dissimilarity_function	Optional[Callable[[np.array, np.array, int, Dict[int, Dict[int, float]]], float]]	Function to compute dissimilarity between samples.
add_root	bool	Whether to add an implicit root to the tree (default: False).
prior_transformation	str	Function to transform priors into weights (default: “negative_log”).
threads	int	Number of threads to use for solver (default: 1).

​

Outputs

None

​

Internal Logic

The solve method orchestrates the tree-solving process:

1. Setup: Initializes the dissimilarity map and creates a basic tree with all samples as leaves.
2. Iteration: Iteratively finds cherries, joins them in the tree, and updates the dissimilarity map until only two nodes remain.
3. Rooting: Roots the tree using the specified or implicit root.
4. Population: Populates the CassiopeiaTree with the solved tree topology.

​

get_dissimilarity_map

​

Description

Obtains or generates the dissimilarity map used throughout the solver. This method can be overridden by subclasses to use other types of sample comparison maps.

​

Inputs

Name	Type	Description
cassiopeia_tree	CassiopeiaTree	The tree object to obtain the dissimilarity map from.
layer	Optional[str]	Layer storing the character matrix for solving (default: None).

​

Outputs

Name	Type	Description
dissimilarity_map	pd.DataFrame	The dissimilarity matrix used for solving.

​

solve

​

Description

Solves the phylogenetic tree using the distance-based approach. It iteratively finds cherries, joins them, and updates the dissimilarity map.

​

Inputs

Name	Type	Description
cassiopeia_tree	CassiopeiaTree	The CassiopeiaTree object to populate with the solved tree.
layer	Optional[str]	Layer storing the character matrix for solving (default: None).
collapse_mutationless_edges	bool	Whether to collapse mutationless edges in the final tree (default: False).
logfile	str	File location to log output (default: “stdout.log”).

​

Outputs

None

​

Internal Logic

1. Initialization: Obtains the dissimilarity map and creates a basic tree with all samples as leaves.
2. Cherry Finding: Iteratively calls the subclass-specific find_cherry method to identify a pair of samples to join.
3. Joining and Updating: Joins the identified cherry in the tree and updates the dissimilarity map using the subclass-specific update_dissimilarity_map method.
4. Rooting: Roots the tree using the root_tree method, which is also implemented by subclasses.
5. Population: Populates the input CassiopeiaTree with the solved tree topology.

​

_ccphylo_solve

​

Description

Solves the tree using fast distance-based algorithms implemented by CCPhylo. Requires CCPhylo to be installed and configured.

​

Inputs

Name	Type	Description
cassiopeia_tree	CassiopeiaTree	The CassiopeiaTree object to populate with the solved tree.
layer	Optional[str]	Layer storing the character matrix for solving (default: None).
collapse_mutationless_edges	bool	Whether to collapse mutationless edges in the final tree (default: False).
logfile	str	File location to log output (default: “stdout.log”).
method	str	The CCPhylo algorithm to use (default: “dnj”).

​

Outputs

None

​

Internal Logic

1. Preparation: Saves the dissimilarity map as a phylip file.
2. CCPhylo Execution: Runs the specified CCPhylo algorithm using the saved dissimilarity map.
3. Conversion and Rooting: Converts the resulting tree to a NetworkX graph and roots it using root_tree.
4. Population: Populates the input CassiopeiaTree with the solved tree topology.

​

_setup_ccphylo

​

Description

Sets up the CCPhylo solver by retrieving the path from the configuration file and validating it.

​

Inputs

None

​

Outputs

None

​

Internal Logic

1. Path Retrieval: Reads the ccphylo_path from the configuration file.
2. Validation: Checks if the path exists and is executable. Raises a DistanceSolverError if not.

​

setup_dissimilarity_map

​

Description

Sets up the solver by creating the dissimilarity map if needed and setting up the root sample.

​

Inputs

Name	Type	Description
cassiopeia_tree	CassiopeiaTree	The CassiopeiaTree object to set up the dissimilarity map for.
layer	Optional[str]	Layer storing the character matrix for solving (default: None).

​

Outputs

None

​

Internal Logic

1. Root Handling: If no root sample is specified, either sets up an implicit root or raises a DistanceSolverError.
2. Dissimilarity Map Creation: If the dissimilarity map is not present, computes it using the provided dissimilarity_function or raises a DistanceSolverError.

​

root_tree

​

Description

(Abstract method) Roots the tree at the specified root sample.

​

Inputs

Name	Type	Description
tree	nx.Graph	The unrooted tree topology.
root_sample	str	The sample to treat as the root.
remaining_samples	List[str]	The last two unjoined nodes in the tree.

​

Outputs

Name	Type	Description
rooted_tree	nx.DiGraph	The rooted tree.

​

find_cherry

​

Description

(Abstract method) Selects two samples to join together as a cherry.

​

Inputs

Name	Type	Description
dissimilarity_map	np.array(float)	The dissimilarity map relating samples.

​

Outputs

Name	Type	Description
cherry	Tuple[int, int]	A tuple of sample indices to join.

​

update_dissimilarity_map

​

Description

(Abstract method) Updates the dissimilarity map after joining a cherry.

​

Inputs

Name	Type	Description
dissimilarity_map	pd.DataFrame	The dissimilarity map to update.
cherry	Tuple[str, str]	The joined cherry nodes.
new_node	str	The new node name to add to the map.

​

Outputs

Name	Type	Description
updated_map	pd.DataFrame	The updated dissimilarity map.

​

setup_root_finder

​

Description

(Abstract method) Defines how an implicit root is to be added to the tree.

​

Inputs

Name	Type	Description
cassiopeia_tree	CassiopeiaTree	The CassiopeiaTree object to set up the root for.

​

Outputs

None

​

Side Effects

The solve method modifies the input CassiopeiaTree object by populating its tree attribute with the solved tree topology.

​

Dependencies

• ete3: Used for tree manipulation and visualization.
• networkx: Used for graph representation and algorithms.
• numpy: Used for numerical operations.
• pandas: Used for data manipulation and representation.
• configparser: Used for reading configuration files.
• subprocess: Used for running external commands (CCPhylo).

​

Configuration

The _ccphylo_solve method relies on the ccphylo_path option defined in the configuration file to locate the CCPhylo executable.