×

zbMATH — the first resource for mathematics

Completing causal networks by meta-level abduction. (English) Zbl 1273.68375
Summary: Meta-level abduction is a method to abduce missing rules in explaining observations. By representing rule structures of a problem in a form of causal networks, meta-level abduction infers missing links and unknown nodes from incomplete networks to complete paths for observations. We examine applicability of meta-level abduction on networks containing both positive and negative causal effects. Such networks appear in many domains including biology, in which inhibitory effects are important in several biological pathways. Reasoning in networks with inhibition involves nonmonotonic inference, which can be realized by making default assumptions in abduction. We show that meta-level abduction can consistently produce both positive and negative causal relations as well as invented nodes. Case studies of meta-level abduction are presented in p53 signaling networks, in which causal relations are abduced to suppress a tumor with a new protein and to stop DNA synthesis when damage has occurred. Effects of our method are also analyzed through experiments of completing networks randomly generated with both positive and negative links.

MSC:
68T27 Logic in artificial intelligence
68T05 Learning and adaptive systems in artificial intelligence
92C42 Systems biology, networks
Software:
GenePath; SOLAR; TopLog
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akutsu, T.; Tamura, T.; Horimoto, K., Completing networks using observed data, No. 5809, 126-140, (2009), Berlin · Zbl 1262.68046
[2] Christiansen, H., Abduction and induction combined in a metalogic framework, 195-211, (2000) · Zbl 1031.03515
[3] Corapi, D.; Russo, A.; Lupu, E. C., Inductive logic programming as abductive search, 54-63, (2010) · Zbl 1237.68203
[4] Costantini, S.; Kakas, A. C. (ed.); Sadri, F. (ed.), Meta-reasoning: a survey, No. 2408, 253-288, (2002), Berlin · Zbl 1012.68190
[5] Damásio, C. V.; Pereira, L. M.; Gabbay, D. M. (ed.); Smets, P. (ed.), A survey of paraconsistent semantics for logic programs, No. 2, 241-320, (1998), Berlin · Zbl 0936.68021
[6] Dietterich, T.; Domingos, P.; Getoor, L.; Muggleton, S.; Tadepalli, P., Structured machine learning: the next ten years, Machine Learning, 73, 3-23, (2008)
[7] Dimopoulos, Y.; Kakas, A.; Raedt, L. (ed.), Abduction and inductive learning, 144-171, (1996), Amsterdam
[8] Eshghi, K., Abductive planning with event calculus, 562-579, (1988)
[9] Fayruzov, T.; Janssen, J.; Cornelis, C.; Vermeir, D.; Cock, M., Extending Boolean regulatory network models with answer set programming, 207-212, (2010)
[10] Flach, P. A. & Kakas, A. C. (Eds.) (2000). Abduction and induction—essays on their relation and integration. Norwell: Kluwer Academic. · Zbl 0992.03006
[11] Gat-Viks, I.; Shamir, R., Chain functions and scoring functions in genetic networks, Bioinformatics, 19, i108-i117, (2003)
[12] Hill, P. M.; Gallagher, J.; Gabbay, D. M. (ed.); Hogger, C. J. (ed.); Robinson, J. A. (ed.), Meta-programming in logic programming, No. 5, 421-497, (1998), London · Zbl 0900.68137
[13] Inoue, K., Linear resolution for consequence finding, Artificial Intelligence, 56, 301-353, (1992) · Zbl 0805.68105
[14] Inoue, K., Induction as consequence finding, Machine Learning, 55, 109-135, (2004) · Zbl 1101.68078
[15] Inoue, K., Logic programming for Boolean networks, 924-930, (2011)
[16] Inoue, K.; Haneda, H., Learning abductive and nonmonotonic logic programs, 213-231, (2000) · Zbl 1032.68690
[17] Inoue, K.; Bando, H.; Nabeshima, H., Inducing causal laws by regular inference, No. 3625, 154-171, (2005), Berlin · Zbl 1134.68472
[18] Inoue, K.; Iwanuma, K.; Nabeshima, H., Consequence finding and computing answers with defaults, Journal of Intelligent Information Systems, 26, 41-58, (2006)
[19] Inoue, K.; Sato, T.; Ishihata, M.; Kameya, Y.; Nabeshima, H., Evaluating abductive hypotheses using an EM algorithm on bdds, 810-815, (2009)
[20] Inoue, K.; Furukawa, K.; Kobayashi, I.; Nabeshima, H.; Raedt, L. (ed.), Discovering rules by meta-level abduction, No. 5989, 49-64, (2010), Berlin · Zbl 1286.68380
[21] Inoue, K.; Doncescu, A.; Nabeshima, H.; Frasconi, P. (ed.); Lisi, F. A. (ed.), Hypothesizing about networks with positive and negative effects by meta-level abduction, No. 6489, 114-129, (2011), Berlin · Zbl 1329.68217
[22] Ishii, N.; Nakahigashi, K.; Baba, T.; etal., Multiple high-throughput analyses monitor the response of E. coli to perturbations, Science, 316, 593-597, (2007)
[23] Iwanuma, K.; Inoue, K., Minimal answer computation and SOL, No. 2424, 245-257, (2002), Berlin · Zbl 1013.68210
[24] Johnson, D.; Yannakakis, M.; Papadimitriou, C., On generating all maximal independent sets, Information Processing Letters, 27, 119-123, (1988) · Zbl 0654.68086
[25] Kakas, A. C.; Riguzzi, F., Learning with abduction, No. 1297, 181-188, (1997), Berlin
[26] Kauffman, S. A. (1993). The origins of order: self-organization and selection in evolution. London: Oxford University Press.
[27] Kimber, T.; Broda, K.; Russo, A., Induction on failure: learning connected Horn theories, No. 5753, 169-181, (2009), Berlin · Zbl 1258.68031
[28] King, R. D.; Whelan, K. E.; Jones, F. M.; Reiser, P. G. K.; Bryant, C. H.; Muggleton, S. H.; Kell, D. B.; Oliver, S. G., Functional genomic hypothesis generation and experimentation by a robot scientist, Nature, 427, 247-252, (2004)
[29] Kowalski, R. A.; Lloyd, J. W. (ed.), Problems and promises of computational logic, 1-36, (1990)
[30] Kowalski, R. A.; Sergot, M. J., A logic-based calculus of events, New Generation Computing, 4, 67-95, (1986) · Zbl 1356.68221
[31] Lamma, E.; Mello, P.; Milano, M.; Riguzzi, F.; Esposito, F.; Ferilli, S.; Semeraro, G., Cooperation of abduction and induction in logic programming, 233-252, (2000) · Zbl 1032.68558
[32] Leitgeb, H., Nonmonotonic reasoning by inhibition nets, Artificial Intelligence, 128, 161-201, (2001) · Zbl 0976.68122
[33] Lejay, G.; Inoue, K.; Doncescu, A., Application of meta-level abduction for the treatment of hypertension using SOLAR, 495-500, (2011), Los Alamitos
[34] Mandal, S.; Guptan, P.; Owusu-Ansah, E.; Banerjee, U., Mitochondrial regulation of cell cycle progression during development as revealed by the tenured mutation in drosophila, Developmental Cell, 9, 843-854, (2005)
[35] Mandal, S.; Freije, W. A.; Guptan, P.; Banerjee, U., Metabolic control of G1-S transition: cyclin E degradation by p53-induced activation of the ubiquitin-proteasome system, The Journal of Cell Biology, 188, 473-479, (2010)
[36] Meek, D. W., Tumour suppression by p53: a role for the DNA damage response?, Nature Reviews. Cancer, 9, 714-723, (2009)
[37] Mooney, R., Integrating abduction and induction in machine learning, 181-191, (2000) · Zbl 1032.68701
[38] Moyle, S., Using theory completion to learn a robot navigation control programs, No. 2583, 182-197, (2003), Berlin · Zbl 1017.68545
[39] Muggleton, S., Inverse entailment and progol, New Generation Computing, 13, 245-286, (1995)
[40] Muggleton, S.; Bryant, C., Theory completion and inverse entailment, No. 1866, 130-146, (2000), Berlin · Zbl 0994.68623
[41] Muggleton, S.; Buntine, W., Machine invention of first-order predicate by inverting resolution, 339-351, (1988), San Mateo
[42] Muggleton, S.; Santos, J. C. A.; Tamaddoni-Nezhad, A., Toplog: ILP using a logic program declarative bias, No. 5366, 687-692, (2008), Berlin · Zbl 1185.68171
[43] Muggleton, S. H.; Raedt, L.; Poole, D.; Bratko, I.; Flach, P.; Inoue, K.; Srinivasan, A., ILP turns 20—biography and future challenges, Machine Learning, 86, 3-23, (2012) · Zbl 1243.68014
[44] Nabeshima, H.; Iwanuma, K.; Inoue, K., SOLAR: a consequence finding system for advanced reasoning, No. 2796, 257-263, (2003), Berlin · Zbl 1274.68412
[45] Nabeshima, H.; Iwanuma, K.; Inoue, K.; Ray, O., SOLAR: an automated deduction system for consequence finding, AI Communications, 23, 183-203, (2010) · Zbl 1205.68362
[46] Nakahigashi, K.; Toya, Y.; Ishii, N.; Soga, T.; Hasegawa, M.; Watanabe, H.; Takai, Y.; Honma, M.; Mori, H.; Tomita, M., Systematic phenome analysis of Escherichia coli multiple-knockout mutants reveals hidden reactions in central carbon metabolism, Molecular Systems Biology, 5, 306, (2009)
[47] Otero, R. P., Induction of the indirect effects of actions by monotonic methods, No. 3625, 279-294, (2005), Berlin · Zbl 1134.68478
[48] Pearl, J. (2009). Causality: models, reasoning, and inference (2nd ed.). Cambridge: Cambridge University Press. · Zbl 1188.68291
[49] Poole, D., A logical framework for default reasoning, Artificial Intelligence, 36, 27-47, (1988) · Zbl 0647.68094
[50] Prives, C.; Hall, P. A., The p53 pathway, Journal of Pathology, 187, 112-126, (1999)
[51] Ray, O., Towards a rational approach for the logical modelling of inhibition in metabolic networks, 18-923, (2009)
[52] Ray, O.; Inoue, K., A consequence finding approach for full clausal abduction, No. 4755, 173-184, (2007), Berlin
[53] Ray, O.; Inoue, K., Mode-directed inverse entailment for full clausal theories, No. 4894, 225-238, (2008), Berlin · Zbl 1136.68502
[54] Ray, O.; Broda, K.; Russo, A., Hybrid abductive inductive learning: a generalisation of progol, No. 2835, 311-328, (2003), Berlin · Zbl 1263.68144
[55] Ray, O.; Whelan, K.; King, R., Logic-based steady-state analysis and revision of metabolic networks with inhibition, 661-666, (2010)
[56] Reiser, P. G. K.; King, R. D.; Kell, D. B.; Muggleton, S. H.; Bryant, C. H.; Oliver, S. G., Developing a logical model of yeast metabolism, Electronic Transactions in Artificial Intelligence, 5-B2, 223-244, (2001)
[57] Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 81-132, (1980) · Zbl 0435.68069
[58] Sakama, C., Abductive generalization and specialization, 253-265, (2000) · Zbl 1032.68761
[59] Schaub, T.; Thiele, S., Metabolic network expansion with answer set programming, No. 5649, 312-326, (2009), Berlin
[60] Schurz, G., Patterns of abduction, Synthese, 164, 201-234, (2008) · Zbl 1261.03064
[61] Shanahan, M., An abductive event calculus planner, The Journal of Logic Programming, 44, 207-239, (2000) · Zbl 0957.68106
[62] Shmulevich, I.; Dougherty, E. R.; Kim, S.; Zhang, W., Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks, Bioinformatics, 18, 261-274, (2002)
[63] Tamaddoni-Nezhad, A.; Chaleil, R.; Kakas, A.; Muggleton, S., Application of abductive ILP to learning metabolic network inhibition from temporal data, Machine Learning, 65, 209-230, (2006) · Zbl 1103.68443
[64] T’kindt, V.; Bouibede-Hocine, K.; Esswein, C., Counting and enumeration complexity with application to multicriteria scheduling, Annals of Operations Research, 153, 215-234, (2007) · Zbl 1142.68038
[65] Tran, N.; Baral, C., Hypothesizing about signaling networks, Journal of Applied Logic, 7, 253-274, (2009) · Zbl 1168.92002
[66] Wagner, A. (2005). Robustness and evolvability in living systems. Princeton: Princeton University Press.
[67] Yamamoto, A., Using abduction for induction based on bottom generalization, 267-280, (2000) · Zbl 1032.68762
[68] Yamamoto, Y.; Inoue, K.; Doncescu, A.; Lodhi, H. (ed.); Muggleton, S. (ed.), Integrating abduction and induction in biological inference using CF-induction, 213-234, (2010), New York
[69] Zupan, B.; Demsar, J.; Bratko, I.; Juvan, P.; Halter, J. A.; Kuspa, A.; Shaulsky, G., Genepath: a system for automated construction of genetic networks from mutant data, Bioinformatics, 19, 383-389, (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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.