Algorithmic and complexity issues of three clustering methods in microarray data analysis
The complexity, approximation and algorithmic issues of several clustering problems are studied. These non-traditional clustering problems arise from recent studies in microarray data analysis. We prove the following results. (1) Two variants of the Order-Preserving Submatrix problem are NP-hard. There are polynomial-time algorithms for the Order-Preserving Submatrix problem when the condition or gene sets are fixed. (2) Three variants of the Smooth Clustering problem are NP-hard. The Smooth Subset problem is approximable with ratio 0.5, but it cannot be approximable with ratio 0.5 + delta for any delta > 0 unless NP = P. (3) The inferring plaid model problem is NP-hard.
microarray data analysis approximation order-preserving submatrix polynomial-time algorithm smooth clustering plaid model np-hardness