TY - GEN

T1 - Copy-number evolution problems

T2 - 16th International Workshop on Algorithms in Bioinformatics, WABI 2016

AU - El-Kebir, Mohammed

AU - Raphael, Benjamin J.

AU - Shamir, Ron

AU - Sharan, Roded

AU - Zaccaria, Simone

AU - Zehavi, Meirav

AU - Zeira, Ron

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84985031012&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985031012&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-43681-4_11

DO - 10.1007/978-3-319-43681-4_11

M3 - Conference contribution

AN - SCOPUS:84985031012

SN - 9783319436807

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 137

EP - 149

BT - Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings

A2 - Frith, Martin

A2 - Pedersen, Christian Nørgaard Storm

PB - Springer Verlag

Y2 - 22 August 2016 through 24 August 2016

ER -