{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:23Z","timestamp":1740122423400,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T00:00:00Z","timestamp":1535673600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472222"],"award-info":[{"award-number":["61472222"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Natural Science Foundation of China (CN)","award":["61672323"],"award-info":[{"award-number":["61672323"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61732009"],"award-info":[{"award-number":["61732009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Natural Science Foundation of China (CN)","award":["61761136017"],"award-info":[{"award-number":["61761136017"]}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2016AM28"],"award-info":[{"award-number":["ZR2016AM28"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Office of the Vice President for Research & Economic Development at Georgia Southern University"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10878-018-0346-y","type":"journal-article","created":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T07:12:16Z","timestamp":1535699536000},"page":"1170-1190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An approximation algorithm for genome sorting by reversals to recover all adjacencies"],"prefix":"10.1007","volume":"37","author":[{"given":"Shanshan","family":"Zhai","sequence":"first","affiliation":[]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Weitian","family":"Tong","sequence":"additional","affiliation":[]},{"given":"Yao","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,31]]},"reference":[{"key":"346_CR1","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V Bafna","year":"1996","unstructured":"Bafna V, Pevzner PA (1996) Genome rearrangements and sorting by reversals. SIAM J Comput 25:272\u2013289","journal-title":"SIAM J Comput"},{"key":"346_CR2","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA (1998) Sorting by transpositions. SIAM J Discrete Math 11:224\u2013240","journal-title":"SIAM J Discrete Math"},{"key":"346_CR3","unstructured":"Berman P, Hannenhalli S, Karpinski M (2002) \n                    \n                      \n                    \n                    $$1.375$$\n                    \n                      \n                        \n                          1.375\n                        \n                      \n                    \n                  -approximation algorithm for sorting by reversals. In: Proceedings of the 10th annual European symposium on algorithms (ESA\u201902), pp 200\u2013210"},{"key":"346_CR4","doi-asserted-by":"crossref","unstructured":"Berman P, Karpinski M (1999) On some tighter inapproximability results. In: Proceedings of the of 26th international colloquium on automata, languages and programming (ICALP\u201999), pp 200\u2013209","DOI":"10.1007\/3-540-48523-6_17"},{"key":"346_CR5","doi-asserted-by":"crossref","unstructured":"Caprara A (1997) Sorting by reversals is difficult. In: Proceedings of the first annual international conference on computational molecular biology, pp 75\u201383","DOI":"10.1145\/267521.267531"},{"key":"346_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.02.017","volume":"530","author":"W Chen","year":"2014","unstructured":"Chen W, Chen Z, Samatova NF, Peng L, Wang J, Tang M (2014) Solving the maximum duo-preservation string mapping problem with linear programming. Theor Comput Sci 530:1\u201311","journal-title":"Theor Comput Sci"},{"key":"346_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","volume":"60","author":"DA Christie","year":"1996","unstructured":"Christie DA (1996) Sorting permutations by block-interchanges. Inf Process Lett 60:165\u2013169","journal-title":"Inf Process Lett"},{"key":"346_CR8","unstructured":"Christie DA (1998) A \n                    \n                      \n                    \n                    $$3\/2$$\n                    \n                      \n                        \n                          3\n                          \/\n                          2\n                        \n                      \n                    \n                   approximation algorithm for sorting by reversals. In: ACM-SIAM proceedings of the ninth annual symposium on discrete algorithms (SODA\u201998), pp 244\u2013252"},{"key":"346_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/S0895480197331995","volume":"14","author":"DA Christie","year":"2001","unstructured":"Christie DA, Irving RW (2001) Sorting strings by reversals and by transpositions. SIAM J Discrete Math 14:193\u2013206","journal-title":"SIAM J Discrete Math"},{"key":"346_CR10","doi-asserted-by":"crossref","unstructured":"Chrobak M, Kolman P, Sgall J (2004) The greedy algorithm for the minimum common string partition problem. In: Proceedings of the 7th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2004) and the 8th international workshop on randomization and computation (RANDOM 2004), LNCS 3122, pp 84\u201395","DOI":"10.1007\/978-3-540-27821-4_8"},{"key":"346_CR11","doi-asserted-by":"crossref","unstructured":"Goldstein A, Kolman P, Zheng J (2004) Minimum common string partition problem: hardness and approximations. In: Proceedings of the 15th international symposium on algorithms and computation (ISAAC 2004), LNCS 3341, pp 484\u2013495","DOI":"10.1007\/978-3-540-30551-4_43"},{"key":"346_CR12","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0304-3975(98)00092-9","volume":"210","author":"Q-P Gu","year":"1999","unstructured":"Gu Q-P, Peng S, Sudborough H (1999) A \n                    \n                      \n                    \n                    $$2$$\n                    \n                      \n                        \n                          2\n                        \n                      \n                    \n                  -approximation algorithm for genome rearrangements by reversals and transpositions. Theor Comput Sci 210:327\u2013339","journal-title":"Theor Comput Sci"},{"key":"346_CR13","doi-asserted-by":"crossref","unstructured":"Hannenhalli S, Pevzner P (1995) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In: ACM proceedings of the 27th annual symposium on the theory of computing (STOC\u201995), pp 178\u2013189","DOI":"10.1145\/225058.225112"},{"key":"346_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"MR Jerrum","year":"1985","unstructured":"Jerrum MR (1985) The complexity of finding minimum-length generator sequences. Theor Comput Sci 36:265\u2013289","journal-title":"Theor Comput Sci"},{"key":"346_CR15","unstructured":"Kececioglu JD, Sankoff D (1993) Exact and approximation algorithms for the inversion distance between two permutations. In: Proceedings of the fourth annual symposium on combinatorial pattern matching (CPM\u201993), LNCS 684, pp 87\u2013105"},{"key":"346_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.dam.2006.05.011","volume":"155","author":"P Kolman","year":"2007","unstructured":"Kolman P, Wale\u0144 T (2007) Approximating reversal distance for strings with bounded number of duplicates. Discrete Appl Math 155:327\u2013336","journal-title":"Discrete Appl Math"},{"key":"346_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-017-0095-y","volume":"12","author":"DP Rubert","year":"2017","unstructured":"Rubert DP, Feij\u00e3o P, Braga MDV, Stoye J, Martinez FHV (2017) Approximating the DCJ distance of balanced genomes in linear time. Algorithms Mol Biol 12:3","journal-title":"Algorithms Mol Biol"},{"key":"346_CR18","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"16","author":"D Sankoff","year":"1999","unstructured":"Sankoff D (1999) Genome rearrangement with gene families. Bioinformatics 16:909\u2013917","journal-title":"Bioinformatics"},{"key":"346_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"G Watterson","year":"1982","unstructured":"Watterson G, Ewens W, Hall T, Morgan A (1982) The chromosome inversion problem. J Theor Biol 99:1\u20137","journal-title":"J Theor Biol"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0346-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0346-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0346-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T14:45:23Z","timestamp":1569249923000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0346-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,31]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["346"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0346-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,8,31]]},"assertion":[{"value":"31 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}