Complexity and algorithms for copy-number evolution problems

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

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

Background: 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 is 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. Results: 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. Conclusions: 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 that scales to practical problem instance sizes. We assess the efficiency and quality of our algorithms on simulated instances. Availability:https://github.com/raphael-group/CNT-ILP.

Original languageEnglish (US)
Article number13
JournalAlgorithms for Molecular Biology
Volume12
Issue number1
DOIs
StatePublished - May 16 2017

All Science Journal Classification (ASJC) codes

  • Structural Biology
  • Molecular Biology
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Cancer
  • Copy-number variant
  • Maximum parsimony
  • Phylogeny
  • Somatic mutation

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

  • Cite this

    El-Kebir, M., Raphael, B. J., Shamir, R., Sharan, R., Zaccaria, S., Zehavi, M., & Zeira, R. (2017). Complexity and algorithms for copy-number evolution problems. Algorithms for Molecular Biology, 12(1), [13]. https://doi.org/10.1186/s13015-017-0103-2