# Three Metaheuristic Approaches for Tumor Phylogeny Inference: An Experimental Comparison
## 3 Methods  
### Particle Swarm Optimization  
The main idea of Particle Swarm Optimization [49] (PSO) revolves around maintaining a population of \(n\) feasible solutions (called particles). These particles move within the search space under the influence of the best overall solutions encountered by the entire population and the individuals themselves. Each particle is characterized by its _position_ and its _velocity_. The population moves synchronously, with all individuals updating their positions and velocities simultaneously, until either convergence is achieved or a specified timeout is reached. The general outline of PSO is provided by Algorithm 1. ```
Data:\(n\): number of particles, \(m\): number of dimensions
1 foreachparticle \(x_{i}\)do
2\(x_{i}\leftarrow\) a random Dollo-\(k\) phylogeny;
3\(p_{i}\gets x_{i}//\ p_{i}\) is the best position seen so far
4 if\(f(p_{i})>f(g)\)then
5\(g\gets p_{i}\)// Currently the best global solution
6 whilehalting criterion not reached yetdo
7 for\(i\gets 1\)to\(n\)do
8\(r_{p},r_{g}\sim\)\(\mathrm{U}(0,1)\);
9\(v_{i}\gets r_{p}(p_{i}-x_{i})+r_{g}(g-x_{i})\)// Update velocity modulus
10 with probability 0.1 // The operation is a transplant
11 with probability 0.5
12\(q\leftarrow\) a subtree of \(p_{i}\) with \(v_{i}\) nodes
13 else
14\(q\leftarrow\) a subtree of \(g\) with \(v_{i}\) nodes
15\(x_{i}\leftarrow\) remove a subtree of \(x_{i}\) with \(v_{i}\) and attach \(q\);
16 Remove all excess mutation losses in \(x_{i}\);
17 Add to \(x_{i}\) at random all missing mutation acquisitions;
18
19 else
20 With uniform probability, pick one of the other operations and apply it to \(T\);
21 if\(f(x_{i})>f(p_{i})\)then
22\(p_{i}\gets x_{i}\);
23 if\(f(p_{i})>f(g)\)then
24\(g\gets p_{i}\)
```  
**Algorithm 1**Particle Swarm Optimization  
In our approach, each phylogeny is represented as a particle, with its topology serving as its position. Initially, positions are generated as random binary trees representing Perfect Phylogeny. At each iteration, particles can move using some of the following operations on a tree \(T\) and a node \(i\), where \(\rho(i)\) denotes the parent of \(i\) in \(T\):  
* Subtree Prune and Reattach: Given two internal nodes, \(u,v\in T\), that are not ancestors of each other, we prune the subtree of \(T\) rooted in \(u\) by removing the edge \((u,\rho(u))\). We then reattach this pruned subtree as a new child of \(v\) by adding the edge \((u,v)\);
* Add a deletion: Given two nodes \(u,v\in T\) such that \(v\) is an ancestor of \(u\), we insert a node \(v^{-}\) in \(T\) to represent the loss of mutation \(v\). The new node becomes the parent of \(u\). Note that this operation is only performed if the resulting tree satisfies the desired phylogeny model. For the Dollo-\(k\) model, we must check that the mutation \(v\) has been lost in the tree at most \(k-1\) times. * Remove a deletion: Given a node \(u\in T\) labeled as a loss, we simply remove it from the tree. All children of \(u\) are added as children of \(\rho(u)\), then the node \(u\) is deleted. * Swap node labels: Given two internal nodes \(u,v\in T\), the labels of \(u\) and \(v\) are swapped. If this operation renders a previously added loss invalid--because a mutation \(c\) is lost in a node \(c^{-}\), but the node where the mutation \(c\) is acquired is no longer an ancestor of \(c^{-}\)--we remove the deletion \(c^{-}\). * Subtree transplant: This operation requires an additional tree \(Q\) which does not necessarily contain the acquisition of all characters of \(T\). The transplant involves: (1) deleting the subtree of \(T\) rooted at \(i\) (i.e., removing \(i\) and all its descendants), (2) making the root of \(Q\) a new child of \(\rho(i)\) (i.e., attaching \(Q\) to \(T\)), and (3) adjusting the resulting tree to ensure it is a Dollo-\(k\) phylogeny for the input mutations.