APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS

doi:10.1137/060664112

	APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS
	Wang, Lusheng 1; Lin, Yu 1,2; Liu, Xiaowen 1
	2008
发表期刊	SIAM JOURNAL ON COMPUTING
ISSN	0097-5397
卷号	38 期号:4 页码:1504-1518
摘要	One of the main goals in the analysis of microarray data is to identify groups of genes and groups of experimental conditions (including environments, individuals, and tissues) that exhibit similar expression patterns. This is the so-called biclustering problem. In this paper, we consider two variations of the biclustering problem: the consensus submatrix problem and the bottleneck submatrix problem. The input of the problems contains an m x n matrix A and integers l and k. The consensus submatrix problem is to find an l x k submatrix with l < m and k < n and a consensus vector such that the sum of distances between the rows in the submatrix and the consensus vector is minimized. The bottleneck submatrix problem is to find an l x k submatrix with l < m and k < n, an integer d and a center vector such that the distance between every row in the submatrix and the vector is at most d and d is minimized. We show that both problems are NP-hard and give randomized approximation algorithms for special cases of the two problems. Using standard techniques, we can derandomize the algorithms to get polynomial time approximation schemes for the two problems. To the best of our knowledge, this is the first time that approximation algorithms with guaranteed ratios are presented for microarray data analysis.
关键词	approximation algorithms computational biology microarray data analysis genes
DOI	10.1137/060664112
收录类别	SCI
语种	英语
资助项目	Research Grants Council of the Hong Kong Special Administrative Region, China[CityU 120905]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000261891600013
出版者	SIAM PUBLICATIONS
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11377
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wang, Lusheng
作者单位	1.City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Wang, Lusheng,Lin, Yu,Liu, Xiaowen. APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS[J]. SIAM JOURNAL ON COMPUTING,2008,38(4):1504-1518.
APA	Wang, Lusheng,Lin, Yu,&Liu, Xiaowen.(2008).APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS.SIAM JOURNAL ON COMPUTING,38(4),1504-1518.
MLA	Wang, Lusheng,et al."APPROXIMATION ALGORITHMS FOR BICLUSTERING PROBLEMS".SIAM JOURNAL ON COMPUTING 38.4(2008):1504-1518.