Partial enumeration of solutions traces for the problem of sorting by signed reversals

Christian Baudet 1 Zanoni Dias 2
1 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : Traditional algorithms to solve the problem of sorting by signed reversals output just one optional solution while the space of optimal solutions can be huge. Algorithms for enumerating the complete set of solutions traces were developed aiming to support biologists studies of alternative evolutionary scenarios. Due to the exponential complexity of the algorithms, their practical use is limited to small permutations. In this work, we propose and evaluate three di erent approaches to producing a partial enumeration of the complete set of traces to transform a given permutation to another one.
Complete list of metadatas

https://hal.inria.fr/hal-00748607
Contributor : Marie-France Sagot <>
Submitted on : Monday, November 5, 2012 - 3:56:21 PM
Last modification on : Thursday, March 21, 2019 - 2:51:28 PM

Identifiers

Collections

Citation

Christian Baudet, Zanoni Dias. Partial enumeration of solutions traces for the problem of sorting by signed reversals. Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine, Aug 2011, Chicago, United States. pp.505--507, ⟨10.1145/2147805.2147884⟩. ⟨hal-00748607⟩

Share

Metrics

Record views

190