×

Hypothesizing about signaling networks. (English) Zbl 1168.92002

Summary: The current knowledge about signaling networks is largely incomplete. Thus biologists constantly need to revise or extend existing knowledge. The revision and/or extension is first formulated as theoretical hypotheses, then verified experimentally. Many computer-aided systems have been developed to assist biologists in undertaking this challenge. The majority of the systems help in finding “patterns” in data and leave the reasoning to biologists. A few systems have tried to automate the reasoning process of hypothesis formation. These systems generate hypotheses from a knowledge base and given observations. A main drawback of these knowledge-based systems is the knowledge representation formalism they use. These formalisms are mostly monotonic and are now known to be not quite suitable for knowledge representation, especially in dealing with the inherently incomplete knowledge about signaling networks.
We propose an action language based framework for hypothesis formation for signaling networks. We show that the hypothesis formation problem can be translated into an abduction problem. This translation facilitates the complexity analysis and an efficient implementation of our system. We illustrate the applicability of our system with an example of hypothesis formation in the signaling network of the p53 protein.

MSC:

92B05 General biology and biomathematics
92C55 Biomedical imaging and signal processing
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J.; Kautz, H.; Pelavin, R.; Tenenberg, J., Reasoning about Plans (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0759.68077
[2] R. Alur, C. Belta, F. Ivanicic, V. Kumar, M. Mintz, G.J. Pappas, H. Rubin, J. Schug, Hybrid modeling and simulation of biomolecular networks, in: Hybrid Systems: Computation and Control, in: LNCS, vol. 2034, 2001, pp. 19-32; R. Alur, C. Belta, F. Ivanicic, V. Kumar, M. Mintz, G.J. Pappas, H. Rubin, J. Schug, Hybrid modeling and simulation of biomolecular networks, in: Hybrid Systems: Computation and Control, in: LNCS, vol. 2034, 2001, pp. 19-32
[3] M. Balduccini, Answer set based design of highly autonomous, rational agents, PhD thesis, Texas Tech. University, 2005; M. Balduccini, Answer set based design of highly autonomous, rational agents, PhD thesis, Texas Tech. University, 2005
[4] M. Balduccini, M. Gelfond, Logic programs with consistency-restoring rules, in: International Symposium on Logical Formalization of Commonsense Reasoning, 2003; M. Balduccini, M. Gelfond, Logic programs with consistency-restoring rules, in: International Symposium on Logical Formalization of Commonsense Reasoning, 2003 · Zbl 1079.68094
[5] Baral, C., Knowledge Representation, Reasoning and Declarative Problem Solving (2003), Cambridge University Press · Zbl 1056.68139
[6] Baral, C.; Chancellor, K.; Tran, N.; Tran, N. L.; Berens, M., A knowledge based approach for representing and reasoning about signaling networks, Bioinformatics, 20, Suppl 1, i15-i22 (2004)
[7] G. Batt, H. de Jong, J. Geiselmann, M. Page, Analysis of genetic regulatory networks: A model-checking approach, in: International Workshop on Qualitative Reasoning, 2003; G. Batt, H. de Jong, J. Geiselmann, M. Page, Analysis of genetic regulatory networks: A model-checking approach, in: International Workshop on Qualitative Reasoning, 2003 · Zbl 1283.93046
[8] Bode, A. M.; Dong, Z., Post-translational modification of p53 in tumorigenesis, Nature Reviews Cancer, 4, 10, 793-805 (2004)
[9] Boutilier, C., Abduction to plausible causes: An even based model of belief update, Artificial Intelligence, 83, 143-166 (1996) · Zbl 1506.68133
[10] Boutilier, C.; Becher, V., Abduction as belief revision, Artificial Intelligence, 77, 43-94 (1995) · Zbl 1014.03506
[11] M. Chiaverini, V. Danos, A core modeling language for the working molecular biologist, in: Computational Methods in Systems Biology, 2003; M. Chiaverini, V. Danos, A core modeling language for the working molecular biologist, in: Computational Methods in Systems Biology, 2003 · Zbl 1112.92313
[12] D. Cook, J. Farley, S. Tapscott, A basis for a visual language for describing, archiving and analyzing functional models of complex biological systems, Genome Biology 2 (4); D. Cook, J. Farley, S. Tapscott, A basis for a visual language for describing, archiving and analyzing functional models of complex biological systems, Genome Biology 2 (4)
[13] V. Danos, C. Laneve, Graphs for core molecular biology, in: Computational Methods in Systems Biology, 2003; V. Danos, C. Laneve, Graphs for core molecular biology, in: Computational Methods in Systems Biology, 2003 · Zbl 1053.92021
[14] L. Darden, Recent work in computational scientific discovery, in: Proceedings of the Nineteenth Annual Conference of the Cognitive Science Society, 1997; L. Darden, Recent work in computational scientific discovery, in: Proceedings of the Nineteenth Annual Conference of the Cognitive Science Society, 1997
[15] L. Darden, Anomaly-driven theory redesign: computational philosophy of science experiments, in: Digital Phoenix: How Computers are Changing Philosophy, 1998, pp. 62-78; L. Darden, Anomaly-driven theory redesign: computational philosophy of science experiments, in: Digital Phoenix: How Computers are Changing Philosophy, 1998, pp. 62-78
[16] Davidson, E. H.; Rast, J. P.; Oliveri, P.; Ransick, A.; Calestani, C.; Yuh, C.-H.; Minokawa, T.; Amore, G.; Hinman, V.; Arenas-Mena, C.; Otim, O.; Brown, C. T.; Livi, C. B.; Lee, P. Y.; Revilla, R.; Rust, A. G.; Pan, Z. J.; Schilstra, M. J.; Clarke, P. J.C.; Arnone, M. I.; Rowen, L.; Cameron, R. A.; McClay, D. R.; Hood, L.; Bolouri, H., A genomic regulatory network for development, Science, 295, 1669-1678 (2002)
[17] Davidson, E. H.; Rast, J. P.; Oliveri, P.; Ransick, A.; Calestani, C.; Yuh, C.-H.; Minokawa, T.; Amore, G.; Hinman, V.; Arenas-Mena, C.; Otim, O.; Brown, C. T.; Livi, C. B.; Lee, P. Y.; Revilla, R.; Rust, A. G.; Pan, Z. J.; Schilstra, M. J.; Clarke, P. J.C.; Arnone, M. I.; Rowen, L.; Cameron, R. A.; McClay, D. R.; Hood, L.; Bolouri, H., A genomic regulatory network for development, Science, 295, 5560, 1669-1678 (2002)
[18] de Jong, H., Modeling and simulation of genetic regulatory systems: A literature review, Journal of Computational Biology, 9, 1, 67-103 (2002)
[19] de Jong, H.; Geiselmann, J.; Hernandez, C.; Page, M., Genetic Network Analyzer: qualitative simulation of genetic regulatory networks, Bioinformatics, 19, 336-344 (2003)
[20] Demir, E.; Babur, O.; Dogrusoz, U.; Gursoy, A.; Ayaz, A.; Gulesir, G.; Nisanci, G.; Cetin-Atalay, R., An ontology for collaborative construction and analysis of cellular pathways, Bioinformatics, 20, 3, 349-356 (2004)
[21] M. Denecker, A.C. Kakas, Abduction in logic programming, in: Computational Logic: Logic Programming and Beyond, 2002; M. Denecker, A.C. Kakas, Abduction in logic programming, in: Computational Logic: Logic Programming and Beyond, 2002 · Zbl 1012.68503
[22] P. Doherty, S. Kertes, M. Magnusson, A. Szalas, Towards a logical analysis of biochemical pathways, in: Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA), 2004; P. Doherty, S. Kertes, M. Magnusson, A. Szalas, Towards a logical analysis of biochemical pathways, in: Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA), 2004 · Zbl 1111.68671
[23] Eiter, T.; Gottlob, G.; Leone, N., Abduction from logic programs: semantics and complexity, Theoretical Computer Science, 189, 1-2, 129-177 (1997) · Zbl 0893.68022
[24] S. Eker, M. Knapp, K. Laderoute, P. Lincoln, JosMeseguer, K. Sonmez, Pathway logic: symbolic analysis of biological signaling, in: Proceedings of the Pacific Symposium on Biocomputing, 2002; S. Eker, M. Knapp, K. Laderoute, P. Lincoln, JosMeseguer, K. Sonmez, Pathway logic: symbolic analysis of biological signaling, in: Proceedings of the Pacific Symposium on Biocomputing, 2002
[25] K. Eshghi, Abductive planning with event calculus, in: Proceedings of the International Conference on Logic Programming, 1998; K. Eshghi, Abductive planning with event calculus, in: Proceedings of the International Conference on Logic Programming, 1998
[26] K. Eshghi, R. Kowalski, Abduction computed with negation as failure, in: Proceedings of the International Conference on Logic Programming, 1989; K. Eshghi, R. Kowalski, Abduction computed with negation as failure, in: Proceedings of the International Conference on Logic Programming, 1989
[27] Fages, F.; Soliman, S.; Chabrier-Rivier, N., Modelling and querying interaction networks in the biochemical abstract machine BIOCHAM, Journal of Biological Physics and Chemistry, 4, 2, 64-73 (2004)
[28] Fukuda, K.; Takagi, T., Knowledge representation of signal transduction pathways, Bioinformatics, 17, 9, 829-837 (2001)
[29] K. Fukuda, Y. Yamagata, T. Takagi, Frex: a query interface for biological processes with a hierarchical and recursive structures, In Silico Biology 4, 0007; K. Fukuda, Y. Yamagata, T. Takagi, Frex: a query interface for biological processes with a hierarchical and recursive structures, In Silico Biology 4, 0007
[30] Funahashi, A.; Tanimura, N.; Morohashi, M.; Kitano, H., Celldesigner: a process diagram editor for gene-regulatory and biochemical networks, Biosilico, 1, 5, 159-162 (2003)
[31] M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: Proceedings of the International Conference on Logic Programming, 1988; M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: Proceedings of the International Conference on Logic Programming, 1988
[32] Gelfond, M.; Lifschitz, V., Representing action and change by logic programs, Journal of Logic Programming, 17, 2/3&4, 301-321 (1993) · Zbl 0783.68024
[33] Hamid, T.; Kakar, S., PTTG/securin activates expression of p53 and modulates its function, Molecular Cancer, 3, 1, 18 (2004)
[34] Heidtke, K.; Schulze-Kremer, S., Design and implementation of a qualitative simulation model of lambda phage infection, Bioinformatics, 14, 81-91 (1998)
[35] Hoffmann, A.; Levchenko, A.; Scott, M. L.; Baltimore, D., The ikappab-nfkappab signaling module: Temporal control and selective gene activation, Science, 298, 1241-1245 (2002)
[36] A. Kakas, R. Kowalski, F. Toni, The role of abduction in logic programming, in: Handbook of logic in Artificial Intelligence and Logic Programming, 1998, pp. 235-324; A. Kakas, R. Kowalski, F. Toni, The role of abduction in logic programming, in: Handbook of logic in Artificial Intelligence and Logic Programming, 1998, pp. 235-324
[37] C. Kakas, Antonis, B. Van Nuffelen, M. Denecker, A-system: Problem solving through abduction, in: Proceedings of the International Joint Conferences on Artificial Intelligence, vol. 1, 2001; C. Kakas, Antonis, B. Van Nuffelen, M. Denecker, A-system: Problem solving through abduction, in: Proceedings of the International Joint Conferences on Artificial Intelligence, vol. 1, 2001 · Zbl 1010.68687
[38] N. Kam, I. Cohen, D. Harel, The immune system as a reactive system: modeling T-cell activation with statecharts, 2001; N. Kam, I. Cohen, D. Harel, The immune system as a reactive system: modeling T-cell activation with statecharts, 2001
[39] Karp, P., Artificial intelligence methods for theory representation and hypothesis formation, Computer Applications in the Biosciences, 7, 3, 301-308 (1991)
[40] Karp, P. D., Design methods for scientific hypothesis formation and their application to molecular biology, Machine Learning, 12, 89-116 (1993)
[41] Karp, P. D., A qualitative biochemistry and its application to the regulation of the tryptophan operon, Artificial Intelligence and Molecular Biology, 289-324 (1993)
[42] P.D. Karp, C. Ouzounis, S. Paley, HinCyc: A knowledge base of the complete genome and metabolic pathways of H. influenzae, in: Proceedings of the International Conference Intelligent Systems for Molecular Biology, 1996; P.D. Karp, C. Ouzounis, S. Paley, HinCyc: A knowledge base of the complete genome and metabolic pathways of H. influenzae, in: Proceedings of the International Conference Intelligent Systems for Molecular Biology, 1996
[43] Karp, P. D.; Paley, S.; Romero, P., The pathway tools software, Bioinformatics, 18, Suppl. 1, S225-S232 (2002)
[44] Karp, P. D.; Riley, M.; Saier, M.; Paulsen, I. T.; Collado-Vides, J.; Paley, S. M.; Pellegrini-Toole, A.; Bonavides, C.; Gama-Castro, S., The ecocyc database, Nucleic Acids Research, 30, 1, 56-58 (2002)
[45] Karp, P. D.; Riley, M.; Saier, M.; Paulsen, I. T.; Paley, S. M.; Pellegrini-Toole, A., The ecocyc and metacyc databases, Nucleic Acids Research, 28, 1, 56-59 (2000)
[46] King, R., Functional genomic hypothesis generation and experimentation by a robot scientist, Nature, 427, 6971, 247-252 (2004)
[47] Kitano, H., A graphical notation for biological networks, Biosilico, 1, 5, 169-176 (2003)
[48] Kohn, K. W., Molecular interaction map of the mammalian cell cycle control and DNA repair systems, Molecular Biology of the Cell, 10, 2703-2734 (1999)
[49] Krieger, C. J.; Zhang, P.; Mueller, L. A.; Wang, A.; Paley, S.; Arnaud, M.; Pick, J.; Rhee, S. Y.; Karp, P. D., Metacyc: A multiorganism database of metabolic pathways and enzymes, Nucleic Acids Research, 32, D438-D442 (2004)
[50] L. Calzone, N. Chabrier-Rivier, F. Fages, S. Soliman, A machine learning approach to biochemical reaction rules discovery, in: Proceedings of the Conference on Foundations of Systems Biology in Engineering, 2005; L. Calzone, N. Chabrier-Rivier, F. Fages, S. Soliman, A machine learning approach to biochemical reaction rules discovery, in: Proceedings of the Conference on Foundations of Systems Biology in Engineering, 2005 · Zbl 1088.68817
[51] V. Lifschitz, H. Turner, Splitting a logic program, in: P.V. Hentenryck (Ed.), Proceedings of the Eleventh International Conference on Logic Programming, 1994; V. Lifschitz, H. Turner, Splitting a logic program, in: P.V. Hentenryck (Ed.), Proceedings of the Eleventh International Conference on Logic Programming, 1994
[52] Lin, F.; You, J.-H., Abduction in logic programming: a new definition and an abductive procedure based on rewriting, Artificial Intelligence, 140, 1-2, 175-205 (2002) · Zbl 0999.68092
[53] R. Maimon, S. Browning, Diagrammatic notation and computational structure of gene networks, in: Proceedings of the Second International Conference on Systems Biology, 2000; R. Maimon, S. Browning, Diagrammatic notation and computational structure of gene networks, in: Proceedings of the Second International Conference on Systems Biology, 2000
[54] H. Matsuno, A. Doi, M. Nagasaki, S. Miyano, Hybrid petri net representation of gene regulatory network, in: Pacific Symposium on Biocomputing 2000, 2000; H. Matsuno, A. Doi, M. Nagasaki, S. Miyano, Hybrid petri net representation of gene regulatory network, in: Pacific Symposium on Biocomputing 2000, 2000
[55] Meyers, S.; Friedland, P., Knowledge-based simulation of genetic regulation in bacteriophage lambda, Nucleic Acids Research, 12, 1, 1-9 (1984)
[56] Michael, D.; Oren, M., The p53 and Mdm2 families in cancer, Current Opinions in Genetics & Development, 12, 1, 53-59 (2002)
[57] Missiaen, M.; Bruynooghe, L.; Denecker, M., CHICA: A planning system based on event calculus, Journal of Logic and Computation, 5, 5, 579-602 (1995) · Zbl 0832.68099
[58] K. Oda, T. Kimura, Y. Matsuoka, A. Funahashi, M. Muramatsu, H. Kitano, Molecular interaction map of a macrophage, AfCS Research Report; K. Oda, T. Kimura, Y. Matsuoka, A. Funahashi, M. Muramatsu, H. Kitano, Molecular interaction map of a macrophage, AfCS Research Report
[59] Ogata, H.; Goto, S.; Sato, K.; Fujibuchi, W.; Bono, H.; Kanehisa, M., Kegg: Kyoto encyclopedia of genes and genomes, Nucleic Acids Research, 27, 1, 29-34 (1999)
[60] I. Papatheodorou, A.C. Kakas, M.J. Sergot, Inference of gene relations from microarray data by abduction, in: Lecture Notes in Artificial Intelligence, vol. 3662, 2005, pp. 389-393; I. Papatheodorou, A.C. Kakas, M.J. Sergot, Inference of gene relations from microarray data by abduction, in: Lecture Notes in Artificial Intelligence, vol. 3662, 2005, pp. 389-393 · Zbl 1152.68417
[61] C. Peirce, Collected papers of Charles Sanders Peirce, vols. 1-8, Havard University Press, Cambridge, MA, 1931-1958; C. Peirce, Collected papers of Charles Sanders Peirce, vols. 1-8, Havard University Press, Cambridge, MA, 1931-1958
[62] Peirce, C., Reasoning and the Logic of Things (1992), Havard University Press: Havard University Press Cambridge, MA
[63] Peleg, M.; Yeh, I.; Altman, R. B., Modelling biological processes using workflow and Petri net models, Bioinformatics, 18, 6, 825-837 (2002)
[64] Poole, D., A logical framework for default reasoning, Artificial Intelligence, 36, 1, 27-48 (1988) · Zbl 0647.68094
[65] Poole, D., Explanation and prediction: an architecture for default and abductive reasoning, Computational Intelligence, 5, 1, 97-110 (1989)
[66] Poole, D., Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, 64, 1, 81-129 (1993) · Zbl 0792.68176
[67] D. Poole, R. Goebel, R. Aleliunas, Theorist: A logical reasoning system for default and diagnosis, in: The Knowledge Frontier: Essays in the Representation of Knowledge, 1987, pp. 331-352; D. Poole, R. Goebel, R. Aleliunas, Theorist: A logical reasoning system for default and diagnosis, in: The Knowledge Frontier: Essays in the Representation of Knowledge, 1987, pp. 331-352
[68] Poole, D.; Mackworth, A.; Goebel, R., Computational Intelligence (1998), Oxford University Press: Oxford University Press Oxford · Zbl 0926.68104
[69] (Priami, C., Computational Methods in Systems Biology. Computational Methods in Systems Biology, Lecture Notes in Computer Science, vol. 2602 (2003), Springer Verlag) · Zbl 1015.00031
[70] A. Regev, W. Silverman, E. Shapiro, Representation and simulation of biochemical processes using Π;; A. Regev, W. Silverman, E. Shapiro, Representation and simulation of biochemical processes using Π;
[71] Reggia, R., Diagnostic expert system based on a set covering model, International Journal of Man Machine Studies, 19, 5, 437-460 (1983)
[72] Reiter, R., A theory of diagnosis from first principles, Artificial Intelligence, 13, 1-2, 81-132 (1980) · Zbl 0435.68069
[73] Sambrano, G. R., Developing a navigation and visualization system for signaling pathways, AfCS Reports
[74] Schoeberl, B.; Eichler-Jonsson, C.; Gilles, E.; Muller, G., Computational modeling of the dynamics of the map kinase cascade activated by surface and internalized egf receptors, Nature Bitechnology, 20, 4, 370-375 (2002)
[75] V. Sembugamoorthy, B. Chandrasekaran, Functional representation of devices and compilation of diagnostic problem-solving systems, in: Experience, Memory and Reasoning, 1986, pp. 47-73; V. Sembugamoorthy, B. Chandrasekaran, Functional representation of devices and compilation of diagnostic problem-solving systems, in: Experience, Memory and Reasoning, 1986, pp. 47-73
[76] Shimada, T.; Hagiya, M.; Arita, M.; Nishizaki, S.; Tan, C., Knowledge-based simulation of regulatory action in lambda phage, International Journal of Artificial Intelligence Tools, 4, 4, 511-524 (1995)
[77] Shrager, J.; Langley, P., Computational Models of Scientific Discovery and Theory Formation (1990), Morgan Kaufmann
[78] C. Talcott, S. Eker, M. Knapp, P. Lincoln, K. Laderoute, Pathway logic modeling of protein functional domains in signal transduction, in: Proceedings of the Pacific Symposium on Biocomputing, 2004; C. Talcott, S. Eker, M. Knapp, P. Lincoln, K. Laderoute, Pathway logic modeling of protein functional domains in signal transduction, in: Proceedings of the Pacific Symposium on Biocomputing, 2004
[79] Tamaddoni-Nezhad, A.; Chaleil, R.; Kakas, A.; Muggleton, S., Application of abductive ilp to learning metabolic network inhibition from temporal data, Journal of Machine Learning, 64, 1-3, 209-230 (2006) · Zbl 1103.68443
[80] N. Tran, C. Baral, Reasoning about triggered actions in AnsProlog and its application to molecular interactions in cells, in: Proceedings of the International Conference on the Principles of Knowledge Representation and Reasoning, 2004; N. Tran, C. Baral, Reasoning about triggered actions in AnsProlog and its application to molecular interactions in cells, in: Proceedings of the International Conference on the Principles of Knowledge Representation and Reasoning, 2004
[81] Voit, E. O., Computational Analysis of Biochemical Systems (2000), Cambridge University Press
[82] Zupan, B.; Bratko, I.; Demsar, J.; Juvan, P.; Curk, T.; Borstnik, U.; Beck, J. R.; Halter, J.; Kuspa, A.; Shaulsky, G., GenePath: a system for inference of genetic networks and proposal of genetic experiments, Artificial Intelligence in Medicine, 29, 1-2, 107-130 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.