{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T12:29:53Z","timestamp":1692534593958},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: 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. Even the simplest versions of the problem are computationally hard. Most of the proposed solutions therefore employ greedy iterative heuristics that locally optimize a suitably assigned scoring function.<\/jats:p>\n               <jats:p>Methods: We provide a fast and simple pre-processing algorithm called localization that reorders the rows and columns of the input data matrix in such a way as to group correlated entries in small local neighborhoods within the matrix. The proposed localization algorithm takes its roots from effective use of graph-theoretical methods applied to problems exhibiting a similar structure to that of biclustering. In order to evaluate the effectivenesss of the localization pre-processing algorithm, we focus on three representative greedy iterative heuristic methods. We show how the localization pre-processing can be incorporated into each representative algorithm to improve biclustering performance. Furthermore, we propose a simple biclustering algorithm, Random Extraction After Localization (REAL) that randomly extracts submatrices from the localization pre-processed data matrix, eliminates those with low similarity scores, and provides the rest as correlated structures representing biclusters.<\/jats:p>\n               <jats:p>Results: We compare the proposed localization pre-processing with another pre-processing alternative, non-negative matrix factorization. We show that our fast and simple localization procedure provides similar or even better results than the computationally heavy matrix factorization pre-processing with regards to H-value tests. We next demonstrate that the performances of the three representative greedy iterative heuristic methods improve with localization pre-processing when biological correlations in the form of functional enrichment and PPI verification constitute the main performance criteria. The fact that the random extraction method based on localization REAL performs better than the representative greedy heuristic methods under same criteria also confirms the effectiveness of the suggested pre-processing method.<\/jats:p>\n               <jats:p>Availability: \u00a0Supplementary material including code implementations in LEDA C++ library, experimental data, and the results are available at http:\/\/code.google.com\/p\/biclustering\/<\/jats:p>\n               <jats:p>Contacts: \u00a0cesim@khas.edu.tr; melihsozdinler@boun.edu.tr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq473","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T02:45:35Z","timestamp":1282617935000},"page":"2594-2600","source":"Crossref","is-referenced-by-count":6,"title":["Improving performances of suboptimal greedy iterative biclustering heuristics via localization"],"prefix":"10.1093","volume":"26","author":[{"given":"Cesim","family":"Erten","sequence":"first","affiliation":[{"name":"1 Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083 and 2Department of Computer Engineering, Bogazi\u00e7i University, Bebek, Istanbul 34342, Turkey"}]},{"given":"Melih","family":"S\u00f6zdinler","sequence":"additional","affiliation":[{"name":"1 Department of Computer Engineering, Kadir Has University, Cibali, Istanbul 34083 and 2Department of Computer Engineering, Bogazi\u00e7i University, Bebek, Istanbul 34342, Turkey"}]}],"member":"286","published-online":{"date-parts":[[2010,8,23]]},"reference":[{"key":"2023012507543721100_B1","doi-asserted-by":"crossref","first-page":"1882","DOI":"10.1016\/j.neucom.2006.02.018","article-title":"A new biclustering technique based on crossing minimization","volume":"69","author":"Abdullah","year":"2006","journal-title":"Neurocomputing"},{"key":"2023012507543721100_B2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.dam.2003.09.004","article-title":"Consensus algorithms for the generation of all maximal bicliques","volume":"145","author":"Alexe","year":"2004","journal-title":"Disc. Appl. Math."},{"key":"2023012507543721100_B3","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1093\/bioinformatics\/btl099","article-title":"Bicat: a biclustering analysis toolbox","volume":"22","author":"Barkow","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B4","first-page":"49","article-title":"Discovering local structure in gene expression data: the order-preserving submatrix problem","volume-title":"Proceedings of the International Conference on Computing Biology, RECOMB '02","author":"Ben-Dor","year":"2002"},{"issue":"Suppl. 1","key":"2023012507543721100_B5","doi-asserted-by":"crossref","first-page":"i38","DOI":"10.1093\/bioinformatics\/bti1016","article-title":"Kernel methods for predicting protein-protein interactions","volume":"21","author":"Ben-Hur","year":"2005","journal-title":"Bioinformatics"},{"issue":"3 Pt 1","key":"2023012507543721100_B6","doi-asserted-by":"crossref","first-page":"031902","DOI":"10.1103\/PhysRevE.67.031902","article-title":"Iterative signature algorithm for the analysis of large-scale gene expression data","volume":"67","author":"Bergmann","year":"2003","journal-title":"Phys. Rev. E, Stat., Nonlinear, Soft Matter Phys."},{"key":"2023012507543721100_B7","doi-asserted-by":"crossref","first-page":"2502","DOI":"10.1093\/bioinformatics\/btg363","article-title":"Characterizing gene sets with funcassociate","volume":"19","author":"Berriz","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B8","first-page":"1","article-title":"Bottom-up biclustering of expression data","volume-title":"IEEE Symposium on Computing Intelligence and Bioinformatics and Computing Biology","author":"Bryan","year":"2006"},{"key":"2023012507543721100_B9","doi-asserted-by":"crossref","first-page":"1426","DOI":"10.1016\/j.compbiomed.2007.01.005","article-title":"Possibilistic approach for biclustering microarray data","volume":"37","author":"Cano","year":"2007","journal-title":"Comp. Biol. Med."},{"key":"2023012507543721100_B10","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1186\/1471-2105-7-78","article-title":"Biclustering of gene expression data by non-smooth non-negative matrix factorization","volume":"7","author":"Carmona-Saez","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012507543721100_B11","first-page":"439","article-title":"Crossing minimization in weighted bipartite graphs","volume":"7","author":"\u00c7akiroglu","year":"2009","journal-title":"J. Disc. Algs"},{"key":"2023012507543721100_B12","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1186\/1471-2105-9-210","article-title":"Identification of coherent patterns in gene expression data using an efficient biclustering algorithm and parallel coordinate visualization","volume":"9","author":"Cheng","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012507543721100_B13","first-page":"93","article-title":"Biclustering of expression data","volume-title":"Proceedings of the 8th International Conference on Intelligent Systems for Molecular, ISMB'00)","author":"Cheng","year":"2000"},{"key":"2023012507543721100_B14","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1186\/1471-2164-10-288","article-title":"Predicting protein-protein interactions in arabidopsis thaliana through integration of orthology, gene ontology and co-expression","volume":"10","author":"De Bodt","year":"2009","journal-title":"BMC Genomics"},{"key":"2023012507543721100_B15","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","article-title":"A survey of graph layout problems","volume":"34","author":"D\u00edaz","year":"2002","journal-title":"ACM Comput. Surv."},{"key":"2023012507543721100_B16","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-642-00727-9_22","article-title":"Biclustering expression data based on expanding localized substructures","volume-title":"Proceedings of the 1st International Conference on Bioinformatics and Computing Biology","author":"Erten","year":"2009"},{"key":"2023012507543721100_B17","doi-asserted-by":"crossref","first-page":"4241","DOI":"10.1091\/mbc.11.12.4241","article-title":"Genomic expression programs in the response of yeast cells to environmental changes","volume":"11","author":"Gasch","year":"2000","journal-title":"Mol. Biol. Cell"},{"key":"2023012507543721100_B18","doi-asserted-by":"crossref","first-page":"12079","DOI":"10.1073\/pnas.210134797","article-title":"Coupled two-way clustering analysis of gene microarray data","volume":"97","author":"Getz","year":"2000","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012507543721100_B19","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1080\/01621459.1972.10481214","article-title":"Direct clustering of a data matrix","volume":"67","author":"Hartigan","year":"1972","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012507543721100_B20","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1101\/gr.205602","article-title":"Relating whole-genome expression data with protein-protein interactions","volume":"12","author":"Jansen","year":"2002","journal-title":"Genome Res."},{"key":"2023012507543721100_B21","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1101\/gr.648603","article-title":"Spectral biclustering of microarray data: coclustering genes and conditions","volume":"13","author":"Kluger","year":"2003","journal-title":"Genome Res."},{"key":"2023012507543721100_B22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S","article-title":"A survey of solved problems and applications on bandwidth, edge-sum, and profile of graphs","volume":"31","author":"Lai","year":"1999","journal-title":"J. Graph Theory"},{"issue":"Suppl. 4","key":"2023012507543721100_B23","first-page":"S5","article-title":"Assessing reliability of protein-protein interactions by integrative analysis of data in model organisms","volume":"10","author":"Lin","year":"2009","journal-title":"BMC Bioinformatics"},{"issue":"Suppl. 4","key":"2023012507543721100_B24","doi-asserted-by":"crossref","first-page":"S9","DOI":"10.1186\/1471-2105-10-S4-S9","article-title":"Biclustering of microarray data with mospo based on crowding distance","volume":"10","author":"Liu","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012507543721100_B25","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1093\/bioinformatics\/btl560","article-title":"Computing the maximum similarity bi-clusters of gene expression data","volume":"23","author":"Liu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B26","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/TCBB.2004.2","article-title":"Biclustering algorithms for biological data analysis: A survey","volume":"1","author":"Madeira","year":"2004","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023012507543721100_B27","volume-title":"Leda: A Platform for Combinatorial and Geometric Computing.","author":"Mehlhorn","year":"1999"},{"key":"2023012507543721100_B28","first-page":"77","article-title":"Extracting conserved gene expression motifs from gene expression data","author":"Murali","year":"2003","journal-title":"Proceedings of the 8th Pacific Symposium on Biocomputing Lihue, Hawaii"},{"key":"2023012507543721100_B29","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1093\/bioinformatics\/btl060","article-title":"A systematic comparison and evaluation of biclustering methods for gene expression data","volume":"22","author":"Preli\u0107","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B30","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1214\/09-AOAS239","article-title":"Finding large average submatrices in high dimensional data","volume":"3","author":"Shabalin","year":"2009","journal-title":"Ann. Appl. Stat."},{"key":"2023012507543721100_B31","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1137\/S0097539797331671","article-title":"On bipartite drawings and the linear arrangement problem","volume":"30","author":"Shahrokhi","year":"2001","journal-title":"SIAM J. Comput."},{"key":"2023012507543721100_B32","doi-asserted-by":"crossref","first-page":"1787","DOI":"10.1093\/bioinformatics\/btg232","article-title":"Click and expander: a system for clustering and visualizing gene expression data","volume":"19","author":"Sharan","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B33","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.294849","article-title":"Genetic algorithms: a survey","volume":"27","author":"Srinivas","year":"1994","journal-title":"Computer"},{"key":"2023012507543721100_B34","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/945394.945402","article-title":"Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization","volume":"6","author":"Stallmann","year":"2001","journal-title":"J. Exp. Algorithmics"},{"key":"2023012507543721100_B35","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1186\/1471-2105-7-360","article-title":"A direct comparison of protein interaction confidence assignment schemes","volume":"7","author":"Suthram","year":"2006","journal-title":"BMC Bioinformatics"},{"issue":"Suppl. 1","key":"2023012507543721100_B36","doi-asserted-by":"crossref","first-page":"S136","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136","article-title":"Discovering statistically significant biclusters in gene expression data","volume":"18","author":"Tanay","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012507543721100_B37","first-page":"289","article-title":"Biclustering gene expression profiles by alternately sorting with weighted correlated coefficient","volume-title":"Machine Learning for Signal Processing, 2006. Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on","author":"Teng","year":"2006"},{"key":"2023012507543721100_B38","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein-protein interactions","volume":"417","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023012507543721100_B39","doi-asserted-by":"crossref","first-page":"R92","DOI":"10.1186\/gb-2004-5-11-r92","article-title":"Sparse graphical gaussian modeling of the isoprenoid gene network in arabidopsis thaliana","volume":"5","author":"Wille","year":"2004","journal-title":"Genome Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/20\/2594\/48852883\/bioinformatics_26_20_2594.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/20\/2594\/48852883\/bioinformatics_26_20_2594.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T07:55:18Z","timestamp":1674633318000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/20\/2594\/194083"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,23]]},"references-count":39,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2010,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq473","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,10,15]]},"published":{"date-parts":[[2010,8,23]]}}}