{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:31:47Z","timestamp":1740137507258,"version":"3.37.3"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"name":"the Brazilian Federal Agency for the Support and Evaluation of Graduate Education, CAPES","award":["001"],"award-info":[{"award-number":["001"]}]},{"name":"S\u00e3o Paulo Research Foundation, FAPESP","award":["2015\/11937-9","2017\/12646-3","2017\/16246-0","2017\/16871-1"],"award-info":[{"award-number":["2015\/11937-9","2017\/12646-3","2017\/16246-0","2017\/16871-1"]}]},{"name":"the National Counsel of Technological and Scientific Development, CNPq","award":["400487\/2016-0","425340\/2016-3","131182\/2017-0","304380\/2018-0"],"award-info":[{"award-number":["400487\/2016-0","425340\/2016-3","131182\/2017-0","304380\/2018-0"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2020,4]]},"abstract":"<jats:p> One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species\u2019 genome. When we represent genomes as permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so, the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the cost of that sequence is minimum. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about the lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for five versions of this problem involving reversals and transpositions. We also give bounds for the diameters concerning these problems and provide an improved approximation factor for simple permutations considering transpositions. <\/jats:p>","DOI":"10.1142\/s0219720020500067","type":"journal-article","created":{"date-parts":[[2020,1,31]],"date-time":"2020-01-31T08:31:45Z","timestamp":1580459505000},"page":"2050006","source":"Crossref","is-referenced-by-count":3,"title":["Sorting permutations by fragmentation-weighted operations"],"prefix":"10.1142","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6320-9747","authenticated-orcid":false,"given":"Alexsandro Oliveira","family":"Alexandrino","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas (Unicamp), Campinas, S\u00e3o Paulo 13083-852, Brazil"}]},{"given":"Carla Negri","family":"Lintzmayer","sequence":"additional","affiliation":[{"name":"Center for Mathematics, Computation and Cognition, Federal University of ABC (UFABC), Santo Andr\u00e9, S\u00e3o Paulo 09210-580, Brazil"}]},{"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas (Unicamp), Campinas, S\u00e3o Paulo 13083-852, Brazil"}]}],"member":"219","published-online":{"date-parts":[[2020,4,24]]},"reference":[{"key":"S0219720020500067BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019731994X"},{"issue":"3","key":"S0219720020500067BIB002","first-page":"1148","volume":"26","author":"Bulteau L","year":"2012","journal-title":"SIAM J Comput"},{"key":"S0219720020500067BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_21"},{"key":"S0219720020500067BIB004","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.44"},{"key":"S0219720020500067BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"S0219720020500067BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.1998.712988"},{"key":"S0219720020500067BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.09.002"},{"key":"S0219720020500067BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.028"},{"key":"S0219720020500067BIB009","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2019.0078"},{"key":"S0219720020500067BIB010","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.R006"},{"key":"S0219720020500067BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0378-1119(95)00878-0"},{"key":"S0219720020500067BIB013","first-page":"1","author":"Oliveira AR","year":"2019","journal-title":"J Comput Biol"},{"key":"S0219720020500067BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91938-6_5"},{"key":"S0219720020500067BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9369-8"},{"key":"S0219720020500067BIB016","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700181"},{"key":"S0219720020500067BIB017","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000031419.12290.2b"},{"key":"S0219720020500067BIB018","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"key":"S0219720020500067BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"S0219720020500067BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.045"},{"key":"S0219720020500067BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.059"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720020500067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T03:43:44Z","timestamp":1589427824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720020500067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4]]},"references-count":20,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["10.1142\/S0219720020500067"],"URL":"https:\/\/doi.org\/10.1142\/s0219720020500067","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"type":"print","value":"0219-7200"},{"type":"electronic","value":"1757-6334"}],"subject":[],"published":{"date-parts":[[2020,4]]}}}