RIn-Close_CVC2: an even more efficient enumerative algorithm for biclustering of numerical datasets
Authors:
Preprint
Abstract
RIn-Close_CVC is an efficient (take polynomial time per bicluster), complete (find all maximal biclusters), correct (all biclusters attend the user-defined level of consistency) and non-redundant (all the obtained biclusters are maximal and the same bicluster is not enumerated more than once) enumerative algorithm for mining maximal biclusters with constant values on columns in numerical datasets. Despite RIn-Close_CVC has all these outstanding properties, it has a high computational cost in terms of memory usage because it must keep a symbol table in memory to prevent a maximal bicluster to be found more than once. In this paper, we propose a new version of RIn-Close_CVC, named RIn-Close_CVC2, that does not use a symbol table to prevent redundant biclusters, and keeps all these four properties. We also prove that these algorithms actually possess these properties. Experiments are carried out with synthetic and real-world datasets to compare RIn-Close_CVC and RIn-Close_CVC2 in terms of memory usage and runtime. The experimental results show that RIn-Close_CVC2 brings a large reduction in memory usage and, in average, significant runtime gain when compared to its predecessor.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Enumerating all maximal biclusters in numerical datasetsInformation Sciences, 2017
- The Genome-Wide Early Temporal Response of Saccharomyces cerevisiae to Oxidative Stress Induced by Cumene HydroperoxidePLOS ONE, 2013
- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time2010
- Disentangling information flow in the Ras-cAMP signaling networkGenome Research, 2006
- Logic of the Yeast Metabolic Cycle: Temporal Compartmentalization of Cellular ProcessesScience, 2005
- Biclustering algorithms for biological data analysis: a surveyIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- IRE1-Independent Gain Control of the Unfolded Protein ResponsePLOS Biology, 2004
- Mathematical aspects of concept analysisJournal of Mathematical Sciences, 1996