# Three Metaheuristic Approaches for Tumor Phylogeny Inference: An Experimental Comparison
## 2 Preliminaries  
In this paper, we consider the computational problem of inferring a tumor phylogeny from single cell data in the presence of partial information. The input of the problem is an \(n\times m\) ternary matrix \(I_{ij}\) that represents the presence/absence of \(m\) mutations in \(n\) cells. The entries of \(I\) can assume three potential values: an entry \(I_{ij}=0\) indicates that cell \(i\) does not have mutation \(j\), \(I_{ij}=1\) indicates the presence of mutation \(j\) in cell \(i\), and a? indicates uncertainty about the presence/absence of mutation \(j\) in cell \(i\). The uncertainty in mutation presence within a cell is typically caused by insufficient coverage during sequencing. Moreover, our models account for potential false positive and false negative entries in the input matrix, which are parameterized with a false positive/negative rate value. Specifically, let \(E\) denote the final \(n\times m\) output matrix, which is the binary matrix without errors and noise estimated by the algorithm. We denote \(\alpha_{j}\) as the false negative rate of mutation \(j\), and \(\beta\) as the false positive rate, similarly to [11; 15; 37; 48]. Hence, for each entry \(E_{ij}\), the following holds:\[P(I_{ij}=0|E_{ij}=0)=1-\beta P(I_{ij}=0|E_{ij}=1)=\alpha_{j}\] \[P(I_{ij}=1|E_{ij}=0)=\beta P(I_{ij}=1|E_{ij}=1)=1-\alpha_{j}.\]  
Notice that, due to the nature of the experimental measure, the false positive rate is usually low (around \(10^{-6}\)), while the false negative rate can be considerably higher (even 40%) [11; 37; 48]. Furthermore, each mutation can have a different false negative rate; for instance, a highly expressed gene will have significantly higher coverage than an under-expressed gene. Similar to previous reconstruction methods ([6]), the objective of the reconstruction problem is to compute a matrix that maximizes the likelihood of the observed matrix \(I\)[48], assuming we know the probability rates of false positives, false negatives, and missing entries. This is conducted under the hypothesis that mutations in samples are acquired and lost following a specific evolutionary model. A tumor phylogeny \(T\) on a set \(C\) of \(m\) mutations and \(n\) cells is defined as a rooted tree whose internal nodes are labeled by the acquisitions or losses of mutations from \(C\), while the leaves are labeled by the cells. The _state_ of a node \(x\) is defined as the set of mutations \(c\) such that: (1) there is an ancestor of \(x\) where \(c\) is acquired, and (2) for each ancestor \(y\) of \(x\) where \(c\) is lost, there is a node of the path from \(y\) to \(x\) where \(c\) is acquired. Therefore, the state of each node \(x\) in the tree \(T\) can be represented as a binary vector of length \(m\), called genotype profile and denoted by \(D(T,x)\), where \(D(T,x)_{c}=1\) if and only if the node \(x\) has the mutation \(j\) and \(0\) otherwise. Given a binary matrix \(E\), we say that a tree \(T\)_encodes_\(E\) if there exists a mapping \(\sigma\) of the rows (cells) of \(E\) to the leaves of \(T\) such that \(E_{i}=D(T,\sigma_{i})\) for each row \(i\) of \(E\), where \(\sigma_{i}\) denotes the image of row \(i\) through the mapping \(\sigma\). Informally, \(\sigma_{i}\) is the node in the phylogenetic tree corresponding to the node where the cell \(i\) is attached. It is important to note that, given an input matrix \(I\), the pair \((T,\sigma)\) fully characterizes the output matrix \(E\). Consequently, the reconstruction problem can be formulated as finding a tree \(T\) that maximizes the following objective function:  
\[\max\sum_{j}^{m}\sum_{i}^{n}\log(P(I_{ij}|D(T,\sigma_{i})_{j}))\]  
To simplify the computation of the likelihood, we make a slight abuse of notation by assuming that \(P(I_{ij}=\?|E_{ij}=1)=P(I_{ij}=\?|E_{ij}=0)=1\). Furthermore, given a tumor phylogeny \(T\), we can define the mapping \(\sigma\) as the one that maximizes the objective function.