{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T11:44:06Z","timestamp":1785930246330,"version":"3.56.0"},"publisher-location":"Singapore","reference-count":17,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819502141","type":"print"},{"value":"9789819502158","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_5","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:13Z","timestamp":1753979113000},"page":"54-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Randomized FPT Approximation Algorithm for\u00a0Sorting Unsigned Genomes by\u00a0Translocations: Breaking the\u00a01.375 Approximation Barrier"],"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":"Guojun","family":"Li","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,8,1]]},"reference":[{"issue":"2","key":"5_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1089\/cmb.2006.13.567","volume":"13","author":"A Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: On sorting by translocations. J. Comput. Biol. 13(2), 567\u2013578 (2006)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"5_CR2","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":"5_CR3","doi-asserted-by":"crossref","unstructured":"Cui, Y., Wang, L., Zhu, D.: A 1.75-approximation algorithm for unsigned translocation distance. J. Comput. Syst. Sci. 73(7), 1045\u20131059 (2007)","DOI":"10.1016\/j.jcss.2007.03.009"},{"key":"5_CR4","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"},{"issue":"1\u20133","key":"5_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0166-218X(96)00061-3","volume":"71","author":"S Hannenhalli","year":"1996","unstructured":"Hannenhalli, S.: Polynomial-time algorithm for computing translocation distance between genomes. Discret. Appl. Math. 71(1\u20133), 137\u2013151 (1996)","journal-title":"Discret. Appl. Math."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Jiang, H., Pu, L., Qingge, L., Sankoff, D., Zhu:, B.: A randomized fpt approximation algorithm for maximum alternating-cycle decomposition with applications. In: International Computing and Combinatorics Conference (COCOON), pp. 26\u201338 (2018)","DOI":"10.1007\/978-3-319-94776-1_3"},{"key":"5_CR7","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. Theoret. Comput. Sci. 607, 166\u2013180 (2015)","DOI":"10.1016\/j.tcs.2015.04.036"},{"key":"5_CR8","unstructured":"Kececioglu, J.D., Ravi, R.: Of mice and men: algorithms for evolutionary distances between genomes with translocation. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 604\u2013613 (1995)"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Li, G., Qi, X., Wang, X., Zhu, B.: A linear-time algorithm for computing translocation distance between signed genomes. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 323\u2013332. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27801-6_24","DOI":"10.1007\/978-3-540-27801-6_24"},{"issue":"4","key":"5_CR10","first-page":"344","volume":"9","author":"M Ozery-Flato","year":"2011","unstructured":"Ozery-Flato, M., Shamir, R.: An $${O}(n^\\frac{3}{2}\\sqrt{logn})$$ algorithm for sorting by reciprocal translocations. J. Dis. Algor. 9(4), 344\u2013357 (2011)","journal-title":"J. Dis. Algor."},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1101\/gr.757503","volume":"13","author":"P Pevzner","year":"2003","unstructured":"Pevzner, P., Tesler, G.: Genome rearrangements in mammalian evolution: lessons from human and mouse genomes. Genome Res. 13(1), 37\u201345 (2003)","journal-title":"Genome Res."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Pu, L., Zhu, D., Jiang, H.: A new approximation algorithm for unsigned translocation sorting. In: International Workshop on Algorithms in Bioinformatics (WABI), pp. 269\u2013280 (2016)","DOI":"10.1007\/978-3-319-43681-4_22"},{"issue":"14","key":"5_CR13","doi-asserted-by":"publisher","first-page":"6575","DOI":"10.1073\/pnas.89.14.6575","volume":"89","author":"D Sankoff","year":"1992","unstructured":"Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B.F., Cedergran, R.: Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. 89(14), 6575\u20136579 (1992)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Sankoff, D.: Edit distances for genome comparisons based on non-local operations. In: Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 121\u2013135 (1992)","DOI":"10.1007\/3-540-56024-6_10"},{"issue":"3","key":"5_CR15","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.jcss.2004.12.005","volume":"70","author":"L Wang","year":"2005","unstructured":"Wang, L., Zhu, D., Liu, X., Ma, S.: An $${O}(n^2)$$ algorithm for signed translocation. J. Comput. Syst. Sci. 70(3), 284\u2013299 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"5_CR16","first-page":"189","volume":"25","author":"D Zhu","year":"2002","unstructured":"Zhu, D., Ma, S.: An improved algorithm for the translocation sorting problem of genomes. Chin. J. Comput. 25(2), 189\u2013196 (2002)","journal-title":"Chin. J. Comput."},{"issue":"1\u20133","key":"5_CR17","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.tcs.2005.09.078","volume":"352","author":"D Zhu","year":"2006","unstructured":"Zhu, D., Wang, L.: On the complexity of unsigned translocation distance. Theoret. Comput. Sci. 352(1\u20133), 322\u2013328 (2006)","journal-title":"Theoret. Comput. Sci."}],"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-95-0215-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T10:49:51Z","timestamp":1785926991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 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":"Chengdu","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}