Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/104657
Title: Algorithmic and complexity issues of three clustering methods in microarray data analysis
Authors: Tan, J.
Chua, K.S.
Zhang, L. 
Issue Date: 2005
Citation: Tan, J.,Chua, K.S.,Zhang, L. (2005). Algorithmic and complexity issues of three clustering methods in microarray data analysis. Lecture Notes in Computer Science 3595 : 74-83. ScholarBank@NUS Repository.
Abstract: 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 given. (2) The Smooth Subset problem cannot be approximable with ratio 0.5 + δ for any constant δ > 0 unless NP=P. (3) Inferring plaid model problem is NP-hard. © Springer-Verlag Berlin Heidelberg 2005.
Source Title: Lecture Notes in Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/104657
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

38
checked on Nov 9, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.