%0 Journal Article
%T Sampling solution traces for the problem of sorting permutations by signed reversals
%A Christian Baudet
%A Zanoni Dias
%A Marie-France Sagot
%J Algorithms for Molecular Biology
%D 2012
%I BioMed Central
%R 10.1186/1748-7188-7-18
%X We propose and evaluate three algorithms for producing a sampling of the complete set of traces that instead can be shown in practice to preserve some of the characteristics of the space of all solutions. The first algorithm (RA) performs the construction of traces through a random selection of reversals on the list of optimal 1-sequences. The second algorithm (DFALT) consists in a slight modification of an algorithm that performs the complete enumeration of traces. Finally, the third algorithm (SWA) is based on a sliding window strategy to improve the enumeration of traces. All proposed algorithms were able to enumerate traces for permutations with up to 200 elements.We analysed the distribution of the enumerated traces with respect to their height and average reversal length. Various works indicate that the reversal length can be an important aspect in genome rearrangements. The algorithms RA and SWA show a tendency to lose traces with high average reversal length. Such traces are however rare, and qualitatively our results show that, for testable-sized permutations, the algorithms DFALT and SWA produce distributions which approximate the reversal length distributions observed with a complete enumeration of the set of traces.
%K Reversals
%K Traces
%K Sampling
%K Genome rearrangement
%U http://www.almob.org/content/7/1/18/abstract