Unifying Framework for Rule Semantics: Application to Gene Expression Data

• Autorzy: Agier M. , Petit J-M. , Suzuki E.
• Języki publikacji: EN

Abstrakty

EN

The notion of rules is very popular and appears in different flavors, for example as association rules in data mining or as functional dependencies in databases. Their syntax is the same but their semantics widely differs. In the context of gene expression data mining, we introduce three typical examples of rule semantics and for each one, we point out that Armstrong's axioms are sound and complete. In this setting, we propose a unifying framework in which any "well-formed" semantics for rules may be integrated. We do not focus on the underlying data mining problems posed by the discovery of rules, rather we prefer to discuss the expressiveness of our contribution in a particular application domain: the understanding of gene regulatory networks from gene expression data. The key idea is that biologists have the opportunity to choose - among some predefined semantics - or to define the meaning of their rules which best fits into their requirements. Our proposition has been implemented and integrated into an existing open-source system named MeV of the TIGR environment devoted to microarray data interpretation. An application has been performed on expression profiles of a sub-sample of genes from breast cancer tumors.

Słowa kluczowe

EN

rules; implication; Armstrong's axiom system; data mining

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 4
• Strony: 543--559
• Opis fizyczny: bibliogr. 32 poz., wykr.

Twórcy

autor

Agier M.

autor

Petit J-M.

autor

Suzuki E.

• LIMOS, UMR 6158 CNRS, Univ. Clermont-Ferrand II, France,

Bibliografia

• [1] Agier, M., Chabaud, V., Petit, J.-M., Sylvain, V., D'Incan, C., Vidal, V., Bignon, Y.-J.: Towards Meaningful Rules between Genes from Gene Expression Data, poster, MGED'03, Aix en Provence, 2003.
• [2] Agrawal, R., Imielinski, T., Swami, A. N.: Mining Association Rules between Sets of Items in Large Databases, Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington D.C., ACM Press, 1993.
• [3] Armstrong, W. W.: Dependency Structures of Data Base Relationships, Proc. of the IFIP Congress 1974, 1974.
• [4] Aussem, A., Petit, J.-M.: є-functional Dependency Inference: Application to DNA Microarray Expression Data, Bases de donn´ees avanc´ees (BDA'02) (P. Pucheral, Ed.), Evry, France, Octobre 2002.
• [5] Becquet, C., Blachon, S., Jeudy, B., Boulicaut, J.-F., Gandrillon, O.: Strong-Association-Rule Mining For Large-Scale Gene-Expression Data Analysis: a Case Study on Human SAGE Data, Genome Biology, 3(12), 2002.
• [6] Beeri, C., Berstein, P.: Computational Problems Related to the Design of Normal Form Relation Schemes, ACM TODS, 4(1), 1979, 30-59.
• [7] Berrar, D. P., Granzow, M., Dubitzky, W.: A Practical Approach to Microarray Data Analysis, Kluwer Academic Publishers, 2002.
• [8] Brin, S., Motwani, R., Ullman, J. D., Tsur, S.: Dynamic Itemset Counting and Implication Rules for Market Basket Data, SIGMOD Conference, 1997.
• [9] Caspard, N., Monjardet, B.: The Lattices of Closure Systems, Closure Operators, and Implicational Systems on a Finite Set: A Survey, Discrete Applied Mathematics, 127(2), 2003, 241-269.
• [10] Cong, G., Xu, X., Pan, F., A.K.H.Tung, Yang, J.: FARMER: Finding Interesting Rule Groups in Microarray Datasets, SIGMOD, 2004.
• [11] Creighton, C., Hanash, S.: Mining Gene Expression Databases for Association Rules, Bioinformatics, 19, 2003, 79-86.
• [12] Demetrovics, J., Thi, V.: Some Remarks On Generating Armstrong And Inferring Functional Dependencies Relation, Acta Cybernetica, 12(2), 1995, 167-180.
• [13] Eisen, M., Spellman, P., Brown, P., Botstein, D.: Gene Expression Profiling Predicts Clinical Outcome of Breast Cancer, Proc Natl Acad Sci, 95(25), 1998, 14863-14868.
• [14] Eiter, T., Gottlob, G.: Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, 24(6), 1995, 1278-1304.
• [15] Fuhrman, S., Cunningham, M., Wen, X., Zweiger, G., Seilhamer, J., Somogyi, R.: The Application of Shannon Entropy in the Prediction of Putative Drug Targets, BioSystems, 55, 2000, 5-14.
• [16] Ganter, B., Wille, R.: Formal Concept Analysis, Springer-Verlag, 1999.
• [17] Gottlob, G., Libkin, L.: Investigations on Armstrong Relations, Dependency Inference, and Excluded Functional Dependencies, Acta Cybernetica, 9(4), 1990, 385-402.
• [18] Gruvberger, S., Ringner, M., Chen, Y., Panavally, S., Saal, L., Borg, A., Ferno, M., Peterson, C., Meltzer, P.: Estrogen Receptor Status in Breast Cancer is Associated with Remarkably Distinct Gene Expression Patterns, Cancer Research, 61(16), 2001, 5979-5984.
• [19] Guerin,M., Sheng, Z.-M., Andrieu, N., Riou, G.: Strong Association between C-myb and Oestrogen-receptor Expression in Human Breast Cancer, Oncogene, 5(1), 1990, 131-135.
• [20] Guigues, J.-L., Duquenne, V.: Familles Minimales d'Implications Informatives R´esultant d'un Tableau de Donn´ees Binaires, Math. Sci. Humaines, 24(95), 1986, 5-18.
• [21] Icev, A., Ruiz, C., Ryder, E. F.: Distance-enhanced Association Rules for Gene Expression, BIOKDD'03, in conjunction with ACM SIGKDD, Washington, DC, USA, 2003.
• [22] Lopes, S., Petit, J.-M., Lakhal, L.: Functional and Approximate Dependencies Mining: Databases and FCA Point of View, JETAI, 14(2/3), 2002, 93-114.
• [23] Maier, D.: Minimum Covers in the Relational Database Model, JACM, 27(4), 1980, 664-674.
• [24] Mannila, H., Räihä, K.-J.: Algorithms for Inferring Functional Dependencies from Relations, DKE, 12, 1994, 83-99.
• [25] Mannila, H., Räihä, K.-J.: The Design of Relational Databases, Second edition, Addison-Wesley, 1994.
• [26] Mannila, H., Toivonen, H.: Levelwise Search and Borders of Theories in Knowledge Discovery, DMKD, 1(3), 1997, 241-258.
• [27] Piatetsky-Shapiro, G.: Discovery, Analysis, and Presentation of Strong Rules, in: Knowledge Discovery in Databases, AAAI/MIT Press, 1991, ISBN 0-262-62080-4, 229-248.
• [28] Saeed, A., Sharov, V., White, J., Li, J., Liang, W., Bhagabati, N., Braisted, J., Klapa, M., Currier, T., Thiagarajan, M., Sturn, A., Snuffin, M., Rezantsev, A., Popov, D., Ryltsov, A., Kostukovich, E., Borisovsky, I., Liu, Z., Vinsavich, A., Trush, V., Quackenbush, J.: TM4: a Free, Open-Source System for Microarray Data Management and Analysis, Biotechniques, 34(2), 2003, 374-78.
• [29] Scherf, U., al.: A Gene Expression Database for the Molecular Pharmacology of Cancer, Nature Genetics, 24(3), 2000, 236-244.
• [30] Shena, M., al.: Quantitative Monitoring of Gene Expression Patterns with a cDNA Microarray, Science, (270), 1995, 467-470.
• [31] Tan, P.-N., Kumar, V., Srivastava, J.: Selecting the Right Objective Measure for Association Analysis, Information Systems, 29(4), 2004, 293-313.
• [32] van't Veer, L., Dai, H., Vijver, M., He, Y., Hart, A., Mao, M., Peterse, H., Kooy, K., Marton, M., Witteveen, A., Schreiber, G., Kerkhoven, R., Roberts, C., Linsley, P., Bernards, R., Friend, S.: Gene Expression Profiling Predicts Clinical Outcome of Breast Cancer, Nature, 415(6871), 2002, 530-536.