Copy-number evolution problems: Complexity and algorithms

Mohammed El-Kebir, Benjamin J. Raphael, Ron Shamir, Roded Sharan, Simone Zaccaria, Meirav Zehavi, Ron Zeira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings
EditorsMartin Frith, Christian Nørgaard Storm Pedersen
PublisherSpringer Verlag
Pages137-149
Number of pages13
ISBN (Print)9783319436807
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event16th International Workshop on Algorithms in Bioinformatics, WABI 2016 - Aarhus, Denmark
Duration: Aug 22 2016Aug 24 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9838 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Workshop on Algorithms in Bioinformatics, WABI 2016
CountryDenmark
CityAarhus
Period8/22/168/24/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Copy-number evolution problems: Complexity and algorithms'. Together they form a unique fingerprint.

  • Cite this

    El-Kebir, M., Raphael, B. J., Shamir, R., Sharan, R., Zaccaria, S., Zehavi, M., & Zeira, R. (2016). Copy-number evolution problems: Complexity and algorithms. In M. Frith, & C. N. S. Pedersen (Eds.), Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings (pp. 137-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9838 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-43681-4_11