Average-Case Analysis of Perfect Sorting by Reversals

DOI10.1007/978-3-642-02441-2_28MaRDI QIDQ3637122zbMATH OpenOpenAlexFDO

Authors Mathilde Bouvel, Cedric Chauve, Marni Mishna, Dominique Rossin

Publication date 7 July 2009

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0940

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Searching and sorting (68P10)

Abstract: 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'erard 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.

Recommendations

• Average-case analysis of perfect sorting by reversals
• On the average number of reversals needed to sort signed permutations
• Combinatorial Pattern Matching
• A more efficient algorithm for perfect sorting by reversals
• Advances on sorting by reversals

Cites work

• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• scientific article; zbMATH DE number 5031986 (Why is no real title available?)
• A more efficient algorithm for perfect sorting by reversals
• Advances on sorting by reversals
• Analytic combinatorics
• Comparative Genomics
• Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
• Finding pattern matchings for permutations
• Simple permutations and pattern restricted permutations
• The On-Line Encyclopedia of Integer Sequences
• Transforming cabbage into turnip

Cited in

(5)

• Average-case analysis of perfect sorting by reversals
• Efficient sample sort and the average case analysis of PEsort
• A note on average-case sorting
• A more efficient algorithm for perfect sorting by reversals
• On the average number of reversals needed to sort signed permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Average-Case Analysis of Perfect Sorting by Reversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637122)