A Fixed Parameter Tractable Integer Program for Finding the Maximum Order Preserving Submatrix

Abstract : Order-preserving submatrices are an important tool for the analysis of gene expression data. As finding large order-preserving submatrices is a computationally hard problem, previous work has investigated both exact but exponential-time as well as polynomial-time but inexact algorithms for finding large order-preserving submatrices. In this paper, we propose a novel exact algorithm to find maximum order preserving submatrices which is fixed parameter tractable with respect to the number of columns of the provided gene expression data. In particular, our algorithm is based on solving a sequence of mixed integer linear programs and it exhibits better guarantees as well as better runtime performance as compared to the state-of-the-art exact algorithms. Our empirical study in benchmark datasets shows large improvement in terms of computational speed.
Type de document :
Communication dans un congrès
Proceedings of the IEEE International Conference of Data Mining, ICDM 2011, Dec 2011, Vancouver, Canada. 2011
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00641896
Contributeur : Gemma C Garriga <>
Soumis le : mardi 17 avril 2012 - 18:35:04
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 26 novembre 2012 - 14:50:50

Fichier

icdm-2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00641896, version 1

Collections

Citation

Jens Humrich, Thomas Gaertner, Gemma Garriga. A Fixed Parameter Tractable Integer Program for Finding the Maximum Order Preserving Submatrix. Proceedings of the IEEE International Conference of Data Mining, ICDM 2011, Dec 2011, Vancouver, Canada. 2011. 〈hal-00641896〉

Partager

Métriques

Consultations de la notice

418

Téléchargements de fichiers

326