{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T12:10:37Z","timestamp":1648642237923},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2016,2]]},"abstract":"<jats:p> We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement operations. Recently, Hao et\u00a0al. gave a 2-approximation scheme called genome sorting by bridges (GSB) for solving this problem. Their result extended and unified the results of (i) He and Chen\u00a0\u2014 a 2-approximation algorithm allowing reversals, transpositions, and block-interchanges (by also allowing transversals) and (ii) Hartman and Sharan\u00a0\u2014 a 1.5-approximation algorithm allowing reversals, transpositions, and transversals (by also allowing block-interchanges). The GSB result is based on introduction of three bridge structures in the breakpoint graph, the L-bridge, T-bridge, and X-bridge that models goodreversal, transposition\/transreversal, and block-interchange, respectively. However, the paper by Hao et\u00a0al. focused on proving the 2-approximation GSB scheme and only mention a straightforward [Formula: see text] algorithm. In this paper, we give an [Formula: see text] algorithm for implementing the GSB scheme. The key idea behind our faster GSB algorithm is to represent cycles in the breakpoint graph by their canonical sequences, which greatly simplifies the search for these bridge structures. We also give some comparison results (running time and computed distances) against the original GSB implementation. <\/jats:p>","DOI":"10.1142\/s0219720016400023","type":"journal-article","created":{"date-parts":[[2015,11,23]],"date-time":"2015-11-23T22:16:58Z","timestamp":1448317018000},"page":"1640002","source":"Crossref","is-referenced-by-count":3,"title":["An O(n3) algorithm for sorting signed genomes by reversals, transpositions, transreversals and block-interchanges"],"prefix":"10.1142","volume":"14","author":[{"given":"Shuzhi","family":"Yu","sequence":"first","affiliation":[{"name":"Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore 117417, Republic of Singapore"}]},{"given":"Fanchang","family":"Hao","sequence":"additional","affiliation":[{"name":"School of Information and Key Laboratory of Evidence-Identifying in Universities of Shandong, Shandong University of Political Science and Law, Jinan, Shandong 250014, P. R. China"}]},{"given":"Hon Wai","family":"Leong","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore 117417, Republic of Singapore"}]}],"member":"219","published-online":{"date-parts":[[2016,2,24]]},"reference":[{"key":"S0219720016400023BIB001","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0025"},{"key":"S0219720016400023BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58094-8_26"},{"key":"S0219720016400023BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"key":"S0219720016400023BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"S0219720016400023BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.04.010"},{"key":"S0219720016400023BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798334207"},{"key":"S0219720016400023BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00155-X"},{"key":"S0219720016400023BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44888-8_12"},{"key":"S0219720016400023BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02946661"},{"key":"S0219720016400023BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"S0219720016400023BIB012","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-S1-S27"},{"key":"S0219720016400023BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720016400023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:26:25Z","timestamp":1565105185000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720016400023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2016,2,24]]},"published-print":{"date-parts":[[2016,2]]}},"alternative-id":["10.1142\/S0219720016400023"],"URL":"https:\/\/doi.org\/10.1142\/s0219720016400023","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2]]}}}