Document Open Access Logo

Genome Halving and Aliquoting Under the Copy Number Distance

Authors Ron Zeira , Geoffrey Mon , Benjamin J. Raphael

PDF
Thumbnail PDF

File

LIPIcs.WABI.2021.18.pdf
  • Filesize: 1.57 MB
  • 25 pages

Document Identifiers

Author Details

Ron Zeira
  • Department of Computer Science, Princeton University, NJ, USA
Geoffrey Mon
  • Department of Computer Science, Princeton University, NJ, USA
Benjamin J. Raphael
  • Department of Computer Science, Princeton University, NJ, USA

Funding

  • Raphael, Benjamin J.: This work is supported by a US National Institutes of Health (NIH) grants U24CA211000 and U24CA248453.

Cite As Get BibTex

Ron Zeira, Geoffrey Mon, and Benjamin J. Raphael. Genome Halving and Aliquoting Under the Copy Number Distance. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 18:1-18:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.WABI.2021.18

Abstract

Large-scale genome rearrangements occur frequently in species evolution and cancer evolution. While the computation of evolutionary distances is tractable for balanced rearrangements, such as inversions and translocations, computing distances involving duplications and deletions is much more difficult. In the recently proposed Copy Number Distance (CND) model, a genome is represented as a Copy Number Profile (CNP), a sequence of integers, and the CND between two CNPs is the length of a shortest sequence of deletions and amplifications of contiguous segments that transforms one CNP into the other. In addition to these segmental events, genomes also undergo global events such as Whole Genome Duplication (WGD) or polyploidization that multiply the entire genome content. These global events are common and important in both species and cancer evolution. In this paper, we formulate the genome halving problem of finding a closest preduplication CNP that has undergone a WGD and evolved into a given CNP under the CND model. We also formulate the analogous genome aliquoting problem of finding the closest prepolyploidzation CNP under the CND distance. We give a linear time algorithm for the halving distance and a quadratic time dynamic programming algorithm for the aliquoting distance. We implement these algorithms and show that they produce reasonable solutions on simulated CNPs.

Subject Classification

ACM Subject Classification
  • Applied computing → Molecular evolution
Keywords
  • Genome rearrangements
  • Copy number distance
  • Whole genome duplication
  • polyploidization
  • genome halving distance
  • genome aliquoting distance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Max A. Alekseyev and Pavel A. Pevzner. Genome halving problem revisited. In Kamal Lodaya and Meena Mahajan, editors, FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, pages 1-15, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  2. Max A Alekseyev and Pavel A Pevzner. Colored de Bruijn graphs and the genome halving problem. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(1):98-107, 2007. URL: https://doi.org/10.1109/TCBB.2007.1002.
  3. Anne Bergeron, Julia Mixtacki, and Jens Stoye. A unifying view of genome rearrangements. In Philipp Bücher and Bernard M.E. Moret, editors, Proc. Workshop on Algorithms in Bioinformatics, volume 4175 of LNCS, pages 163-173. Springer, 2006. URL: https://doi.org/10.1007/11851561_16.
  4. Craig M Bielski, Ahmet Zehir, Alexander V Penson, Mark TA Donoghue, Walid Chatila, Joshua Armenia, Matthew T Chang, Alison M Schram, Philip Jonsson, Chaitanya Bandlamudi, et al. Genome doubling shapes the evolution and prognosis of advanced cancers. Nature genetics, 50(8):1189-1195, 2018. Google Scholar
  5. John E Bowers, Brad A Chapman, Junkang Rong, and Andrew H Paterson. Unravelling angiosperm genome evolution by phylogenetic analysis of chromosomal duplication events. Nature, 422(6930):433, 2003. Google Scholar
  6. Peter J. Campbell, Gad Getz, Jan O. Korbel, Joshua M. Stuart, Jennifer L. Jennings, Lincoln D. Stein, Marc D. Perry, Hardeep K. Nahal-Bose, B. F. Francis Ouellette, Constance H. Li, Esther Rheinbay, G. Petur Nielsen, Dennis C. Sgroi, Chin-Lee Wu, William C. Faquin, Vikram Deshpande, Paul C. Boutros, Alexander J. Lazar, Katherine A. Hoadley, David N. Louis, L. Jonathan Dursi, Christina K. Yung, Matthew H. Bailey, Gordon Saksena, Keiran M. Raine, Ivo Buchhalter, Kortine Kleinheinz, Matthias Schlesner, Junjun Zhang, Wenyi Wang, David A. Wheeler, Li Ding, Jared T. Simpson, Brian D. O'Connor, Sergei Yakneen, Kyle Ellrott, Naoki Miyoshi, Adam P. Butler, Romina Royo, Solomon I. Shorser, Miguel Vazquez, Tobias Rausch, Grace Tiao, Sebastian M. Waszak, Bernardo Rodriguez-Martin, Suyash Shringarpure, Dai-Ying Wu, German M. Demidov, Olivier Delaneau, Shuto Hayashi, Seiya Imoto, Nina Habermann, Ayellet V. Segre, Erik Garrison, Andy Cafferkey, Eva G. Alvarez, JoséMaría Heredia-Genestar, Francesc Muyas, Oliver Drechsel, Alicia L. Bruzos, Javier Temes, Jorge Zamora, Adrian Baez-Ortega, Hyung-Lae Kim, R. Jay Mashl, Kai Ye, Anthony DiBiase, Kuan-lin Huang, Ivica Letunic, Michael D. McLellan, Steven J. Newhouse, Tal Shmaya, Sushant Kumar, David C. Wedge, Mark H. Wright, Venkata D. Yellapantula, Mark Gerstein, Ekta Khurana, Tomas Marques-Bonet, Arcadi Navarro, Carlos D. Bustamante, Reiner Siebert, Hidewaki Nakagawa, Douglas F. Easton, Stephan Ossowski, Jose M. C. Tubio, Francisco M. De La Vega, Xavier Estivill, Denis Yuen, George L. Mihaiescu, Larsson Omberg, Vincent Ferretti, Radhakrishnan Sabarinathan, Oriol Pich, Abel Gonzalez-Perez, Amaro Taylor-Weiner, Matthew W. Fittall, Jonas Demeulemeester, Maxime Tarabichi, Nicola D. Roberts, Peter Van Loo, Isidro Cortés-Ciriano, Lara Urban, Peter Park, Bin Zhu, Esa Pitkänen, Yilong Li, Natalie Saini, Leszek J. Klimczak, Joachim Weischenfeldt, Nikos Sidiropoulos, Ludmil B. Alexandrov, Raquel Rabionet, Georgia Escaramis, Mattia Bosio, Aliaksei Z. Holik, Hana Susak, Aparna Prasad, Serap Erkek, Claudia Calabrese, Benjamin Raeder, Eoghan Harrington, Simon Mayes, Daniel Turner, Sissel Juul, Steven A. Roberts, Lei Song, Roelof Koster, Lisa Mirabello, Xing Hua, Tomas J. Tanskanen, Marta Tojo, Jieming Chen, Lauri A. Aaltonen, Gunnar Rätsch, Roland F. Schwarz, Atul J. Butte, Alvis Brazma, Stephen J. Chanock, Nilanjan Chatterjee, Oliver Stegle, Olivier Harismendy, G. Steven Bova, Dmitry A. Gordenin, David Haan, Lina Sieverling, Lars Feuerbach, Don Chalmers, Yann Joly, Bartha Knoppers, Fruzsina Molnár-Gábor, Mark Phillips, Adrian Thorogood, David Townend, Mary Goldman, Nuno A. Fonseca, Qian Xiang, Brian Craft, Elena Piñeiro-Yáñez, Alfonso Muñoz, Robert Petryszak, Anja Füllgrabe, Fatima Al-Shahrour, Maria Keays, David Haussler, John Weinstein, Wolfgang Huber, Alfonso Valencia, Irene Papatheodorou, Jingchun Zhu, Yu Fan, David Torrents, Matthias Bieg, Ken Chen, Zechen Chong, Kristian Cibulskis, Roland Eils, Robert S. Fulton, Josep L. Gelpi, Santiago Gonzalez, Ivo G. Gut, Faraz Hach, Michael Heinold, Taobo Hu, Vincent Huang, Barbara Hutter, Natalie Jäger, Jongsun Jung, Yogesh Kumar, Christopher Lalansingh, Ignaty Leshchiner, Dimitri Livitz, Eric Z. Ma, Yosef E. Maruvka, Ana Milovanovic, Morten Muhlig Nielsen, Nagarajan Paramasivam, Jakob Skou Pedersen, Montserrat Puiggròs, S. Cenk Sahinalp, Iman Sarrafi, Chip Stewart, Miranda D. Stobbe, Jeremiah A. Wala, Jiayin Wang, Michael Wendl, Johannes Werner, Zhenggang Wu, Hong Xue, Takafumi N. Yamaguchi, Venkata Yellapantula, Brandi N. Davis-Dusenbery, Robert L. Grossman, Youngwook Kim, Michael C. Heinold, Jonathan Hinton, David R. Jones, Andrew Menzies, Lucy Stebbings, Julian M. Hess, Mara Rosenberg, Andrew J. Dunford, Manaswi Gupta, Marcin Imielinski, Matthew Meyerson, Rameen Beroukhim, Jüri Reimand, Priyanka Dhingra, Francesco Favero, Stefan Dentro, Jeff Wintersinger, Vasilisa Rudneva, Ji Wan Park, Eun Pyo Hong, Seong Gu Heo, André Kahles, Kjong-Van Lehmann, Cameron M. Soulette, Yuichi Shiraishi, Fenglin Liu, Yao He, Deniz Demircioğlu, Natalie R. Davidson, Liliana Greger, Siliang Li, Dongbing Liu, Stefan G. Stark, Fan Zhang, Samirkumar B. Amin, Peter Bailey, Aurélien Chateigner, Milana Frenkel-Morgenstern, Yong Hou, Matthew R. Huska, Helena Kilpinen, Fabien C. Lamaze, Chang Li, Xiaobo Li, Xinyue Li, Xingmin Liu, Maximillian G. Marin, Julia Markowski, Tannistha Nandi, Akinyemi I. Ojesina, Qiang Pan-Hammarström, Peter J. Park, Chandra Sekhar Pedamallu, Hong Su, Patrick Tan, Bin Tean Teh, Jian Wang, Heng Xiong, Chen Ye, Christina Yung, Xiuqing Zhang, Liangtao Zheng, Shida Zhu, Philip Awadalla, Chad J. Creighton, Kui Wu, Huanming Yang, Jonathan Göke, Zemin Zhang, Angela N. Brooks, Matthew W. Fittall, Iñigo Martincorena, Carlota Rubio-Perez, Malene Juul, Steven Schumacher, Ofer Shapira, David Tamborero, Loris Mularoni, Henrik Hornshøj, Jordi Deu-Pons, Ferran Muiños, Johanna Bertl, Qianyun Guo, and The ICGC/TCGA Pan-Cancer Analysis of Whole Genomes Consortium. Pan-cancer analysis of whole genomes. Nature, 578(7793):82-93, 2020. URL: https://doi.org/10.1038/s41586-020-1969-6.
  7. Scott L Carter, Kristian Cibulskis, Elena Helman, Aaron McKenna, Hui Shen, Travis Zack, Peter W Laird, Robert C Onofrio, Wendy Winckler, Barbara A Weir, et al. Absolute quantification of somatic dna alterations in human cancer. Nature biotechnology, 30(5):413, 2012. Google Scholar
  8. 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, 2014. Google Scholar
  9. Stefan C. Dentro, Ignaty Leshchiner, Kerstin Haase, Maxime Tarabichi, Jeff Wintersinger, Amit G. Deshwar, Kaixian Yu, Yulia Rubanova, Geoff Macintyre, Jonas Demeulemeester, Ignacio Vázquez-García, Kortine Kleinheinz, Dimitri G. Livitz, Salem Malikic, Nilgun Donmez, Subhajit Sengupta, Pavana Anur, Clemency Jolly, Marek Cmero, Daniel Rosebrock, Steven E. Schumacher, Yu Fan, Matthew Fittall, Ruben M. Drews, Xiaotong Yao, Thomas B. K. Watkins, Juhee Lee, Matthias Schlesner, Hongtu Zhu, David J. Adams, Nicholas McGranahan, Charles Swanton, Gad Getz, Paul C. Boutros, Marcin Imielinski, Rameen Beroukhim, S. Cenk Sahinalp, Yuan Ji, Martin Peifer, Inigo Martincorena, Florian Markowetz, Ville Mustonen, Ke Yuan, Moritz Gerstung, Paul T. Spellman, Wenyi Wang, Quaid D. Morris, David C. Wedge, Peter Van Loo, Stefan C. Dentro, Amit G. Deshwar, Santiago Gonzalez, David J. Adams, Paul C. Boutros, David D. Bowtell, Peter J. Campbell, Shaolong Cao, Elizabeth L. Christie, Yupeng Cun, Kevin J. Dawson, Ruben M. Drews, Roland Eils, Dale W. Garsed, Gavin Ha, Lara Jerman, Henry Lee-Six, Dimitri G. Livitz, Thomas J. Mitchell, Layla Oesper, Myron Peto, Benjamin J. Raphael, S. Cenk Sahinalp, Adriana Salcedo, Steven E. Schumacher, Ruian Shi, Seung Jun Shin, Lincoln D. Stein, Oliver Spiro, Shankar Vembu, David A. Wheeler, Tsun-Po Yang, Quaid D. Morris, Paul T. Spellman, and David C. Wedge. Characterizing genetic intra-tumor heterogeneity across 2,658 human cancer genomes. Cell, 2021. URL: https://doi.org/10.1016/j.cell.2021.03.009.
  10. Li Ding, Timothy J Ley, David E Larson, Christopher A Miller, Daniel C Koboldt, John S Welch, Julie K Ritchey, Margaret A Young, Tamara Lamprecht, Michael D McLellan, Joshua F McMichael, John W Wallis, Charles Lu, Dong Shen, Christopher C Harris, David J Dooling, Robert S Fulton, Lucinda L Fulton, Ken Chen, Heather Schmidt, Joelle Kalicki-Veizer, Vincent J Magrini, Lisa Cook, Sean D McGrath, Tammi L Vickery, Michael C Wendl, Sharon Heath, Mark A Watson, Daniel C Link, Michael H Tomasson, William D Shannon, Jacqueline E Payton, Shashikant Kulkarni, Peter Westervelt, Matthew J Walter, Timothy A Graubert, Elaine R Mardis, Richard K Wilson, and John F DiPersio. Clonal evolution in relapsed acute myeloid leukaemia revealed by whole-genome sequencing. Nature, 481(7382):506-10, 2012. URL: https://doi.org/10.1038/nature10738.
  11. Mohammed El-Kebir, Benjamin J Raphael, Ron Shamir, Roded Sharan, Simone Zaccaria, Meirav Zehavi, and Ron Zeira. Complexity and algorithms for copy-number evolution problems. Algorithms for Molecular Biology, 12(1):13, 2017. Google Scholar
  12. Nadia El-Mabrouk, Joseph H. Nadeau, and David Sankoff. Genome halving. In Martin Farach-Colton, editor, Proc. Combinatorial Pattern Matching, pages 235-250, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. Google Scholar
  13. Pedro Feijão and Joao Meidanis. SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5):1318-29, 2011. URL: https://doi.org/10.1109/TCBB.2011.34.
  14. Guillaume Fertin, Anthony Labarre, Irena Rusu, Stéphane Vialette, and Eric Tannier. Combinatorics of genome rearrangements. MIT press, 2009. Google Scholar
  15. Andrej Fischer, Ignacio Vázquez-García, Christopher JR Illingworth, and Ville Mustonen. High-definition reconstruction of clonal composition in cancer. Cell reports, 7(5):1740-1752, 2014. Google Scholar
  16. Moritz Gerstung, Clemency Jolly, Ignaty Leshchiner, Stefan C. Dentro, Santiago Gonzalez, Daniel Rosebrock, Thomas J. Mitchell, Yulia Rubanova, Pavana Anur, Kaixian Yu, Maxime Tarabichi, Amit Deshwar, Jeff Wintersinger, Kortine Kleinheinz, Ignacio Vázquez-García, Kerstin Haase, Lara Jerman, Subhajit Sengupta, Geoff Macintyre, Salem Malikic, Nilgun Donmez, Dimitri G. Livitz, Marek Cmero, Jonas Demeulemeester, Steven Schumacher, Yu Fan, Xiaotong Yao, Juhee Lee, Matthias Schlesner, Paul C. Boutros, David D. Bowtell, Hongtu Zhu, Gad Getz, Marcin Imielinski, Rameen Beroukhim, S. Cenk Sahinalp, Yuan Ji, Martin Peifer, Florian Markowetz, Ville Mustonen, Ke Yuan, Wenyi Wang, Quaid D. Morris, Stefan C. Dentro, Amit G. Deshwar, David J. Adams, Paul C. Boutros, David D. Bowtell, Peter J. Campbell, Shaolong Cao, Elizabeth L. Christie, Yupeng Cun, Kevin J. Dawson, Ruben M. Drews, Roland Eils, Matthew Fittall, Dale W. Garsed, Gavin Ha, Henry Lee-Six, Dimitri G. Livitz, Inigo Martincorena, Thomas J. Mitchell, Layla Oesper, Myron Peto, Benjamin J. Raphael, S. Cenk Sahinalp, Adriana Salcedo, Ruian Shi, Seung Jun Shin, Oliver Spiro, Lincoln D. Stein, Shankar Vembu, David A. Wheeler, Tsun-Po Yang, Quaid D. Morris, Paul T. Spellman, David C. Wedge, Peter Van Loo, Paul T. Spellman, David C. Wedge, PCAWG Evolution & Heterogeneity Working Group, and PCAWG Consortium. The evolutionary history of 2,658 cancers. Nature, 578(7793):122-128, 2020. URL: https://doi.org/10.1038/s41586-019-1907-7.
  17. Gavin Ha, Andrew Roth, Jaswinder Khattra, Julie Ho, Damian Yap, Leah M Prentice, Nataliya Melnyk, Andrew McPherson, Ali Bashashati, Emma Laks, et al. Titan: inference of copy number architectures in clonal cell populations from tumor whole-genome sequence data. Genome research, 24(11):1881-1893, 2014. Google Scholar
  18. Sridhar Hannenhalli and Pavel A Pevzner. Transforming cabbage into turnip. In Proc. Annual ACM Symposium on the Theory of Computing, volume 46, pages 178-189, New York, New York, USA, 1995. URL: https://doi.org/10.1145/225058.225112.
  19. Sridhar Hannenhalli and Pavel A Pevzner. Transforming men into mice (polynomial algorithm for genomic distance problem). In Proc. IEEE Symposium on Foundations of Computer Science, volume 36, pages 581-592, 1995. URL: https://doi.org/10.1109/SFCS.1995.492588.
  20. Jun Inoue, Yukuto Sato, Robert Sinclair, Katsumi Tsukamoto, and Mutsumi Nishida. Rapid genome reshaping by multiple-gene loss after whole-genome duplication in teleost fish suggested by mathematical modeling. Proceedings of the National Academy of Sciences, 112(48):14918-14923, 2015. URL: https://doi.org/10.1073/pnas.1507669112.
  21. Olivier Jaillon, Jean-Marc Aury, Frédéric Brunet, Jean-Louis Petit, Nicole Stange-Thomann, Evan Mauceli, Laurence Bouneau, Cécile Fischer, Catherine Ozouf-Costaz, Alain Bernot, et al. Genome duplication in the teleost fish tetraodon nigroviridis reveals the early vertebrate proto-karyotype. Nature, 431(7011):946-957, 2004. Google Scholar
  22. Jakub Kováč. On the complexity of rearrangement problems under the breakpoint distance. Journal of Computational Biology, 21(1):1-15, 2014. URL: https://doi.org/10.1089/cmb.2013.0004.
  23. Yilong Li, Nicola D. Roberts, Jeremiah A. Wala, Ofer Shapira, Steven E. Schumacher, Kiran Kumar, Ekta Khurana, Sebastian Waszak, Jan O. Korbel, James E. Haber, Marcin Imielinski, Kadir C. Akdemir, Eva G. Alvarez, Adrian Baez-Ortega, Rameen Beroukhim, Paul C. Boutros, David D. L. Bowtell, Benedikt Brors, Kathleen H. Burns, Peter J. Campbell, Kin Chan, Ken Chen, Isidro Cortés-Ciriano, Ana Dueso-Barroso, Andrew J. Dunford, Paul A. Edwards, Xavier Estivill, Dariush Etemadmoghadam, Lars Feuerbach, J. Lynn Fink, Milana Frenkel-Morgenstern, Dale W. Garsed, Mark Gerstein, Dmitry A. Gordenin, David Haan, James E. Haber, Julian M. Hess, Barbara Hutter, David T. W. Jones, Young Seok Ju, Marat D. Kazanov, Leszek J. Klimczak, Youngil Koh, Jan O. Korbel, Eunjung Alice Lee, Jake June-Koo Lee, Andy G. Lynch, Geoff Macintyre, Florian Markowetz, Iñigo Martincorena, Alexander Martinez-Fundichely, Matthew Meyerson, Satoru Miyano, Hidewaki Nakagawa, Fabio C. P. Navarro, Stephan Ossowski, Peter J. Park, John V. Pearson, Montserrat Puiggròs, Karsten Rippe, Nicola D. Roberts, Steven A. Roberts, Bernardo Rodriguez-Martin, Steven E. Schumacher, Ralph Scully, Mark Shackleton, Nikos Sidiropoulos, Lina Sieverling, Chip Stewart, David Torrents, Jose M. C. Tubio, Izar Villasante, Nicola Waddell, Jeremiah A. Wala, Joachim Weischenfeldt, Lixing Yang, Xiaotong Yao, Sung-Soo Yoon, Jorge Zamora, Cheng-Zhong Zhang, Peter J. Campbell, PCAWG Structural Variation Working Group, and PCAWG Consortium. Patterns of somatic structural variation in human cancer genomes. Nature, 578(7793):112-121, 2020. URL: https://doi.org/10.1038/s41586-019-1913-9.
  24. Stefano Mangiola, Matthew KH Hong, Marek Cmero, Natalie Kurganovs, Andrew Ryan, Anthony J Costello, Niall M Corcoran, Geoff Macintyre, and Christopher M Hovens. Comparing nodal versus bony metastatic spread using tumour phylogenies. Scientific reports, 6:33918, 2016. Google Scholar
  25. Julia Mixtacki. Genome halving under DCJ revisited. In Xiaodong Hu and Jie Wang, editors, Proc. Computing and Combinatorics, volume 5092 of Lecture Notes in Computer Science, pages 276-286. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-69733-6.
  26. Serena Nik-Zainal, Peter Van Loo, David C Wedge, Ludmil B Alexandrov, Christopher D Greenman, King Wai Lau, Keiran Raine, David Jones, John Marshall, Manasa Ramakrishna, et al. The life history of 21 breast cancers. Cell, 149(5):994-1007, 2012. Google Scholar
  27. Layla Oesper, Ahmad Mahmoody, and Benjamin J Raphael. Theta: inferring intra-tumor heterogeneity from high-throughput dna sequencing data. Genome biology, 14(7):R80, 2013. Google Scholar
  28. J D Palmer and L A Herbon. Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. Journal of Molecular Evolution, 28(1-2):87-97, 1988. URL: http://www.ncbi.nlm.nih.gov/pubmed/3148746.
  29. Alexandre Pelé, Mathieu Rousseau-Gueutin, and Anne-Marie Chèvre. Speciation success of polyploid plants closely relates to the regulation of meiotic recombination. Frontiers in Plant Science, 9:907, 2018. URL: https://doi.org/10.3389/fpls.2018.00907.
  30. Marina Petkovic, Thomas BK Watkins, Emma C Colliver, Sofya Laskina, Charles Swanton, Kerstin Haase, and Roland F Schwarz. Whole-genome doubling-aware copy number phylogenies for cancer evolution with medicc2. bioRxiv, 2021. URL: https://doi.org/10.1101/2021.02.28.433227.
  31. Pavel Pevzner and Glenn Tesler. Transforming men into mice. In Proc. Seventh annual international conference on Research in Computational Molecular Biology, pages 247-256, New York, New York, USA, 2003. ACM Press. URL: https://doi.org/10.1145/640075.640108.
  32. David Sankoff and Mathieu Blanchette. Multiple genome rearrangement and breakpoint phylogeny. Journal of computational biology, 5(3):555-570, 1998. Google Scholar
  33. Roland F Schwarz, Charlotte KY Ng, Susanna L Cooke, Scott Newman, Jillian Temple, Anna M Piskorz, Davina Gale, Karen Sayal, Muhammed Murtaza, Peter J Baldwin, et al. Spatial and temporal heterogeneity in high-grade serous ovarian cancer: a phylogenetic analysis. PLoS medicine, 12(2):e1001789, 2015. Google Scholar
  34. 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, 2014. Google Scholar
  35. Ronglai Shen and Venkatraman E Seshan. Facets: allele-specific copy number and clonal heterogeneity analysis tool for high-throughput dna sequencing. Nucleic acids research, 44(16):e131-e131, 2016. Google Scholar
  36. Andrea Sottoriva, Haeyoun Kang, Zhicheng Ma, Trevor A Graham, Matthew P Salomon, Junsong Zhao, Paul Marjoram, Kimberly Siegmund, Michael F Press, Darryl Shibata, et al. A big bang model of human colorectal tumor growth. Nature genetics, 47(3):209, 2015. Google Scholar
  37. Steven H Strauss, Jeffrey D Palmer, Glen T Howe, and Allan H Doerksen. Chloroplast genomes of two conifers lack a large inverted repeat and are extensively rearranged. Proceedings of the National Academy of Sciences, 85(11):3898-3902, 1988. Google Scholar
  38. Alfred H Sturtevant and Th Dobzhansky. Inversions in the third chromosome of wild races of drosophila pseudoobscura, and their use in the study of the history of the species. Proceedings of the National Academy of Sciences, 22(7):448-450, 1936. Google Scholar
  39. Eric Tannier, Chunfang Zheng, and David Sankoff. Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics, 10(1):120, 2009. URL: https://doi.org/10.1186/1471-2105-10-120.
  40. Robert Warren and David Sankoff. Genome halving with double cut and join. Journal of Computational Biology, 7(2):357-371, 2009. Google Scholar
  41. Robert Warren and David Sankoff. Genome aliquoting revisited. Journal of Computational Biology, 18(9):1065-1075, 2011. URL: http://online.liebertpub.com/doi/abs/10.1089/cmb.2011.0087.
  42. Kenneth H. Wolfe and Denis C. Shields. Molecular evidence for an ancient duplication of the entire yeast genome. Nature, 387:708 EP-, 1997. URL: https://doi.org/10.1038/42711.
  43. Sophia Yancopoulos, Oliver Attie, and Richard Friedberg. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21(16):3340-3346, 2005. URL: https://doi.org/10.1093/bioinformatics/bti535.
  44. Simone Zaccaria, Mohammed El-Kebir, Gunnar W. Klau, and Benjamin J. Raphael. Phylogenetic copy-number factorization of multiple tumor samples. Journal of Computational Biology, 25(7):689-708, 2018. PMID: 29658782. URL: https://doi.org/10.1089/cmb.2017.0253.
  45. Travis I Zack, Steven E Schumacher, Scott L Carter, Andrew D Cherniack, Gordon Saksena, Barbara Tabak, Michael S Lawrence, Cheng-Zhong Zhang, Jeremiah Wala, Craig H Mermel, et al. Pan-cancer patterns of somatic copy number alteration. Nature genetics, 45(10):1134, 2013. Google Scholar
  46. Ron Zeira, Meirav Zehavi, and Ron Shamir. A linear-time algorithm for the copy number transformation problem. Journal of Computational Biology, 24(12):1179-1194, 2017. Google Scholar
  47. Chunfang Zheng, Qian Zhu, Zaky Adam, and David Sankoff. Guided genome halving: hardness, heuristics and the history of the hemiascomycetes. Bioinformatics (Oxford, England), 24(13):i96-i104, July 2008. URL: https://doi.org/10.1093/bioinformatics/btn146.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact