LIPIcs.CPM.2016.16.pdf
- Filesize: 0.53 MB
- 13 pages
Document
A Linear-Time Algorithm for the Copy Number Transformation Problem
Authors
-
Part of:
Volume:
27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-27
Cite As Get BibTex
Ron Shamir, Meirav Zehavi, and Ron Zeira. A Linear-Time Algorithm for the Copy Number Transformation Problem. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CPM.2016.16
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.
Subject Classification
Keywords
- Genome Rearrangement
- Copy Number
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ryan P Abo, Matthew Ducar, Elizabeth P Garcia, Aaron R Thorner, Vanesa Rojas-Rudilla, Ling Lin, Lynette M Sholl, William C Hahn, Matthew Meyerson, Neal I Lindeman, Paul Van Hummelen, and Laura E MacConaill. BreaKmer: detection of structural variation in targeted massively parallel sequencing data using kmers. Nucleic Acids Research, nov 2014. URL: http://dx.doi.org/10.1093/nar/gku1211.
- Salim Akhter Chowdhury, E Michael Gertz, Darawalee Wangsa, Kerstin Heselmeyer-Haddad, Thomas Ried, Alejandro A Schäffer, and Russell Schwartz. Inferring models of multiscale copy number evolution for single-tumor phylogenetics. Bioinformatics, 31(12):i258-67, jun 2015. URL: http://dx.doi.org/10.1093/bioinformatics/btv233.
- Salim Akhter Chowdhury, Stanley E Shackney, Kerstin Heselmeyer-Haddad, Thomas Ried, Alejandro A Schäffer, and Russell Schwartz. Phylogenetic analysis of multiprobe fluorescence in situ hybridization data from tumor cell populations. Bioinformatics, 29(13):i189-98, jul 2013. URL: http://dx.doi.org/10.1093/bioinformatics/btt205.
- Salim Akhter Chowdhury, Stanley E Shackney, Kerstin Heselmeyer-Haddad, Thomas Ried, Alejandro A Schäffer, and Russell Schwartz. Algorithms to model single gene, single chromosome, and whole genome copy number changes jointly in tumor phylogenetics. PLoS Computational Biology, 10(7):e1003740, jul 2014. URL: http://dx.doi.org/10.1371/journal.pcbi.1003740.
-
Guillaume Fertin, Anthony Labarre, Irena Rusu, Eric Tannier, and Stéphane Vialette. Combinatorics of Genome Rearrangements. MIT Press, 2009.
- Eric Letouzé, Yves Allory, Marc A Bollet, François Radvanyi, and Frédéric Guyon. Analysis of the copy number profiles of several tumor samples from the same patient reveals the successive steps in tumorigenesis. Genome Biology, 11(7):R76, 2010. URL: http://dx.doi.org/10.1186/gb-2010-11-7-r76.
- Andrew McPherson, Chunxiao Wu, Alexander W Wyatt, Sohrab Shah, Colin Collins, and S Cenk Sahinalp. nFuse: discovery of complex genomic rearrangements in cancer using high-throughput sequencing. Genome Research, 22(11):2250-61, nov 2012. URL: http://dx.doi.org/10.1101/gr.136572.111.
- M Mohri. Weighted finite-state transducer algorithms. An overview. Formal Languages and Applications, 2004. URL: http://link.springer.com/chapter/10.1007/978-3-540-39886-8_29.
-
Mehryar Mohri. Edit-distance of weighted automata: General definitions and algorithms. International Journal of Foundations of Computer Science, 14(06):957-982, 2003.
- Layla Oesper, Anna Ritz, Sarah J Aerni, Ryan Drebin, and Benjamin J Raphael. Reconstructing cancer genomes from paired-end sequencing data. BMC Bioinformatics, 13 Suppl 6(Suppl 6):S10, jan 2012. URL: http://dx.doi.org/10.1186/1471-2105-13-S6-S10.
- D. Pinkel, T. Straume, and J. W. Gray. Cytogenetic analysis using quantitative, high-sensitivity, fluorescence hybridization. Proceedings of the National Academy of Sciences, 83(9):2934-2938, may 1986. URL: http://dx.doi.org/10.1073/pnas.83.9.2934.
- Olivier Tremblay Savard, Yves Gagnon, Denis Bertrand, and Nadia El-Mabrouk. Genome halving and double distance with losses. Journal of Computational Biology, 18(9):1185-99, 2011. URL: http://dx.doi.org/10.1089/cmb.2011.0136.
- Roland F Schwarz, Anne Trinh, Botond Sipos, James D Brenton, Nick Goldman, and Florian Markowetz. Phylogenetic quantification of intra-tumour heterogeneity. PLoS Computational Biology, 10(4):e1003535, apr 2014. URL: http://dx.doi.org/10.1371/journal.pcbi.1003535.
- Mingfu Shao and Yu Lin. Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion. BMC Bioinformatics, 13(Suppl 19):S13, 2012. URL: http://dx.doi.org/10.1186/1471-2105-13-S19-S13.
- Eric Tannier, Chunfang Zheng, and David Sankoff. Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics, 10(1):120, 2009. URL: http://www.biomedcentral.com/1471-2105/10/120, URL: http://dx.doi.org/10.1186/1471-2105-10-120.
- The Cancer Genome Atlas Research Network. Integrated genomic analyses of ovarian carcinoma. Nature, 474(7353):609-15, jun 2011. URL: http://dx.doi.org/10.1038/nature10166.
- Alexander Eckehart Urban, Jan O Korbel, Rebecca Selzer, Todd Richmond, April Hacker, George V Popescu, Joseph F Cubells, Roland Green, Beverly S Emanuel, Mark B Gerstein, Sherman M Weissman, and Michael Snyder. High-resolution mapping of DNA copy alterations in human chromosome 22 using high-density tiling oligonucleotide arrays. Proceedings of the National Academy of Sciences, 103(12):4534-9, mar 2006. URL: http://dx.doi.org/10.1073/pnas.0511340103.