# Three Metaheuristic Approaches for Tumor Phylogeny Inference: An Experimental Comparison
## 1 Introduction  
Inferring phylogenies is one of the key problems in bioinformatics, and its importance has increased more and more in recent years, as the availability of genetic data extracted from cancer samples has allowed researchers to examine how somatic mutations occur and, most importantly, accumulate during the progression of cancer. Furthermore, recent improvements in targeted therapies for cancer treatment require an accurate inference of the clonal evolution and progression of the disease to provide effective therapy [1, 2]. Given the importance of the problem [3], several methods [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] designed to infer cancer progression from next-generation sequencing data have been published. The field has also recently witnessed the development of pipelines [21] and preprocessing steps. Cancer cells proliferate in a highly constrained environment under very strong evolutionary pressure--for example, due to low levels of oxygen and the reaction of the immune system. This leads to frequently observed mutations that are very unusual in healthy cells [22], such as copy number aberrations, gene duplications, and ploidy changes. Some tools try to incorporate these mutational events when inferring tumoral evolutions (see, for example, [8, 23]). While the predictions should become more accurate with such events included, the models become more complicated. Because the focus of this paper is a computational comparison, we do not consider these events, only the acquisition and loss of mutations. On the other hand, single-cell sequencing data have provided clear evidence that mutation losses and (less frequently) mutation recurrences are common [24; 25]. In fact, allowing only mutation accumulation corresponds to the directed perfect phylogeny problem on binary characters, which has a linear-time algorithm [26], while more general models (where mutation losses or recurrences are also allowed) result in NP-complete problems, with a much larger solution space. The perfect phylogeny model has found several applications in bioinformatics, most notably in haplotyping [27; 28; 29; 30], and has been deeply investigated. For example, the combinatorial properties of perfect phylogenies are instrumental in the development of efficient algorithms, including the graph-theoretical characterization of genotype matrices that admit a tree representation [27; 28; 30; 31]. In this paper, we focus on the Dollo-\(k\) model [5; 32; 33; 34], which is a generalization of the perfect phylogeny model that incorporates the potential loss of characters. Under the Dollo-\(k\) model, each mutation can only be acquired once and lost at most \(k\) times in the entire evolutionary process. The restriction on the number of losses is motivated by the fact that even if character losses are possible, they are not frequent [24; 35]. Variants of the Dollo-\(k\) model are considered in some recent tools, such as TRAIT [36], SiFit [37] and SPhyR [15], SASC [6], and ScisTree [38]. Notice that we are considering the _binary_ case, where each mutation is either present or missing. The phylogeny inference problem under the Dollo-\(k\) model is NP complete [39], motivating the use of specialized metaheuristic strategies [6; 15] which work well in practice even with fairly large instances. The fact that practical cases have incomplete or noisy information makes the use of heuristics more relevant [40; 41]. Nonetheless, at least an exact solution for the problem, based on ILP, has been proposed [4], but it is too slow to be used in practice. To mitigate this problem, that tool has a hill climbing final step to guarantee that a local optimum is returned.