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 -