{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:38:56Z","timestamp":1740155936124,"version":"3.37.3"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p>Permutation sorting, one of the fundamental steps in pre-processing data for the efficient application of other algorithms, has a long history in mathematical research literature and has numerous applications. Two special-purpose sorting operations are considered in this paper: context directed swap, (cds) and context directed reversal, (cdr). These are special cases of sorting operations that were studied in prior work on permutation sorting. Moreover, cds and cdr have been postulated to model molecular sorting events that occur in the genome maintenance program of certain species of single-celled organisms called ciliates. This paper investigates mathematical aspects of these two sorting operations. The main result of this paper is a generalization of previously discovered characterizations of cds-sortability of a permutation. The combinatorial structure underlying this generalization suggests natural combinatorial two-player games. These games are the main mathematical innovation of this paper.<\/jats:p>","DOI":"10.1142\/s179383091750063x","type":"journal-article","created":{"date-parts":[[2017,8,25]],"date-time":"2017-08-25T07:18:18Z","timestamp":1503645498000},"page":"1750063","source":"Crossref","is-referenced-by-count":2,"title":["Sorting permutations: Games, genomes, and cycles"],"prefix":"10.1142","volume":"09","author":[{"given":"K. L. M.","family":"Adamyk","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Colorado, Boulder, CO, USA"}]},{"given":"E.","family":"Holmes","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Hawaii at Manoa, Honolulu, HI, USA"}]},{"given":"G. R.","family":"Mayfield","sequence":"additional","affiliation":[{"name":"Oregon Health Sciences University, Department of Computational Biology, 3181 S.W. Sam Jackson Park Rd., Portland, Oregon 97239-3098, USA"}]},{"given":"D. J.","family":"Moritz","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, University of Montana, Missoula, MT, USA"}]},{"given":"M.","family":"Scheepers","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Boise State University, Boise, ID, USA"}]},{"given":"B. E.","family":"Tenner","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, DePaul University, Chicago, IL, USA"}]},{"given":"H. C.","family":"Wauck","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University, of Illinois at Urbana-Champaign, Urbana, IL, USA"}]}],"member":"219","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"S179383091750063XBIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"key":"S179383091750063XBIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.04.010"},{"key":"S179383091750063XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.041"},{"key":"S179383091750063XBIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2014.07.034"},{"key":"S179383091750063XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00155-X"},{"key":"S179383091750063XBIB006","first-page":"1","volume":"10","author":"Doignon J.","year":"2007","journal-title":"J. Integer Seq."},{"key":"S179383091750063XBIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-06371-2"},{"key":"S179383091750063XBIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1043-9"},{"key":"S179383091750063XBIB009","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"S179383091750063XBIB010","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"S179383091750063XBIB014","volume-title":"The Art of Computer Programming","volume":"1","author":"Knuth D. E.","year":"1968"},{"issue":"2","key":"S179383091750063XBIB016","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1128\/MMBR.58.2.233-267.1994","volume":"58","author":"Prescott D. M.","year":"1994","journal-title":"Microbiol. Rev."},{"key":"S179383091750063XBIB017","doi-asserted-by":"publisher","DOI":"10.1038\/35042057"},{"key":"S179383091750063XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-5193(03)00037-7"},{"key":"S179383091750063XBIB019","doi-asserted-by":"publisher","DOI":"10.1534\/genetics.107.086074"},{"key":"S179383091750063XBIB021","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.22.7.448"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091750063X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T07:36:24Z","timestamp":1602833784000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091750063X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":16,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,11,2]]},"published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.1142\/S179383091750063X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091750063x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}