> ## Documentation Index > Fetch the complete documentation index at: https://demo.agenticlabs.com/llms.txt > Use this file to discover all available pages before exploring further. # PercolationSolver.py ## High-level description The `PercolationSolver` class implements a top-down, percolation-based algorithm for reconstructing phylogenetic trees. It recursively partitions a set of samples based on their similarity in observed mutations, creating a tree structure where similar samples are grouped closer together. ## Code Structure The `PercolationSolver` class is initialized with a joining solver, prior transformation function, similarity function, and a threshold. The `solve` method orchestrates the tree reconstruction process by recursively partitioning the sample set using the `percolate` method. The `percolate` method constructs a similarity graph, removes edges based on similarity, and partitions the graph into clades. If more than two clades are formed, the `joining_solver` is used to cluster them. Finally, the `__add_duplicates_to_tree` method adds duplicate samples to the tree. ## References This code references the following symbols: * `CassiopeiaSolver` (from `cassiopeia.solver`) * `dissimilarity_functions` (from `cassiopeia.solver`) * `solver_utilities` (from `cassiopeia.solver`) * `CassiopeiaTree` (from `cassiopeia.data`) * `data_utilities` (from `cassiopeia.data.utilities`) ## Symbols ### `PercolationSolver` #### Description This class implements the Percolation algorithm for phylogenetic tree reconstruction. It takes a character matrix and optional priors as input and builds a tree by recursively partitioning the sample set based on their similarity in observed mutations. #### Inputs | Name | Type | Description | | :-------------------- | :------------------------------------------------------------------------------------------------ | :--------------------------------------------------------------------------------------------------------------------- | | joining\_solver | CassiopeiaSolver.CassiopeiaSolver | The CassiopeiaSolver used to cluster groups of samples if percolation produces more than two groups. | | prior\_transformation | str | A string specifying the transformation to apply to the priors. Defaults to "negative\_log". | | similarity\_function | Optional\[Callable\[\[np.array, np.array, int, Optional\[Dict\[int, Dict\[int, float]]]], float]] | A function that calculates the similarity score between two samples. Defaults to `hamming_similarity_without_missing`. | | threshold | Optional\[int] | The minimum similarity threshold for adding an edge in the similarity graph. Defaults to 0. | #### Outputs This class doesn't directly return any output. It modifies the input `CassiopeiaTree` object to store the reconstructed tree. #### Internal Logic 1. **Initialization:** The class is initialized with a joining solver, prior transformation function, similarity function, and a threshold. 2. **Solve:** The `solve` method orchestrates the tree reconstruction process. * It first extracts the character matrix and transforms the priors into weights if provided. * It then creates a NetworkX graph and recursively partitions the sample set using the `percolate` method. * Finally, it adds duplicate samples to the tree and populates the input `CassiopeiaTree` object. 3. **Percolate:** The `percolate` method partitions a set of samples into two groups based on their similarity. * It constructs a similarity graph with samples as nodes and edges weighted by their similarity. * It then iteratively removes the minimum weighted edges until the graph is disconnected into multiple components. * If more than two components are formed, it clusters them using the `joining_solver` and returns the two resulting groups. 4. **Add Duplicates:** The `__add_duplicates_to_tree` method adds duplicate samples to the tree by finding groups of samples with identical character states and placing them as sister nodes under a new internal node. #### Side Effects * Modifies the input `CassiopeiaTree` object to store the reconstructed tree. ### `percolate` #### Description Partitions a set of samples into two groups based on their similarity in the character matrix. #### Inputs | Name | Type | Description | | :------------------------ | :--------------------------------------- | :---------------------------------------------------------------------------------------- | | character\_matrix | pd.DataFrame | The character matrix representing the mutation profiles of the samples. | | samples | List\[str] | A list of sample names to be partitioned. | | priors | Optional\[Dict\[int, Dict\[int, float]]] | A dictionary of prior probabilities for each character/state pair. | | weights | Optional\[Dict\[int, Dict\[int, float]]] | A dictionary of weights for each character/state pair, typically derived from the priors. | | missing\_state\_indicator | int | The character representing missing data in the character matrix. Defaults to -1. | #### Outputs | Name | Type | Description | | :--------------- | :----------------------------- | :---------------------------------------------------------------------------------------- | | partition\_named | Tuple\[List\[str], List\[str]] | A tuple containing two lists of sample names, representing the left and right partitions. | #### Internal Logic 1. **Similarity Graph:** Constructs a weighted graph with samples as nodes and edges weighted by their similarity calculated using the provided `similarity_function`. 2. **Percolation:** Iteratively removes the minimum weighted edges until the graph is disconnected into multiple connected components. 3. **Component Merging (if necessary):** If more than two connected components are formed, it clusters them using the `joining_solver` based on the LCA of each component and returns the two resulting groups. 4. **Return Partitions:** Returns a tuple containing two lists of sample names, representing the left and right partitions. ### `__add_duplicates_to_tree` #### Description Adds duplicate samples to the tree. #### Inputs | Name | Type | Description | | :-------------------- | :-------------------------- | :---------------------------------------------------------------------- | | tree | nx.DiGraph | The tree to which duplicate samples need to be added. | | character\_matrix | pd.DataFrame | The character matrix representing the mutation profiles of the samples. | | node\_name\_generator | Generator\[str, None, None] | A generator object that produces unique node names. | #### Outputs | Name | Type | Description | | :--- | :--------- | :------------------------------------- | | tree | nx.DiGraph | The tree with duplicate samples added. | #### Internal Logic 1. **Identify Duplicates:** Identifies groups of samples with identical character states in the character matrix. 2. **Add Duplicates:** For each group of duplicates: * Creates a new internal node as the parent of the duplicates. * Connects the original sample and all its duplicates as children of this new internal node. 3. **Return Tree:** Returns the modified tree with the duplicate samples added.