{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:04Z","timestamp":1771036384532,"version":"3.50.1"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. B\u00e9rard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals.<\/jats:p>","DOI":"10.1142\/s1793830911001280","type":"journal-article","created":{"date-parts":[[2011,10,21]],"date-time":"2011-10-21T12:29:23Z","timestamp":1319200163000},"page":"369-392","source":"Crossref","is-referenced-by-count":7,"title":["AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS"],"prefix":"10.1142","volume":"03","author":[{"given":"MATHILDE","family":"BOUVEL","sequence":"first","affiliation":[{"name":"CNRS, Universit\u00e9 de Bordeaux I, LaBRI, Bordeaux, France"}]},{"given":"CEDRIC","family":"CHAUVE","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, BC Canada V5A 1S6, Canada"}]},{"given":"MARNI","family":"MISHNA","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, BC Canada V5A 1S6, Canada"}]},{"given":"DOMINIQUE","family":"ROSSIN","sequence":"additional","affiliation":[{"name":"CNRS, \u00c9cole Polytechnique, LIX, Palaiseau, France"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.016"},{"key":"rf2","volume":"6","author":"Albert M. H.","journal-title":"J. Integer Seq."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1011"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0088"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.10.012"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/060651331"},{"key":"rf8","volume-title":"Mathematics of Evolution and Phylogeny","author":"Bergeron A.","year":"2005"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.16"},{"key":"rf12","first-page":"189","volume":"8","author":"Corteel S.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1042"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00029-X"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731121"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2005.12.1289"},{"key":"rf24","first-page":"i190","author":"Lefebvre J.-F.","journal-title":"Bioinformatics"},{"key":"rf25","volume-title":"Mathematics of Evolution and Phylogeny","author":"Moret B. M. E.","year":"2005"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0020014"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.02.033"},{"key":"rf31","doi-asserted-by":"crossref","first-page":"R105","DOI":"10.37236\/829","volume":"15","author":"Tesler G.","journal-title":"Electron. J. Combinat."},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910014"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003254"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn295"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.A004"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830911001280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T09:38:08Z","timestamp":1593164288000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830911001280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":28,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1142\/S1793830911001280"],"URL":"https:\/\/doi.org\/10.1142\/s1793830911001280","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]}}}