Abstract
Biclustering gene expression data is the problem of extracting submatrices of genes and conditions exhibiting significant correlation across both the rows and the columns of a data matrix of expression values. We provide a method, LEB (Localize-and-Extract Biclusters) which reduces the search space into local neighborhoods within the matrix by first localizing correlated structures. The localization procedure takes its roots from effective use of graph-theoretical methods applied to problems exhibiting a similar structure to that of biclustering. Once interesting structures are localized the search space reduces to small neighborhoods and the biclusters are extracted from these localities. We evaluate the effectiveness of our method with extensive experiments both using artificial and real datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdullah, A., Hussain, A.: A new biclustering technique based on crossing minimization. Neurocomputing 69(16-18), 1882–1896 (2006)
Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discrete Appl. Math. 145(1), 11–21 (2004)
Barkow, S., Bleuler, S., Prelic, A., Zimmermann, P., Zitzler, E.: Bicat: a biclustering analysis toolbox. Bioinformatics (Oxford, England) 22(10), 1282–1283 (2006)
Ben-Dor, A., Chor, B., Karp, R., Yakhini, Z.: Discovering local structure in gene expression data: the order-preserving submatrix problem. In: RECOMB 2002: Proceedings of the sixth annual international conference on Computational biology, pp. 49–57. ACM, New York (2002)
Ben-Hur, A., Noble, W.S.: Kernel methods for predicting protein–protein interactions. Bioinformatics 21(1), 38–46 (2005)
Bergmann, S., Ihmels, J., Barkai, N.: Iterative signature algorithm for the analysis of large-scale gene expression data. Physical review. E, Statistical, nonlinear, and soft matter physics 67(3 Pt 1) (March 2003)
Berriz, G.F., King, O.D., Bryant, B., Sander, C., Roth, F.P.: Characterizing gene sets with funcassociate. Bioinformatics 19(18), 2502–2504 (2003)
Bryan, K., Cunningham, P.: Bottom-up biclustering of expression data. In: Proceedings of the 2006 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2006, vol. (4133177), pp. 232–239 (2006)
Çakiroglu, O.A., Erten, C., Karatas, Ö., Sözdinler, M.: Crossing minimization in weighted bipartite graphs. Journal of Discrete Algorithms (2008), doi:10.1016/j.jda.2008.08.003
Chen, K., Hu, Y.-J.: Bicluster analysis of genome-wide gene expression. In: 2006 IEEE Symposium on Computational Intelligence and Bioinformatics and Computational Biology, 2006. CIBCB 2006, pp. 1–7 (September 2006)
Cheng, Y., Church, G.M.: Biclustering of expression data. In: Altman, R., Bailey, T.L., Bourne, P., Gribskov, M., Lengauer, T., Shindyalov, I.N. (eds.) Proceedings of the 8th International Conference on Intelligent Systems for Molecular (ISMB 2000), Menlo Park, CA, August 16–23, pp. 93–103. AAAI Press, Menlo Park (2000)
Getz, G., Levine, E., Domany, E.: Coupled two-way clustering analysis of gene microarray data. In: Proc. Natl. Acad. Sci. USA, pp. 12079–12084 (2000)
Hartigan, J.A.: Direct clustering of a data matrix. Journal of the American Statistical Association 67(337), 123–129 (1972)
Mewes, H.W., Frishman, D., Güldener, U., Mannhaupt, G., Mayer, K., Mokrejs, M., Morgenstern, B., Münsterkötter, M., Rudd, S., Weil, B.: Mips: a database for genomes and protein sequences. Nucleic Acids Res. 30(1), 31–34 (2002)
Kluger, Y., Basri, R., Chang, J.T., Gerstein, M.: Spectral biclustering of microarray data: coclustering genes and conditions. Journal Genome Res PMID 12671006 13, 703–716 (2003)
Madeira, S.C., Oliveira, A.L.: Biclustering algorithms for biological data analysis: A survey. IEEE/ACM Trans. on Comp. Biol. and Bioinformatics (TCBB) 1(1), 24–45 (2004)
Mehlhorn, K., Naher, S.: Leda: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)
Murali, T.M., Kasif, S.: Extracting conserved gene expression motifs from gene expression data. In: Pacific Symposium on Biocomputing, pp. 77–88 (2003)
Peeters, R.: The maximum edge biclique problem is np-complete. Discrete Appl. Math. 131(3), 651–654 (2003)
Prelic, A., Bleuler, S., Zimmermann, P., Wille, A., Buhlmann, P., Gruissem, W., Hennig, L., Thiele, L., Zitzler, E.: A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics 22, 1122–1129 (2006)
Sharan, R., Maron-katz, A., Shamir, R.: Click and expander: A system for clustering and visualizing gene expression data. Bioinformatics 19, 1787–1799 (2003)
Tanay, A., Sharan, R., Shamir, R.: Discovering statistically significant biclusters in gene expression data. Bioinformatics 18(suppl. 1) (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erten, C., Sözdinler, M. (2009). Biclustering Expression Data Based on Expanding Localized Substructures. In: Rajasekaran, S. (eds) Bioinformatics and Computational Biology. BICoB 2009. Lecture Notes in Computer Science(), vol 5462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00727-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-00727-9_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00726-2
Online ISBN: 978-3-642-00727-9
eBook Packages: Computer ScienceComputer Science (R0)