Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T08:37:19.448Z Has data issue: false hasContentIssue false
  • English
  • Français

Detecting inconsistencies in large biological networks with answer set programming

Published online by Cambridge University Press:  27 January 2011

MARTIN GEBSER,
TORSTEN SCHAUB,
SVEN THIELE and
PHILIPPE VEBER
MARTIN GEBSER
Affiliation:
Institute for Informatics, University of Potsdam, Potsdam, Germany (e-mail: gebser@cs.uni-potsdam.de, torsten@cs.uni-potsdam.de, sthiele@cs.uni-potsdam.de)
TORSTEN SCHAUB
Affiliation:
Institute for Informatics, University of Potsdam, Potsdam, Germany (e-mail: gebser@cs.uni-potsdam.de, torsten@cs.uni-potsdam.de, sthiele@cs.uni-potsdam.de)
SVEN THIELE
Affiliation:
Institute for Informatics, University of Potsdam, Potsdam, Germany (e-mail: gebser@cs.uni-potsdam.de, torsten@cs.uni-potsdam.de, sthiele@cs.uni-potsdam.de)
PHILIPPE VEBER
Affiliation:
Institut Cochin, Paris, France (e-mail: philippe.veber@googlemail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce an approach to detecting inconsistencies in large biological networks by using answer set programming. To this end, we build upon a recently proposed notion of consistency between biochemical/genetic reactions and high-throughput profiles of cell activity. We then present an approach based on answer set programming to check the consistency of large-scale data sets. Moreover, we extend this methodology to provide explanations for inconsistencies by determining minimal representations of conflicts. In practice, this can be used to identify unreliable data or to indicate missing reactions.

Keywords

answer set programmingbioinformaticsconsistencydiagnosis

References

Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.CrossRefGoogle Scholar
Ben-Eliyahu, R. and Dechter, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, 1–2, 53–87.CrossRefGoogle Scholar
BioASP Tools. 2008. Accessed 7 January 2011, URL: http://www.cs.uni-potsdam.de/wv/bioaspGoogle Scholar
Chen, M., Hancock, L. and Lopes, J. 2007. Transcriptional regulation of yeast phospholipid biosynthetic genes. Biochimica et Biophysica Acta 1771, 3, 310–321.Google Scholar
Dershowitz, N., Hanna, Z. and Nadel, A. 2006. A scalable algorithm for minimal unsatisfiable core extraction. In Proc. of the 9th International Conference on Theory and Applications of Satisfiability Testing (SAT'06), Biere, A. and Gomes, C., Eds. Springer, 36–41.Google Scholar
Drescher, C., Gebser, M., Grote, T., Kaufmann, B., König, A., Ostrowski, M. and Schaub, T. 2008. Conflict-driven disjunctive answer set solving. In Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08), Brewka, G. and Lang, J., Eds. AAAI Press, 422–432.Google Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3–4, 289–323.Google Scholar
Erdős, A. and Rényi, P. 1959. On random graphs. Publicationes Mathematicae 6, 290–297.CrossRefGoogle Scholar
Friedman, N., Linial, M., Nachman, I. and Pe'er, D. 2000. Using Bayesian networks to analyze expression data. Journal of Computational Biology 7, 3–4, 601–620.Google Scholar
Gebser, M., Guziolowski, C., Ivanchev, M., Schaub, T., Siegel, A., Thiele, S. and Veber, P. 2010. Repair and prediction (under inconsistency) in large biological networks with answer set programming. In Proc. of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR'10).Google Scholar
Gebser, M., Kaminski, R., Ostrowski, M., Schaub, T. and Thiele, S. 2009a. On the input language of ASP grounder gringo. In Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09), Erdem, E., Lin, F. and Schaub, T., Eds. Springer, 502–508.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set enumeration. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07), Baral, C., Brewka, G. and Schlipf, J., Eds. Springer, 136–148.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2009b. Solution enumeration for projected Boolean search problems. In Proc. of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'09), van Hoeve, W. and Hooker, J., Eds. Springer, 71–86.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2009c. The conflict-driven answer set solver clasp: Progress report. In Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09), Erdem, E., Lin, F. and Schaub, T., Eds. Springer, 509–514.Google Scholar
Gelfond, M. 2008. Answer sets. In Handbook of Knowledge Representation, Lifschitz, V., van Hermelen, F. and Porter, B., Eds. Elsevier, 285–316.Google Scholar
Gelfond, M., Lifschitz, V., Przymusinska, H. and Truszczyński, M. 1991. Disjunctive defaults. In Proc. of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR'91), Allen, J., Fikes, R. and Sandewall, E., Eds. Morgan Kaufmann, 230–237.Google Scholar
Giunchiglia, E., Lierler, Y. and Maratea, M. 2006. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning 36, 4, 345–377.CrossRefGoogle Scholar
Guelzim, N., Bottani, S., Bourgine, P. and Képès, F. 2002. Topological and causal structure of the yeast transcriptional regulatory network. Nature Genetics 31, 60–63.CrossRefGoogle ScholarPubMed
Gutierrez-Rios, R., Rosenblueth, D., Loza, J., Huerta, A., Glasner, J., Blattner, F. and Collado-Vides, J. 2003. Regulatory network of Escherichia coli: Consistency between literature knowledge and microarray profiles. Genome Research 13, 11, 2435–2443.CrossRefGoogle ScholarPubMed
Guziolowski, C., Bourde, A., Moreews, F. and Siegel, A. 2009. Bioquali cytoscape plugin: Analysing the global consistency of regulatory networks. BMC Genomics 10.Google Scholar
Guziolowski, C., Veber, P., LeBorgne, M. Borgne, M., Radulescu, O. and Siegel, A. 2007. Checking consistency between expression data and large scale regulatory networks: A case study. Journal of Biological Physics and Chemistry 7, 2, 37–43.Google Scholar
Janhunen, T., Niemelä, I., Seipel, D., Simons, P. and You, J. 2006. Unfolding partiality and disjunctions in stable model semantics. ACM Transactions on Computational Logic 7, 1, 1–37.CrossRefGoogle Scholar
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. and Barabási, A. 2000. The large-scale organization of metabolic networks. Nature 407, 651–654.Google Scholar
Klamt, S. and Stelling, J. 2006. Stoichiometric and constraint-based modelling. In System Modeling in Cellular Biology: From Concepts to Nuts and Bolts, Szallasi, Z., Stelling, J. and Periwal, V., Eds. MIT Press, 73–96.CrossRefGoogle Scholar
Kuipers, B. 1994. Qualitative reasoning. Modeling and simulation with incomplete knowledge. MIT Press.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.CrossRefGoogle Scholar
Mallory, M., Cooper, K. and Strich, R. 2007. Meiosis-specific destruction of the Ume6p repressor by the Cdc20-directed APC/C. Molecular Cell 27, 6, 951–961.Google Scholar
Papadimitriou, C. and Yannakakis, M. 1982. The complexity of facets (and some facets of complexity). In Proc. of the 14th Annual ACM Symposium on Theory of Computing (STOC'82). ACM Press, 255–260.Google Scholar
Remy, É., Ruet, P. and Thieffry, D. 2008. Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework. Advances in Applied Mathematics 41, 3, 335–350.CrossRefGoogle Scholar
Richard, A., Comet, J. and Bernot, G. 2004. R. Thomas' modeling of biological regulatory networks: Introduction of singular states in the qualitative dynamics. Fundamenta Informaticae 65, 4, 373–392.Google Scholar
Siegel, A., Radulescu, O., Le Borgne, M., Veber, P., Ouy, J. and Lagarrigue, S. 2006. Qualitative analysis of the relation between DNA microarray data and behavioral models of regulation networks. Biosystems 84, 2, 153–174.Google Scholar
Soulé, C. 2003. Graphic requirements for multistationarity. Complexus 1, 3, 123–133.CrossRefGoogle Scholar
Soulé, C. 2006. Mathematical approaches to differentiation and gene regulation. Comptes Rendus Biologies 329, 13–20.CrossRefGoogle ScholarPubMed
Sudarsanam, P., Iyer, V., Brown, P. and Winston, F. 2000. Whole-genome expression analysis of snf/swi mutants of Saccharomyces cerevisiae. Proceedings of the National Academy of Sciences of the United States of America 97, 7, 3364–3369.Google Scholar
Syrjänen, T.Lparse 1.0 user's manual, Accessed 7 January 2011. URL: http://www.tcs.hut.fi/Software/smodels/lparse.ps.gzGoogle Scholar
Veber, P., Le Borgne, M., Siegel, A., Lagarrigue, S. and Radulescu, O. 2004. Complex qualitative models in biology: A new approach. Complexus 2, 3–4, 140–151.Google Scholar
Washburn, B. and Esposito, R. 2006. Identification of the Sin3-binding site in Ume6 defines a two-step process for conversion of Ume6 from a transcriptional repressor to an activator in yeast. Molecular and Cellular Biology 21, 6, 2057–2069.CrossRefGoogle Scholar