2020/02/25 by Garance Cordonnier, Cordonnier, Garance, Manuel Lafond +1
Biochemistry, Genetics and Molecular Biology · #Cancer Genomics and Diagnostics #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Genomic variations and chromosomal abnormalities #Genomics (q-bio.GN) #Genomics and Rare Diseases
paper · pdf · doi:10.48550/arxiv.2002.11271
openalex publication_date 2020/02/25 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
During cancer progression, malignant cells accumulate somatic mutations that\ncan lead to genetic aberrations. In particular, evolutionary events akin to\nsegmental duplications or deletions can alter the copy-number profile (CNP) of\na set of genes in a genome. Our aim is to compute the evolutionary distance\nbetween two cells for which only CNPs are known. This asks for the minimum\nnumber of segmental amplifications and deletions to turn one CNP into another.\nThis was recently formalized into a model where each event is assumed to alter\na copy-number by 1 or -1, even though these events can affect large\nportions of a chromosome. We propose a general cost framework where an event\ncan modify the copy-number of a gene by larger amounts. We show that any cost\nscheme that allows segmental deletions of arbitrary length makes computing the\ndistance strongly NP-hard. We then devise a factor 2 approximation algorithm\nfor the problem when copy-numbers are non-zero and provide an implementation\ncalled textsfcnp2cnp. We evaluate our approach experimentally by\nreconstructing simulated cancer phylogenies from the pairwise distances\ninferred by textsfcnp2cnp and compare it against two other alternatives,\nnamely the textsfMEDICC distance and the Euclidean distance. The\nexperimental results show that our distance yields more accurate phylogenies on\naverage than these alternatives if the given CNPs are error-free, but that the\n textsfMEDICC distance is slightly more robust against error in the data. In\nall cases, our experiments show that either our approach or the textsfMEDICC\napproach should preferred over the Euclidean distance.\n