3BAMBOO - An algorithmic view on genomes, cells, and environments (Laboratoire de Biométrie et Biologie Évolutive. UMR CNRS 5558 Campus de La Doua - Université Claude Bernard - Lyon 1 Bâtiment Grégoire Mendel - 16 rue Raphael Dubois 69 100 Villeurbanne -- INRIA Grenoble - Rhône-Alpes Inovallée 655 avenue de l'Europe -Montbonnot 38 334 Saint Ismier Cedex France - France)
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.
https://hal.inria.fr/hal-00835201
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, June 18, 2013 - 11:14:01 AM Last modification on : Wednesday, April 15, 2020 - 9:56:11 AM