{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:07:21Z","timestamp":1786979241518,"version":"build-2736575974"},"publisher-location":"Singapore","reference-count":19,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819610891","type":"print"},{"value":"9789819610907","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_1","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:32:31Z","timestamp":1741105951000},"page":"3-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Can the\u00a01.375 Approximation Ratio of\u00a0Unsigned Genomes Distances be Improved?"],"prefix":"10.1007","author":[{"given":"Chengcheng","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haitao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1023\/A:1013851611274","volume":"6","author":"RR Alberto Caprara","year":"2002","unstructured":"Alberto Caprara, R.R.: Improved approximation for breakpoint graph decomposition and sorting by reversals. J. Comb. Optim. 6(2), 157\u2013182 (2002)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1_CR2","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discret. Math. 11(2), 224\u2013240 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: Proceedings of the 6th International Workshop on Algorithms in Bioinformatics, WABI, pp. 163\u2013173 (2006)","DOI":"10.1007\/11851561_16"},{"issue":"2","key":"1_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32(2), 115\u2013132 (1999)","journal-title":"Theory Comput. Syst."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45749-6_21","volume-title":"Algorithms \u2014 ESA 2002","author":"P Berman","year":"2002","unstructured":"Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-approximation algorithm for sorting by reversals. In: M\u00f6hring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 200\u2013210. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45749-6_21"},{"issue":"1","key":"1_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A Caprara","year":"1999","unstructured":"Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discret. Math. 12(1), 91\u2013110 (1999)","journal-title":"SIAM J. Discret. Math."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Sun, R., Yu, J.: Approximating the double-cut-and-join distance between unsigned genomes. BMC Bioinform. 12(S-9), S17 (2011)","DOI":"10.1186\/1471-2105-12-S9-S17"},{"key":"1_CR8","unstructured":"Christie, D.A.: A 3\/2-approximation algorithm for sorting by reversals. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 244\u2013252 (1998)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Cui, Y., Wang, L., Zhu, D., Liu, X.: A (1.5 + $$\\epsilon $$)-approximation algorithm for unsigned translocation distance. IEEE\/ACM Trans. Comput. Biol. Bioinform. 5(1), 56\u201366 (2008)","DOI":"10.1109\/TCBB.2007.70216"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(4), 369\u2013379 (2006)","DOI":"10.1109\/TCBB.2006.44"},{"key":"1_CR11","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 160\u2013169 (1995)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 581\u2013592 (1995)","DOI":"10.1109\/SFCS.1995.492588"},{"issue":"1","key":"1_CR13","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_CR14","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, L., Zhu, B., Zhu, D.: A factor-(1.408 + $$\\varepsilon $$) approximation for sorting unsigned genomes by reciprocal translocations. Theor. Comput. Sci. 607(2), 166\u2013180 (2015)","DOI":"10.1016\/j.tcs.2015.04.036"},{"issue":"3","key":"1_CR15","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1093\/bioinformatics\/btq674","volume":"27","author":"H Jiang","year":"2011","unstructured":"Jiang, H., Zhu, B., Zhu, D.: Algorithms for sorting unsigned linear genomes by the DCJ operations. Bioinformatics 27(3), 311\u2013316 (2011)","journal-title":"Bioinformatics"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Pu, L., Zhu, D., Jiang:, H.: A 1.375-approximation algorithm for unsigned translocation sorting. J. Comput. Syst. Sci. 113, 163\u2013178 (2020)","DOI":"10.1016\/j.jcss.2020.05.004"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Sankoff, D.: Edit distances for genome comparisons based on non-local operations. In: Combinatorial Pattern Matching, Third Annual Symposium, CPM 1992, pp. 121\u2013135 (1992)","DOI":"10.1007\/3-540-56024-6_10"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Tannier, E., Sagot, M.F.: Sorting by reversals in subquadratic time. In: CPM, pp. 1\u201313 (2004)","DOI":"10.1007\/978-3-540-27801-6_1"},{"issue":"16","key":"1_CR19","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"}],"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-981-96-1090-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T07:11:30Z","timestamp":1757142690000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","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":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}