Telling Stories Fast

Michele Borassi 1 Pierluigi Crescenzi 2 Vincent Lacroix 3 Andrea Marino 2 Marie-France Sagot 3, * Paulo Vieira Milreu 3
* Auteur correspondant
1 SNS - Scuola Normale Superiore di Pisa
2 DSI - Dipartimento di Sistemi e Informatica
3 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive
Abstract : This paper presents a linear-time delay algorithm for enumerating all directed acyclic subgraphs of a directed graph G(V,E) that have their sources and targets included in two subsets S and T of V, respectively. From these subgraphs, called pitches, the maximal ones, called stories, may be extracted in a dramatically more efficient way in relation to a previous story telling algorithm. The improvement may even increase if a pruning technique is further applied that avoids generating many pitches which have no chance to lead to a story. We experimentally demonstrate these statements by making use of a quite large dataset of real metabolic pathways and networks.
Type de document :
Communication dans un congrès
12th International Symposium Experimental Algorithms (SEA), Jun 2013, Rome, Italy. 7933, pp.200-211, 2013, Lecture Notes in Computer Science
Liste complète des métadonnées
https://hal.inria.fr/hal-00835201
Contributeur : Marie-France Sagot <>
Soumis le : mardi 18 juin 2013 - 11:14:01
Dernière modification le : jeudi 19 avril 2018 - 14:49:47

Identifiants

  • HAL Id : hal-00835201, version 1

Collections

INRIA | BAMBOO | BIOENVIS | UNIV-LYON1 | INRIA-RENGRE

Citation

Michele Borassi, Pierluigi Crescenzi, Vincent Lacroix, Andrea Marino, Marie-France Sagot, et al.. Telling Stories Fast. 12th International Symposium Experimental Algorithms (SEA), Jun 2013, Rome, Italy. 7933, pp.200-211, 2013, Lecture Notes in Computer Science. 〈hal-00835201〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

323

Contact


archive-ouverte@inria.fr