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
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.
Type de document :
Communication dans un congrès
Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine, Aug 2011, Chicago, United States. ACM, pp.505--507, 2011, 〈10.1145/2147805.2147884〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00748607
Contributeur : Marie-France Sagot <>
Soumis le : lundi 5 novembre 2012 - 15:56:21
Dernière modification le : jeudi 19 avril 2018 - 14:49:47

Identifiants

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. ACM, pp.505--507, 2011, 〈10.1145/2147805.2147884〉. 〈hal-00748607〉

Partager

Métriques

Consultations de la notice

148