Modeling parsimonious putative regulatory networks: complexity and heuristic approach

Abstract : A relevant problem in systems biology is the description of the regulatory interactions between genes. It is observed that pairs of genes have significant correlation through several experimental conditions. The question is to find causal relationships that can explain this experimental evidence. A putative regulatory network can be represented by an oriented weighted graph, where vertices represent genes, arcs represent predicted regulatory interactions and the arc weights represent the $p$-value of the prediction. Given such graph, and experimental evidence of correlation between pairs of vertices, we propose an abstraction and a method to enumerate all parsimonious subgraphs that assign causality relationships compatible with the experimental evidence. When the problem is modeled as the minimization of a global weight function, we show that the enumeration of scenarios is a hard problem. As an heuristic, we model the problem as a set of independent minimization problems, each solvable in polynomial time, which can be combined to explore a relevant subset of the solution space. We present a logic-programming formalization of the model implemented using Answer Set Programming. We show that, when the graph follows patterns that can be found in real organisms, our heuristic finds solutions that are good approximations to the full model. We encoded these approach using Answer Set Programming, applied this to a specific case in the organism \emph{E.\,coli} and compared the execution time of each approach.
Type de document :
Communication dans un congrès
15th conference in Verification, Model Checking, and Abstract Interpretation, 2014, San Diego, United States. Springer, 8318, pp.322-336, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54013-4_18〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00926477
Contributeur : Anne Siegel <>
Soumis le : jeudi 9 janvier 2014 - 16:06:17
Dernière modification le : mercredi 16 mai 2018 - 11:23:35
Document(s) archivé(s) le : jeudi 10 avril 2014 - 11:45:10

Fichier

complex.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Vicente Acuña, Andrés Aravena, Alejandro Maass, Anne Siegel. Modeling parsimonious putative regulatory networks: complexity and heuristic approach. 15th conference in Verification, Model Checking, and Abstract Interpretation, 2014, San Diego, United States. Springer, 8318, pp.322-336, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-642-54013-4_18〉. 〈hal-00926477〉

Partager

Métriques

Consultations de la notice

401

Téléchargements de fichiers

329