{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T01:14:27Z","timestamp":1750122867605,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031491894"},{"type":"electronic","value":"9783031491900"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49190-0_1","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"3-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity and\u00a0Enumeration in\u00a0Models of\u00a0Genome Rearrangement"],"prefix":"10.1007","author":[{"given":"Lora","family":"Bailey","sequence":"first","affiliation":[]},{"given":"Heather Smith","family":"Blake","sequence":"additional","affiliation":[]},{"given":"Garner","family":"Cochran","sequence":"additional","affiliation":[]},{"given":"Nathan","family":"Fox","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Levet","sequence":"additional","affiliation":[]},{"given":"Reem","family":"Mahmoud","sequence":"additional","affiliation":[]},{"given":"Elizabeth Bailey","family":"Matson","sequence":"additional","affiliation":[]},{"given":"Inne","family":"Singgih","sequence":"additional","affiliation":[]},{"given":"Grace","family":"Stadnyk","sequence":"additional","affiliation":[]},{"given":"Xinyi","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wiedemann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/3-540-45784-4_23","volume-title":"Algorithms in Bioinformatics","author":"Y Ajana","year":"2002","unstructured":"Ajana, Y., Jean-Fran\u00e7ois, L., Tillier, E.R.M., El-Mabrouk, N.: Exploring the set of all minimal sequences of reversals\u2014an application to test the replication-directed reversal hypothesis. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol. 2452, pp. 300\u2013315. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45784-4_23"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Alekseyev, M.A., Pevzner, P.A.: Comparative genomics reveals birth and death of fragile regions in mammalian evolution. Genome Biol. 11(11), R117 (2010)","DOI":"10.1186\/gb-2010-11-11-r117"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Bergeron, A., Medvedev, P., Stoye, J.: Rearrangement models and single-cut operations. J. Comput. Biol. J. Comput. Mol. Cell Biol. 17, 1213\u20131225 (2010)","DOI":"10.1089\/cmb.2010.0091"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms in Bioinformatics","author":"A Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS, vol. 4175, pp. 163\u2013173. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11851561_16"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-540-87989-3_17","volume-title":"Comparative Genomics","author":"A Bergeron","year":"2008","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: On computing the breakpoint reuse rate in rearrangement scenarios. In: Nelson, C.E., Vialette, S. (eds.) RECOMB-CG 2008. LNCS, vol. 5267, pp. 226\u2013240. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87989-3_17"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Bailey, L., et al.: Complexity and Enumeration in Models of Genome Rearrangement. arXiv:2305.01851 (2023)","DOI":"10.1007\/978-3-031-49190-0_1"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Formulations and hardness of multiple sorting by reversals. In: Proceedings of the Third Annual International Conference on Computational Molecular Biology, RECOMB 1999, pp. 84\u201393. Association for Computing Machinery, New York, NY, USA (1999)","DOI":"10.1145\/299432.299461"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Darling, A., Mikl\u00f3s, I., Ragan, M.: Dynamics of genome rearrangement in bacterial populations. PLoS Genet. 4, e1000128 (2008)","DOI":"10.1371\/journal.pgen.1000128"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Durrett, R., Nielsen, R., York, T.: Bayesian estimation of genomic distance. Genetics 166, 621\u2013629 (2004)","DOI":"10.1534\/genetics.166.1.621"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Feij\u00e3o, P., Meidanis, J.: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE\/ACM Trans. Comput. Biol. Bioinf. 8, 1318\u20131329 (2011)","DOI":"10.1109\/TCBB.2011.34"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 581\u2013592 (1995)","DOI":"10.1109\/SFCS.1995.492588"},{"issue":"1","key":"1_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46(1), 1\u201327 (1999)","journal-title":"J. ACM"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Larget, B., Simon, D.L., Kadane, J.B., Sweet, D.: A Bayesian analysis of metazoan mitochondrial genome arrangements. Mol. Biol. Evol. 22(3), 486\u2013495 (2004)","DOI":"10.1093\/molbev\/msi032"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"McClintock, B.: Chromosome organization and genic expression. In: Cold Spring Harbor Symposia on Quantitative Biology, vol. 16, pp. 13\u201347. Cold Spring Harbor Laboratory Press (1951)","DOI":"10.1101\/SQB.1951.016.01.004"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2014.07.027","volume":"552","author":"I Mikl\u00f3s","year":"2014","unstructured":"Mikl\u00f3s, I., Kiss, S.Z., Tannier, E.: Counting and sampling SCJ small parsimony solutions. Theor. Comput. Sci. 552, 83\u201398 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s, I., Smith, H.: Sampling and counting genome rearrangement scenarios. BMC Bioinf. 16, S6 (2015)","DOI":"10.1186\/1471-2105-16-S14-S6"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.aam.2018.09.002","volume":"102","author":"I Mikl\u00f3s","year":"2019","unstructured":"Mikl\u00f3s, I., Smith, H.: The computational complexity of calculating partition functions of optimal medians with hamming distance. Adv. Appl. Math. 102, 18\u201382 (2019)","journal-title":"Adv. Appl. Math."},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s, I., Tannier, E.: Bayesian sampling of genomic rearrangement scenarios via double cut and join. Bioinformatics 26(24), 3012\u20133019 (2010)","DOI":"10.1093\/bioinformatics\/btq574"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2012.03.006","volume":"439","author":"I Mikl\u00f3s","year":"2012","unstructured":"Mikl\u00f3s, I., Tannier, E.: Approximating the number of double cut-and-join scenarios. Theoret. Comput. Sci. 439, 30\u201340 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Palmer, J.D., Herbon, L.A.: Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. J. Mol. Evol. 28, 87\u201397 (1988)","DOI":"10.1007\/BF02143500"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Raphael, B., Pevzner, P.: Reconstructing tumor amplisomes. Bioinformatics (Oxford, England) 20(Suppl 1), i265\u201373 (2004)","DOI":"10.1093\/bioinformatics\/bth931"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008)","DOI":"10.1145\/1391289.1391291"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/3-540-08342-1_37","volume-title":"Automata, Languages and Programming","author":"J Simon","year":"1977","unstructured":"Simon, J.: On the difference between one and many. In: Salomaa, A., Steinby, M. (eds.) ICALP 1977. LNCS, vol. 52, pp. 480\u2013491. Springer, Heidelberg (1977). https:\/\/doi.org\/10.1007\/3-540-08342-1_37"},{"issue":"1","key":"1_CR25","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/jez.1400140104","volume":"14","author":"AH Sturtevant","year":"1913","unstructured":"Sturtevant, A.H.: The linear arrangement of six sex-linked factors in drosophila, as shown by their mode of association. J. Exp. Zool. 14(1), 43\u201359 (1913)","journal-title":"J. Exp. Zool."},{"issue":"9","key":"1_CR26","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1073\/pnas.3.9.555","volume":"3","author":"AH Sturtevant","year":"1917","unstructured":"Sturtevant, A.H.: Genetic factors affecting the strength of linkage in drosophila. Proc. Natl. Acad. Sci. U.S.A. 3(9), 555\u2013558 (1917)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"1_CR27","unstructured":"Sturtevant, A.H.: Known and probably inverted sections of the autosomes of Drosophila melanogaster. Carnegie Inst. Washington Publisher 421, 1\u201327 (1931)"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Sturtevant, A.H., Novitski, E.: The homologies of the chromosome elements in the genus drosophila. Genetics 26(5), 517\u2013541 (1941)","DOI":"10.1093\/genetics\/26.5.517"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Tannier, C.Z., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinf. 10, 120 (2009)","DOI":"10.1186\/1471-2105-10-120"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics (Oxford, England) 21, 3340\u20133346 (2005)","DOI":"10.1093\/bioinformatics\/bti535"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49190-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T16:28:16Z","timestamp":1730824096000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49190-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491894","9783031491900"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49190-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}