An Algorithm for Recomputing Concepts in Microarray Data Analysis by Biological Lattice
Hidenobu Hashikami*, Takanari Tanabata**, Fumiaki Hirose***,
Nur Hasanah*, Kazuhito Sawase*, and Hajime Nobuhara*
*Department of Intelligent Interaction Technologies, University of Tsukuba, 1-1-1 Tennoudai, Tsukuba Science City, Ibaraki 305-8573, Japan
**Gene Discovery Research Group, RIKEN Center for Sustainable Resource Science, 3-1-1 Koyadai, Tsukuba, Ibaraki 305-0074, Japan
***Functional Transgenic Crops Research Unit, National Institute of Agrobiological Sciences (NIAS), 2-1-2 Kannondai, Tsukuba, Ibaraki 305-8602, Japan
A data-analytic system is proposed for microarray gene expression data based on Formal Concept Analysis (FCA). The purpose of the system is to systematically organize data and to build a complete lattice that analyzes complex relations among genes and give biological interpretation of microarray data. In the system, formal concept analysis handles complex relations, so the microarray data is binarized by setting up a threshold. When change occurs in a conventional algorithm, formal concepts that are nodes of the lattice were calculated from the beginning, but the calculation is inefficient. This paper proposes a new algorithm that has two phase of matrix detection and updating concepts to efficiently update only altered concepts from previously generated concepts. Experiments on run time show that the algorithm takes an average of 0.94 seconds to process real microarray data containing of 43,734 genes and 6 gene expression values.
-  S. Knudsen, “A biologist’s guide to analysis of DNA microarray data,” John Wiley and Sons, 2002.
-  J. Kim, H. J. Chung, Y. Jung, K. K. Kim, and J. H. Kim, “Bio-Lattice: a framework for the biological interpretation of microarray gene expression data using concept lattice analysis,” J. of Biomedical Informatics, Vol.41, pp. 232-241, 2008.
-  T. Tanabata, F. Hirose, H. Hashikami, and H. Nobuhara, “Interactive data mining tool for microarray data analysis using formal concept analysis,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.16, No.2, pp. 273-281, 2012.
-  B. Ganter, G. Stumme, and R. Wille (Eds.), “Formal concept analysis: foundation and application,” LNAI 3626, 2005.
-  U. Priss, “Formal concept analysis in information science,” Annual Review of Information Science and Technology, Vol.40, 2006.
-  R. Wille, “Restructuring lattice theory: an approach based on hierarchies of concepts,” In I. Rival (Ed.), Ordered sets, Reidel, Dordrecht-Boston, pp. 445-470, 1982.
-  H. Hashikami, N. Hasanah, K. Sawase, T. Tanabata, F. Hirose, and H. Nobuhara, “An efficient recomputing concepts algorithm for microarray data analysis using biological lattice,” Proc. 2011 Int. Workshop Smart Info-Media Systems in Asia (SISA 2011), Nagasaki, RS2-10, 2011.
-  U. Priss, “Formal concept analysis homepage, formal concept analysis algorithms,” 2007.
-  B. Ganter, “Two basic algorithms in concept analysis,” Technical Report FB4-Preprint, TH Darmstadt, 831, 1984.
-  P. Krajca, J. Outrata, and V. Vychodil, “Advances in algorithms based on CbO,” CLA’2010, 2010.
-  S. Andrews, “In-Close, a fast algorithm for computing formal concepts,” In Rudolph, Dau, Kuznetsov (Eds.), Supplementary Proc. of ICCS’09, CEUR WS 483, 2009.
-  S. Andrews, “In-Close2, a high performance formal concept miner,” Conceptual Structures for Discovering Knowledge – 19th Int. Conf. on Conceptual Structures, ICCS 2011, pp. 25-29, 2011.
-  P. Krajca, J. Outrata, and V. Vychodil, “Parallel recursive algorithm for FCA,” R. Belohlavek and S. O. Kuznetsov (Eds.), Proc. CLA 2008, CEUR WS, 433, 2008.
-  R. Godin, R. Missaoui, and H. Alaoui, “Incremental concept formation algorithms based on Galois (concept) lattices,” Computational Intelligence, Vol.11, No.2, pp. 246-267, 1995.
-  D. Merwe, S. Obiedkov, and D. Kourie, “AddIntent: A new incremental algorithm for constructing concept lattices,” Concept Lattices, 2nd Int. Conf. on Formal Concept Analysis, ICFCA 2004, Vol.2961, pp. 372-385, 2004.
-  J. Poelmans, P. Elzinga, S. Viaene, and G. Dedene, “Formal concept analysis in knowledge discovery:a survey,” ICCS, ser. LNCS, Vol.6208, pp. 139-153, 2010.
-  C. Carpineto and G. Romano, “Concept data analysis: theory and applications,” John Wiley and Sons, 2010.
-  K. Sawase and H. Nobuhara, “Management system for tagged image database using lattice structure,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.14, No.2, pp. 150-154, 2010.
-  T. Tanabata, K. Sawase, H. Nobuhara, and B. Bede, “Interactive data mining for large-scale image databases based on formal concept analysis,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.14, No.3, pp. 303-308, 2010.
-  T. Itoh et al., “Curated genome annotation of Oryza sativa ssp. japonica and comparative genome analysis with Arabidopsis thaliana,” Genome Res., Vol.17, No.2, pp. 175-183, 2007.
-  Rice Annotation Project, “The rice annotation project database (RAP-DB): 2008 update,” Nucleic Acids Res., 36:D1028-D1033, 2008.
-  Q. Wu and Z. Liu, “Real formal concept analysis based on greyrough set theory,” Knowledge-Based Systems, Vol.22, No.1, pp. 38-45, 2009.
-  K. M. Folta, M. A. Pontin, G. Karlin-Neumann, R. Bottini, and E. P. Spalding, “Genomic and physiological studies of early cryptochrome 1 action demonstrate roles for auxin and gibberellin in the control of hypocotyl growth by blue light,” The Plant J., Vol.36, pp. 203-214, 2003.