{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:00Z","timestamp":1759638960582},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The double cut and join operation (abbreviated as DCJ) has been extensively used for genomic rearrangement. Although the DCJ distance between signed genomes with both linear and circular (uni- and multi-) chromosomes is well studied, the only known result for the NP-complete unsigned DCJ distance problem is an approximation algorithm for unsigned linear unichromosomal genomes. In this article, we study the problem of computing the DCJ distance on two unsigned linear multichromosomal genomes (abbreviated as UDCJ).<\/jats:p>\n               <jats:p>Results: We devise a 1.5-approximation algorithm for UDCJ by exploiting the distance formula for signed genomes. In addition, we show that UDCJ admits a weak kernel of size 2k and hence an FPT algorithm running in O(22kn) time.<\/jats:p>\n               <jats:p>Contact: \u00a0bhz@cs.montana.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq674","type":"journal-article","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T04:48:21Z","timestamp":1291697301000},"page":"311-316","source":"Crossref","is-referenced-by-count":15,"title":["Algorithms for sorting unsigned linear genomes by the DCJ operations"],"prefix":"10.1093","volume":"27","author":[{"given":"Haitao","family":"Jiang","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, Montana State University, Bozeman, MT 59717, USA and 2School of Computer Science and Technology, Shandong University, Jinan, China"},{"name":"1 Department of Computer Science, Montana State University, Bozeman, MT 59717, USA and 2School of Computer Science and Technology, Shandong University, Jinan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Montana State University, Bozeman, MT 59717, USA and 2School of Computer Science and Technology, Shandong University, Jinan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, Montana State University, Bozeman, MT 59717, USA and 2School of Computer Science and Technology, Shandong University, Jinan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2010,12,6]]},"reference":[{"key":"2023012511554212600_B1","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","article-title":"Sorting by Transpositions","volume":"11","author":"Bafna","year":"1998","journal-title":"SIAM J. Discrete Math."},{"key":"2023012511554212600_B2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/11851561_16","article-title":"A unifying view of genome rearrangements","volume-title":"Proceedings of the 6th International Workshop on Algorithms in Bioinformatics (WABI\u203206)","author":"Bergeron","year":"2006"},{"key":"2023012511554212600_B3","first-page":"200","article-title":"1.375-Approximation algorithm for sorting by reversals","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02)","author":"Berman","year":"2002"},{"key":"2023012511554212600_B4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S089548019731994X","article-title":"Sorting permutations by reversals and Eulerian cycle decompositions","volume":"12","author":"Caprara","year":"1999","journal-title":"SIAM J. Discrete Math."},{"key":"2023012511554212600_B5","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-3-642-14031-0_47","article-title":"On sorting permutations by double-cut-and-joins","volume-title":"Proceedings of the 16th International Conf. on Computing and Combinatorics (COCOON'10)","author":"Chen","year":"2010"},{"key":"2023012511554212600_B6","first-page":"244","article-title":"A 3\/2-Approximation algorithm for sorting by reversals","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98)","author":"Christie","year":"1998"},{"key":"2023012511554212600_B7","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/TCBB.2007.70216","article-title":"A (1.5 + \u03f5)-Approximation algorithm for unsigned translocation distance","volume":"5","author":"Cui","year":"2008","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012511554212600_B8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"2023012511554212600_B9","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/TCBB.2006.44","article-title":"A 1.375-Approximation algorithm for sorting by transpositions","volume":"3","author":"Elias","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012511554212600_B10","volume-title":"Parameterized Complexity Theory.","author":"Flum","year":"2006"},{"key":"2023012511554212600_B11","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0215009","article-title":"An O(EVlog V) algorithm for finding a maximal weighted matching in general graphs","volume":"15","author":"Galil","year":"1986","journal-title":"SIAM J. Comput."},{"key":"2023012511554212600_B12","first-page":"581","article-title":"Transforming men into mice (polynomial algorithm for genomic distance problem)","volume-title":"Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS'95)","author":"Hannenhalli","year":"1995"},{"key":"2023012511554212600_B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","article-title":"Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals","volume":"46","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"key":"2023012511554212600_B14","first-page":"TR10","article-title":"Weak kernels","author":"Jiang","year":"2010","journal-title":"ECCC Report"},{"key":"2023012511554212600_B15","article-title":"A 14\/11-Approximation algorithm for sorting by short block-moves","author":"Jiang","year":"2011","journal-title":"Science in China Series F."},{"key":"2023012511554212600_B16","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/3\/311\/48867438\/bioinformatics_27_3_311.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/3\/311\/48867438\/bioinformatics_27_3_311.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:24:28Z","timestamp":1674649468000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/3\/311\/321669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,6]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq674","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2011,2,1]]},"published":{"date-parts":[[2010,12,6]]}}}