The structural analysis of metabolic networks aims both at understanding the function and the evolution of metabolism. While it is commonly admitted that metabolism is modular, the identification of metabolic modules remains an open topic. Several definitions of what is a module have been proposed. We focus here on the notion of chemical organisations, i.e. sets of molecules which are closed and self-maintaining. We show that finding a reactive organisation is NP-hard even if the network is flux-consistent and that the hardness comes from blocking cycles. We then propose new algorithms for enumerating chemical organisations that are theoretically more efficient than existing approaches.
ENUMERATING CHEMICAL ORGANISATIONS IN CONSISTENT METABOLIC NETWORKS: COMPLEXITY AND ALGORITHMS / P. MILREU; V. ACUNA; E. BIRMELE; P. CRESCENZI; A. MARCHETTI-SPACCAMELA; M.-F. SAGOT; L. STOUGIE; V. LACROIX. - STAMPA. - (2010), pp. 226-237. (Intervento presentato al convegno Tenth Workshop on Algorithms in Bioinformatics) [10.1007/978-3-642-15294-8_19].
ENUMERATING CHEMICAL ORGANISATIONS IN CONSISTENT METABOLIC NETWORKS: COMPLEXITY AND ALGORITHMS
CRESCENZI, PIERLUIGI;
2010
Abstract
The structural analysis of metabolic networks aims both at understanding the function and the evolution of metabolism. While it is commonly admitted that metabolism is modular, the identification of metabolic modules remains an open topic. Several definitions of what is a module have been proposed. We focus here on the notion of chemical organisations, i.e. sets of molecules which are closed and self-maintaining. We show that finding a reactive organisation is NP-hard even if the network is flux-consistent and that the hardness comes from blocking cycles. We then propose new algorithms for enumerating chemical organisations that are theoretically more efficient than existing approaches.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.