Abstract
Systems biology is with no doubt one of the most compelling fields for a computer scientist. Modelling such systems is per se a major challenge, but the ultimate goal is to reason over those systems. We focus on modelling and reasoning over biological networks using Maximum Satisfiability (MaxSAT). Biological networks are represented by an influence graph whose vertices represent the genes of the network and edges represent interactions between genes. Given an influence graph and an experimental profile, the first step is to check for mutual consistency. In case of inconsistency, a repair is suggested. In addition, what is common to all solutions/optimal repairs is also provided. This information, named prediction, is of particular interest from a user’s point of view. Answer Set Programming (ASP) has been successfully applied to biological networks in the recent past. In this work, we give empirical evidence that MaxSAT is by far more adequate for solving this problem. Moreover, we show how concepts well studied in the fields of MaxSAT and CP, such as backbones and unsatisfiable subformulas, can be naturally related to this practical problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Gene Regulatory Network
- Biological Network
- Conjunctive Normal Form
- Unit Clause
- Conjunctive Normal Form Formula
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Workshops on Constraint Based Methods for Bioinformatics (WCB) (2005-2012)
Allen, T., Herrgård, M., Liu, M., Qiu, Y., Glasner, J., Blattner, F., Palsson, B.: Genome-scale analysis of the uses of the escherichia coli genome: model-driven analysis of heterogeneous data sets. Journal of Bacteriology 185(21), 6392–6399 (2003)
Barahona, P., Krippahl, L., Perriquet, O.: Bioinformatics: a challenge to constraint programming. In: Hybrid Optimization, vol. 45, pp. 463–487. Springer (2011)
Bobrow, D.: Qualitative reasoning about physical systems: an introduction. Artificial Intelligence 24(1-3), 1–5 (1984)
Bradley, M., Beach, M., de Koning, A., Pratt, T., Osuna, R.: Effects of fis on escherichia coli gene expression during different growth stages. Microbiology 153(9), 2922–2940 (2007)
Corblin, F., Bordeaux, L., Fanchon, E., Hamadi, Y., Trilling, L.: Connections and integration with SAT solvers: a survey and a case study in computational biology. In: Hybrid Optimization, vol. 45, pp. 425–461. Springer (2011)
Corblin, F., Fanchon, E., Trilling, L.: Applications of a formal approach to decipher discrete genetic networks. BMC Bioinformatics 11, 385 (2010)
Corblin, F., Tripodi, S., Fanchon, E., Ropers, D., Trilling, L.: A declarative constraint-based method for analyzing discrete genetic regulatory networks. Biosystems 98(2), 91–104 (2009)
de Jong, H.: Modeling and simulation of genetic regulatory systems: a literature review. Journal of Computational Biology 9(1), 67–103 (2002)
Eén, N., Sörensson, N.: An Extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)
Gama-Castro, S., Jiménez-Jacinto, V., Peralta-Gil, M., Santos-Zavaleta, A., Peñaloza-Spinola, M., Contreras-Moreira, B., Segura-Salazar, J., Muñiz-Rascado, L., Martínez-Flores, I., Salgado, H., Bonavides-Martínez, C., Abreu-Goodger, C., Rodríguez-Penagos, C., Miranda-Ríos, J., Morett, E., Merino, E., Huerta, A., Treviño-Quintanilla, L., Collado-Vides, J.: RegulonDB (version 6.0): gene regulation model of escherichia coli k-12 beyond transcription, active (experimental) annotated promoters and textpresso navigation. Nucleic Acids Research 36(Database Issue), 120–124 (2008)
Gebser, M., Guziolowski, C., Ivanchev, M., Schaub, T., Siegel, A., Thiele, S., Veber, P.: Repair and prediction (under inconsistency) in large biological networks with answer set programming. In: International Conference on Principles of Knowledge Representation and Reasoning, pp. 497–507 (2010)
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: the Potsdam answer set solving collection. AI Communications 24(2), 107–124 (2011)
Gebser, M., Kaufmann, B., Schaub, T.: The Conflict-Driven Answer Set Solver clasp: Progress Report. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS, vol. 5753, pp. 509–514. Springer, Heidelberg (2009)
Gebser, M., König, A., Schaub, T., Thiele, S., Veber, P.: The BioASP library: ASP solutions for systems biology. In: IEEE International Conference on Tools with Artificial Intelligence, pp. 383–389 (2010)
Gebser, M., Schaub, T., Thiele, S., Veber, P.: Detecting inconsistencies in large biological networks with answer set programming. Theory and Practice of Logic Programing 11(2-3), 323–360 (2011)
Gregory, P., Fox, M., Long, D.: A New Empirical Study of Weak Backdoors. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 618–623. Springer, Heidelberg (2008)
Guziolowski, C., Veber, P., Le Borgne, M., Radulescu, R., Siegel, A.: Checking consistency between expression data and large scale regulatory networks: a case study. Journal of Biological Physics and Chemistry 7(2), 37–43 (2007)
Hebrard, E., Hnich, B., O’Sullivan, B., Walsh, T.: Finding diverse and similar solutions in constraint programming. In: AAAI Conference on Artificial Intelligence, pp. 372–377 (2005)
Hemery, F., Lecoutre, C., Sais, L., Boussemart, F.: Extracting MUCs from constraint networks. In: European Conference on Artificial Intelligence, pp. 113–117 (2006)
Hsu, E.I., Muise, C.J., Christopher Beck, J., McIlraith, S.A.: Probabilistically Estimating Backbones and Variable Bias: Experimental Overview. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 613–617. Springer, Heidelberg (2008)
Jeong, H., Tombor, B., Albert, R., Oltvai, Z., Barabási, A.-L.: The large-scale organization of metabolic networks. Nature 407(6804), 651–654 (2000)
Kilby, P., Slaney, J., Thiébaux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: AAAI Conference on Artificial Intelligence, pp. 1368–1373 (2005)
Marques-Silva, J.: Minimal unsatisfiability: models, algorithms and applications. In: IEEE International Symposium on Multiple-Valued Logic, pp. 9–14 (2010)
Marques-Silva, J., Manquinho, V.: Towards More Effective Unsatisfiability-Based Maximum Satisfiability Algorithms. In: Kleine Büning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol. 4996, pp. 225–230. Springer, Heidelberg (2008)
Marques-Silva, J., Mikoláš, J., Lynce, I.: On computing backbones of propositional theories. In: European Conference on Artificial Intelligence, pp. 15–20 (2010)
Menaï, M.: A two-phase backbone-based search heuristic for partial MAX-SAT – an initial investigation. In: Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, pp. 681–684 (2005)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic ‘phase transitions’. Nature 400(6740), 133–137 (1999)
Siegel, A., Radulescu, O., Le Borgne, M., Veber, P., Ouy, J., Lagarrigue, S.: Qualitative analysis of the relation between DNA microarray data and behavioral models of regulation networks. Biosystems 84(2), 153–174 (2006)
Slaney, J., Walsh, T.: Backbones in optimization and approximation. In: International Joint Conference on Artificial Intelligence, pp. 254–259 (2001)
Soliman, S.: Constraint programming for the dynamical analysis of biochemical systems – a survey. Technical Report Deliverable 1.6, ANR CALAMAR, ANR-08-SYSC-003 (2011)
Soulé, C.: Mathematical approaches to differentiation and gene regulation. Comptes Rendus Biologies 329(1), 13–20 (2006)
Zhang, W., Rangan, A., Looks, M.: Backbone guided local search for maximum satisfiability. In: International Joint Conference on Artificial Intelligence, pp. 1179–1184 (2003)
Zhu, C., Weissenbacher, G., Sethi, D., Malik, S.: SAT-based techniques for determining backbones for post-silicon fault localisation. In: IEEE International High Level Design Validation and Test Workshop, pp. 84–91 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guerra, J., Lynce, I. (2012). Reasoning over Biological Networks Using Maximum Satisfiability. In: Milano, M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_67
Download citation
DOI: https://doi.org/10.1007/978-3-642-33558-7_67
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33557-0
Online ISBN: 978-3-642-33558-7
eBook Packages: Computer ScienceComputer Science (R0)