Skip to main content

Complexity and algorithms for copy-number evolution problems.

Author(s): El-Kebir, Mohammed; Raphael, Benjamin J; Shamir, Ron; Sharan, Roded; Zaccaria, Simone; et al

To refer to this page use:
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 [Formula: see text] to [Formula: see text] by the minimum number of events needed to transform [Formula: see text] into [Formula: see text]. 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:
Publication Date: Jan-2017
Citation: El-Kebir, Mohammed, Raphael, Benjamin J, Shamir, Ron, Sharan, Roded, Zaccaria, Simone, Zehavi, Meirav, Zeira, Ron. (2017). Complexity and algorithms for copy-number evolution problems.. Algorithms for molecular biology : AMB, 12 (13 - ?. doi:10.1186/s13015-017-0103-2
DOI: doi:10.1186/s13015-017-0103-2
ISSN: 1748-7188
EISSN: 1748-7188
Pages: 13 - ?
Language: eng
Type of Material: Journal Article
Journal/Proceeding Title: Algorithms for molecular biology : AMB
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.