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.