Complexity and algorithms for copy-number evolution problems

Algorithms for Molecular Biology : AMB
Mohammed El-KebirRon Zeira

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 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. 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. 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 s...Continue Reading

References

Oct 1, 1976·Science·P C Nowell
Jan 10, 2013·British Journal of Cancer·R FisherC Swanton
Sep 28, 2013·Nature Genetics·Giovanni CirielloChris Sander
Feb 4, 2014·BMC Bioinformatics·Wei JiaoQuaid Morris
Apr 20, 2014·PLoS Computational Biology·Roland F SchwarzFlorian Markowetz
Jan 9, 2015·Bioinformatics·Salem MalikicCenk S Sahinalp
Feb 11, 2015·Nature Genetics·Andrea SottorivaChristina Curtis
May 7, 2015·Genome Biology·Victoria PopicSerafim Batzoglou
Jun 15, 2015·Bioinformatics·Mohammed El-KebirBenjamin J Raphael
Aug 25, 2017·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Ron ZeiraRon Shamir

❮ Previous
Next ❯

Citations

Apr 17, 2018·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Simone ZaccariaBenjamin J Raphael
Jul 14, 2020·Bioinformatics·Ron Zeira, Benjamin J Raphael
Sep 4, 2020·Nature Biotechnology·Simone Zaccaria, Benjamin J Raphael

❮ Previous
Next ❯

Software Mentioned

MEDICC
Alg2
MPP
WABI
Alg1
CPLEX
DP

Related Concepts

Related Feeds

Cancer Genomics (Keystone)

Cancer genomics approaches employ high-throughput technologies to identify the complete catalog of somatic alterations that characterize the genome, transcriptome and epigenome of cohorts of tumor samples. Discover the latest research using such technologies in this feed.