Files

article_extended.pdf
  • Open Access
  • Adobe PDF
  • 593.86 KB
Download

Details

Authors
Abstract
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 max-sum sub-matrix is a related but distinct problem for which one looks for a (non-necessarily contiguous) rectangular sub-matrix 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 (LNS). In this work, we exhibit some key properties of this NP-hard problem and define a bounding function such that larger problems can be solved in reasonable time. The use of these properties results in an improved CP-LNS implementation evaluated here. Two additional algorithms are also proposed in order to exploit the highlighted characteristics of the problem: a CP approach with a global constraint (CPGC) and a 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 CP-LNS 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Branders, V., Schaus, P., & Dupont, P. (2018). Combinatorial Optimization Algorithms to Mine a Sub-Matrix of Maximal Sum. In Annalisa Appice, Corrado Loglisci, Giuseppe Manco, Elio Masciari, Zbigniew W. Ras (ed.), New Frontiers in Mining Complex Patterns (6th International Workshop, NFMCP 2017, Held in Conjunction with ECML-PKDD 2017, Macedonia, Sept. 18-22, Revised Selected Papers, p. p. 65-79). Springer International Publishing. https://doi.org/10.1007/978-3-319-78680-3_5