# Copy-number evolution problems: complexity and algorithms

Published in *International Workshop on Algorithms in Bioinformatics (WABI 2016)*, 2016

Recommended citation: M. El-Kebir, B.J. Raphael, R. Shamir, R. Sharan, S. Zaccaria, M. Zehavi, and R. Zeira. Copy-number evolution problems: complexity and algorithms. In International Workshop on Algorithms in Bioinformatics (WABI 2016), pp. 137-149. Springer, 2016. __https://link.springer.com/chapter/10.1007/978-3-319-43681-4_11__

# Abstract

Cancer is an evolutionary process characterized by the accumulation of somatic mutations in a population of cells that form a tumor. One frequent type of mutations are copy number aberrations, which alter the number of copies of genomic regions. The number of copies of each position along a chromosome constitutes the chromosome’s copy-number profile. Understanding how such profiles evolve in cancer can assist in both diagnosis and prognosis. We model the evolution of a tumor by segmental deletions and amplifications, and gauge distance from profile a to b by the minimum number of events needed to transform a into b . Given two profiles, our first problem aims to find a parental profile that minimizes the sum of distances to its children. Given k profiles, the second, more general problem, seeks a phylogenetic tree, whose k leaves are labeled by the k given profiles and whose internal vertices are labeled by ancestral profiles such that the sum of edge distances is minimum. For the former problem we give a pseudo-polynomial dynamic programming algorithm that is linear in the profile length, and an integer linear program formulation. For the latter problem we show it is NP-hard and give an integer linear program formulation. We assess the efficiency and quality of our algorithms on simulated instances.