Computer Science – Discrete Mathematics
Scientific paper
2012-01-04
Computer Science
Discrete Mathematics
A preliminary version of this work appeared in the proceedings of Combinatorial Pattern Matching (CPM) 2009. See arXiv:0901.28
Scientific paper
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.
Bouvel Mathilde
Chauve Cedric
Mishna Marni
Rossin Dominique
No associations
LandOfFree
Average-case analysis of perfect sorting by reversals (Journal Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Average-case analysis of perfect sorting by reversals (Journal Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Average-case analysis of perfect sorting by reversals (Journal Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-156838