The Copy Number Transformation Problem


Meirav Zehavi, U Bergen, Norway

Problems of genome rearrangement are central in both evolution and cancer. Most evolutionary scenarios have been studied under the assumption that the genome contains a single copy of each gene. In contrast, tumor genomes undergo deletions and duplications, and thus the number of copies of genes varies. The number of copies of each gene along a chromosome is called its copy number profile. Understanding copy number profile changes can assist in predicting disease progression and treatment. To date, questions related to distances between copy number profiles gained little scientific attention. In this talk, I will focus on the Copy Number Transformation problem: given two copy number profiles, u and v, compute the edit distance from u to v, where the edit operations are segmental deletions and amplifications. I will discuss the computational complexity of this problem, showing that it is solvable in linear time and constant space. Moreover, I will address the Copy Number Triplet problem as well as the Copy Number Tree problem, which are extensions of the Copy Number Transformation problem.