Random Articles
Reseach Article
BiCross : A Biclustering Technique for Gene Expression Data using One Layer Fixed Weighted Bipartite Graph Crossing Minimization
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 29 - Number 4 |
| Year of Publication: 2011 |
| Authors: Suvendu Kanungo, Gadadhar Sahoo, Manoj Madhava Gore |
10.5120/3553-4880
|
Suvendu Kanungo, Gadadhar Sahoo, Manoj Madhava Gore . BiCross : A Biclustering Technique for Gene Expression Data using One Layer Fixed Weighted Bipartite Graph Crossing Minimization. International Journal of Computer Applications. 29, 4 ( September 2011), 28-34. DOI=10.5120/3553-4880
Abstract
Biclustering has become an important data mining technique for microarray gene expression analysis and profiling, as it provides a local view of the hidden relationships in data, unlike a global view provided by conventional clustering techniques. This technique, in contrast to the conventional clustering techniques, helps in identifying a subset of the genes and a subset of the experimental conditions that together exhibit co-related pattern. In this paper, a biclustering technique using weighted crossing minimization paradigm is proposed, which can mine significant patterns by employing a local search instead of a global search of the input data matrix. We present the novel idea of modelling the gene expression data as a weighted bipartite graph between genes and experimental conditions in order to rearrange the vertices in one layer of this graph. Using this model, an efficient biclustering technique is developed that can mine different types of biclusters and works well in practice for simulated and real world data. The experimental results demonstrate that, our method is scalable to practical gene expression data and has superiority over other similar algorithms in terms of accuracy and computational efficiency.
References
- Cheng, Y. and Church, G. M. 2000. Biclustering of expression data. Proceedings of 8th International Conference on Intelligent Systems for Molecular Biology. 93-103.
- Tanay, A., Sharan, R. and Shamir, R. 2002. Discovering statistically significant biclusters in gene expression data. Bioinformatics, 18,S136-S144.
- Ben-Dor, A., Chor, B., Karp, R. and Yakhini,, Z. 2002. Discovering Local Structure in Gene Expression Data: The Order-Preserving Sub-matrix Problem. Proceedings of Sixth International Conference on Computational Molecular Biology (RECOMB ’02). 49-57.
- Hussain, A. and Abdullah, A. 2006. A new biclustering technique based on crossing minimization. Neurocomputing Journal. 69,1982-1896.
- Wang, L. and Liu, X. 2007. Computing the maximum similarity bi-clusters of gene expression data. Bioinformatics. 23(1),50-56.
- Zimmermann, P., Wille, A., Buhlmann, P., Gruissem, W., Hennig, L., Thiele, L., Zitzler, E., Prelic A. and Bleuler, S. 2007. A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics. 23(1),50-56.
- Dhillon, I. S., Banerjee, A., Merugu, S. and Ghosh, J. 2005. Clustering with bregman divergences. Journal of Machine Learning Research. 6,1705-1749.
- Madeira, S. C. and Oliveira, A. L. 2004. Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics.1(1), 24-45.
- Garey, M. R. and Johnson, D. S. 1983. Crossing number is np-complete. SIAM Journal on Algebraic and Discrete Methods. 4,312-316.
- Tagawa, S., Sugiyama, K. and Toda, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man, and Cybernetics. 11(2),109-125.
- Eades, P. and Wormald, N. 1986.The Median heuristic for drawing 2-layers networks. Technical Report 69, Department of Computer Science, University of Queensland, Brisbane, Australia.
- Pach, J., Shahrokhi, F. and Szegedy, M. 1996. Applications of the crossing number. Algoritmica. 16, 111–117.
- Farhad Shahrokhi, Ondrej Sýkora, László A. Székely and Imrich V. 2001. On bipartite drawings and the linear arrangement problem. SIAM Journal on Computing. 30(6), 1773-1789.
- Jünger, M. and Mutzel, P. 1997. 2-layer straightline crossing minimization, Performance of exact and heuristic algorithms, Journal of Graph Algorithms and Applications. 1(1),1-25.
- Brown, P. O., Alter, O. and Botstein,D. 2000. Singular value decomposition for genome-wide expression data processing and modeling, PNAS. 97,10101-10106.
- Troyannskaya, O., Cantor, M., Sherlock, G., Brown, P., Hastie, T., Tibshirani, R., Botstein, D. and Altman, R. 2001. Missing value estimation methods for dna microarrays. Bioinformatics. 17(6), 1-6.
- Tchagang, A. B. and Tewfik, A.H. 2005. Robust biclustering algorithm (roba) for dna microarray data nalysis, Proceedings of IEEE Workshop on Statistical Signal Processing.
- Yang, Y. and Webb, G.I. 2002. A comparative study of discretization methods for naïve-baysian classifiers. Proceedings of Pacific Rim Knowledge Acquisition Workshop, National Center of Sciences, Tokyo, Japan.
- Devore, J. L. 1995. Probability and Statistics for Engineering and the Sciences, Duxbury Press, 4th edition.
- Munoz, X., Unger, W. and Vrto, I. 2002. One sided crossing minimization is np-hard for sparse graphs. International Symposium on Graph Drawing, London, UK. 115-123, Springer-Verlag.
- Gasch, A.P. 2000. Genomic expression programs in the response of yeast cells to environmental changes. Molecular Biology Cell. 11,4241-4257.
- Kriegel, H., Krӧger, P. and Zimek, A. 2009. Clustering High-Dimensional Data: A Survey on Subspace Clustering, Pattern-Based Clustering, and Correlation Clustering. ACM transactions on knowledge discovery from data. 3(1), Article 1.
- Bergmann, S., Ihmels, J. and Barkai, N. 2004. Defining transcription modules using large-scale gene expression data. Bioinformatics, 20(13),1993-2003.
- Maron-Katz, A., Sharan, R. and Shamir, R. 2003. Click and expander: A system for clustering and visualizing gene expression data. Bioinformatics. 19(14),1787-1799.
- Prelic, A., Zimmermann, P., Barkow, S., Bleuler, S. and Zitzler, E. 2006. Bicat: a biclustering analysis toolbox. Bioinformatics. 22(10),1282-1283.
- Gene Ontology Consortium (2000). Gene ontology: tool for the unification of biology. Nat. Genet.. 25,25-29.
- Berriz, G., Bryant, O., Sander, C. and Roth, F. 2003. Charactering gene sets with FuncAssociate, Bioinformatics, 22,1282-1283.
- Cover, T. M. and Thomas, J. A. 2006. Elements of Information Theory. Wiley.
- Han, J. and Kamber, M. 2011. Data Mining: Concepts and Techniques. Elsevier.
Index Terms
Keywords