An improved algorithm to enumerate all traces that sort a signed permutation by 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 : In 2008, Braga et al. proposed an algorithm to perform the enumeration of traces that sort a signed permutation by reversals. This algorithm has exponential complexity in both time and space. The original implementation uses a special structure, to handle the information during the process. However, even with this structure, memory consumption is still a problem. In this work, we propose a stack structure to represent the set of traces that is being enumerated by the algorithm. This new structure consumes less memory and can be kept in the main memory, improving the space and time performance of the algorithm.
Type de document :
Communication dans un congrès
ACM. ACM Symposium on Applied Computing (SAC), Mar 2010, Sierre, Switzerland. pp.1521-1525, 2010, 〈10.1145/1774088.1774416〉
Liste complète des métadonnées

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

Identifiants

Citation

Christian Baudet, Zanoni Dias. An improved algorithm to enumerate all traces that sort a signed permutation by reversals. ACM. ACM Symposium on Applied Computing (SAC), Mar 2010, Sierre, Switzerland. pp.1521-1525, 2010, 〈10.1145/1774088.1774416〉. 〈hal-00748579〉

Partager

Métriques

Consultations de la notice

184