License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.16
URN: urn:nbn:de:0030-drops-60789
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6078/
Go to the corresponding LIPIcs Volume Portal

Shamir, Ron ; Zehavi, Meirav ; Zeira, Ron

A Linear-Time Algorithm for the Copy Number Transformation Problem

pdf-format:
LIPIcs-CPM-2016-16.pdf (0.5 MB)

Abstract

Problems of genome rearrangement are central in both evolution and cancer. Most evolutionary scenarios have been studied under the assumption that the genome contains a single copy of each gene. In contrast, tumor genomes undergo deletions and duplications, and thus the number of copies of genes varies. The number of copies of each gene along a chromosome is called its copy number profile. Understanding copy number profile changes can assist in predicting disease progression and treatment. To date, questions related to distances between copy number profiles gained little scientific attention. Here we focus on the following fundamental problem, introduced by Schwarz et al. (PLOS Comp. Biol., 2014): given two copy number profiles, u and v, compute the edit distance from u to v, where the edit operations are segmental deletions and amplifications. We establish the computational complexity of this problem, showing that it is solvable in linear time and constant space.

BibTeX - Entry

@InProceedings{shamir_et_al:LIPIcs:2016:6078,
  author =	{Ron Shamir and Meirav Zehavi and Ron Zeira},
  title =	{{A Linear-Time Algorithm for the Copy Number Transformation Problem}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6078},
  URN =		{urn:nbn:de:0030-drops-60789},
  doi =		{10.4230/LIPIcs.CPM.2016.16},
  annote =	{Keywords: Genome Rearrangement, Copy Number}
}

Keywords: Genome Rearrangement, Copy Number
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI