Mining a SubMatrix of Maximal Sum
This topic contains 0 replies, has 1 voice, and was last updated by arXiv 1 year, 10 months ago.

Mining a SubMatrix of Maximal Sum
Biclustering techniques have been widely used to identify homogeneous subgroups within large data matrices, such as subsets of genes similarly expressed across subsets of patients. Mining a maxsum submatrix is a related but distinct problem for which one looks for a (nonnecessarily contiguous) rectangular submatrix with a maximal sum of its entries. Le Van et al. (Ranked Tiling, 2014) already illustrated its applicability to gene expression analysis and addressed it with a constraint programming (CP) approach combined with large neighborhood search (CPLNS). In this work, we exhibit some key properties of this NPhard problem and define a bounding function such that larger problems can be solved in reasonable time. Two different algorithms are proposed in order to exploit the highlighted characteristics of the problem: a CP approach with a global constraint (CPGC) and mixed integer linear programming (MILP). Practical experiments conducted both on synthetic and real gene expression data exhibit the characteristics of these approaches and their relative benefits over the original CPLNS method. Overall, the CPGC approach tends to be the fastest to produce a good solution. Yet, the MILP formulation is arguably the easiest to formulate and can also be competitive.
Mining a SubMatrix of Maximal Sum
by Vincent Branders, Pierre Schaus, Pierre Dupont
https://arxiv.org/pdf/1709.08461v1.pdf
You must be logged in to reply to this topic.