Treffer: Average-case analysis of perfect sorting by reversals (Journal Version)

Title:
Average-case analysis of perfect sorting by reversals (Journal Version)
Authors:
Bouvel, Mathilde, Chauve, Cedric, Mishna, Marni, Rossin, Dominique
Contributors:
Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université Bordeaux Segalen - Bordeaux 2 - Université Sciences et Technologies - Bordeaux 1 - École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) - Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Burnaby], Simon Fraser University (SFU.ca), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Polytechnique - X - Centre National de la Recherche Scientifique (CNRS)
Source:
Discrete Mathematics. 03(03):369-392
Publisher Information:
HAL CCSD; World Scientific Publishing, 2011.
Publication Year:
2011
Collection:
collection:CNRS
collection:LIX
collection:LABRI
collection:INSMI
collection:UNIV-BORDEAUX
collection:PARISTECH
collection:X-LIX
collection:X
collection:X-DEP
collection:X-DEP-INFO
collection:ENSEIRB
collection:TDS-MACS
Subject Terms:
[INFO.INFO-DM] Computer Science [cs], Discrete Mathematics [cs.DM], [INFO.INFO-DS] Computer Science [cs], Data Structures and Algorithms [cs.DS], [MATH.MATH-CO] Mathematics [math], Combinatorics [math.CO]
Original Identifier:
HAL: hal-00964118
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
1793-8309
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/1201.0940; info:eu-repo/semantics/altIdentifier/doi/10.1142/S1793830911001280
Availability:
https://hal.archives-ouvertes.fr/hal-00964118
Accession Number:
edshal.hal.00964118v1
Database:
HAL

Weitere Informationen

A preliminary version of this work appeared in the proceedings of Combinatorial Pattern Matching (CPM) 2009. See arXiv:0901.2847; Discrete Mathematics, Algorithms and Applications, vol. 3(3), 2011
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érard 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.