基于MapReduce的基因数据密度层次聚类算法

doi:10.3969/j.issn.0253-2778.2014.07.001

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (7): 537-543.DOI: 10.3969/j.issn.0253-2778.2014.07.001

• 论著 • 下一篇

基于MapReduce的基因数据密度层次聚类算法

涂金金，杨明，郭丽娜

南京师范大学计算机科学与技术学院,江苏南京 210046

收稿日期:2014-03-21 修回日期:2014-06-15 接受日期:2014-06-15 出版日期:2023-05-11 发布日期:2014-06-15
通讯作者: 杨明
作者简介:涂金金，男，1988年生，硕士生. 研究方向：机器学习、模式识别. E-mail: tujinjin1988@sina.com
基金资助:
国家自然科学基金(61272222，61003116)，江苏省自然科学基金重点重大专项(BK2011005)，江苏省自然科学基金(BK2011782)，江苏省普通高校研究生科研创新计划项目(CXLX12_0415)资助.

A density-based hierarchical clustering algorithm of gene data based on MapReduce

TU Jinjin, YANG Ming, GUO Lina

School of Computer Science and Technology, Nanjing Normal University, Nanjing 210046, China

Received:2014-03-21 Revised:2014-06-15 Accepted:2014-06-15 Online:2023-05-11 Published:2014-06-15

摘要/Abstract

摘要： 随着生物信息技术的快速发展，基因表达数据的规模急剧增长，这给传统的基因表达数据聚类算法带来了严峻的挑战.基于密度的层次聚类(DHC)能够较好地解决基因表达数据嵌套类问题且鲁棒性较好，但处理海量数据的效率不高.为此，提出了基于MapReduce的密度层次聚类算法——DisDHC.该算法首先进行数据分割，在每个子集上利用DHC进行聚类获得稀疏化的数据；在此基础上再次进行DHC聚类；最终产生整体数据的密度中心点.在酵母数据集、酵母细胞周期数据集、人血清数据集上进行实验，结果表明，DisDHC算法在保持DHC聚类效果的同时，极大地缩短了聚类时间.

关键词: MapReduce, 密度层次聚类, 基因表达数据

Abstract: The amount of gene expression data scale is increasing sharply with the rapid development of bio-informatics technology, which poses a serious challenge for traditional clustering algorithms. Density-based hierarchical clustering (DHC) can solve the problem of the nested class of gene expression data and has good robustness, but for handling huge amounts of data. Therefore, a density-based hierarchical clustering algorithm on MapReduce(DisDHC) was proposed. It partitioned data sets into smaller blocks, clustered each block using DHC in parallel, gathered the result for re-clustering, and produced all density centers of each cluster. The experiments on GAL dataset, Cell cycle dataset, and Serum dataset show that DisDHC reduces clustering time and achieves high performance.

Key words: MapReduce, density-based hierarchical clustering, gene expression data

中图分类号:

TP31

涂金金，杨明，郭丽娜. 基于MapReduce的基因数据密度层次聚类算法[J]. 中国科学技术大学学报, 2014, 44(7): 537-543.

TU Jinjin, YANG Ming, GUO Lina. A density-based hierarchical clustering algorithm of gene data based on MapReduce[J]. Journal of University of Science and Technology of China, 2014, 44(7): 537-543.

参考文献

［1］ Gilbert D R, Schroeder M, van Helden J. Interactive visualization and exploration of relationships between biological objects［J］. Trends in Biotechnology, 2000, 18(12): 487-494.
［2］ Eisen M B, Brown P O. DNA arrays for analysis of gene expression［J］. Methods Enzymology, 1999, 303:179-205.
［3］ Jiang D X, Pei J, Zhang A D. DHC: A density-based hierarchical clustering method for time series gene expression data［C］ // Proceedings of the 3rd IEEE Symposium on Bioinformatics and Bioengineering. Washington, USA: IEEE Press, 2003: 393-400.
［4］ Jain A K, Murty M N, Flynn P J. Data clustering: A review［J］. ACM Computing Surveys, 1999, 31(3): 264-323.
［5］ Bach F R, Jordan M I. Learning spectral clustering［R］. Proceedings of Neural Information Processing Systems, No. UCB/CSD-03-1249, Berkeley, USA, 2003.
［6］ Frey B J, Dueck D. Clustering by passing messages between data points［J］. science, 2007, 315(5814): 972-976.
［7］ Ben-Dor A, Shamir R, Yakhini Z. Clustering gene expression patterns［J］. Journal of Computational Biology, 1999, 6(3-4): 281-297.
［8］ Tamayo P, Slonim D, Mesirov J, et al. Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation［J］. Proceedings of the National Academy of Sciences, 1999, 96(6): 2 907-2 912.
［9］ Zhao W Z, Ma H F, He Q. Parallel k-means clustering based on MapReduce［C］// Proceedings of the First International Conference on Cloud Computing. Beijing, China: Springer, 2009: 674-679.
［10］ Chen W Y, Song Y Q, Bai H J, et al. Parallel spectral clustering in distributed systems［J］. Pattern Analysis and Machine Intelligence, 2011, 33(3): 568-586.
［11］鲁伟明, 杜晨阳, 魏宝刚, 等. 基于 MapReduce 的分布式近邻传播聚类算法［J］. 计算机研究与发展, 2012, 49(8): 1 762-1 772.
［12］ Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters［J］. Communications of the ACM, 2008, 51(1): 107-113.
［13］刘鹏. 实战 Hadoop: 开启通向云计算的捷径［M］. 北京：电子工业出版社, 2011.
［14］ Schena M, Shalon D, Davis R W, et al. Quantitative monitoring of gene expression patterns with a complementary DNA microarray［J］. Science, 1995, 270(5235): 467-470.
［15］ Lockhart D J, Dong H, Byrne M C, et al. Expression monitoring by hybridization to high density oligonucleotide arrays［J］. Nature Biotechnology, 1996, 14(13): 1 675-1 680.
［16］ Jiang D X, Pei J, Zhang A D. Gpx: Interactive mining of gene expression data［C］// Proceedings of the 30th International Conference on Very Large Databases. Toronto, Canada: ACM Press, 2004: 1 249-1 252.
［17］ Bustin S A. Absolute quantification of mRNA using real-time reverse transcription polymerase chain reaction assays［J］. Journal of Molecular Endocrinology, 2000, 25(2): 169-193.
［18］ Cho R J, Campbell M J, Winzeler E A, et al. A genome-wide transcriptional analysis of the mitotic cell cycle［J］. Molecular Cell, 1998, 2(1): 65-73.
［19］ Yeung K Y, Haynor D R, Ruzzo W L. Validating clustering for gene expression data［J］. Bioinformatics, 2001, 17(4): 309-318.
［20］杨春梅. 基因表达数据聚类分析算法研究和应用［D］. 天津大学, 2006.

[1]	苏浩，刘其成，牟春晓. 基于MapReduce的商品评论热点发现算法研究[J]. 中国科学技术大学学报, 2019, 49(2): 112-118.
[2]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[3]	王进，王鸿，夏翠萍，欧阳卫华，陈乔松，邓欣. 基于Spark的组合分类器链多标签分类方法[J]. 中国科学技术大学学报, 2017, 47(4): 350-357.
[4]	陈远，汪璟玢. 分布式RDF关键词近似搜索方法[J]. 中国科学技术大学学报, 2017, 47(10): 823-836.
[5]	林子雨，李雨倩，李粲，赖永炫. PipelineJoin：一种新的基于MapReduce的多表连接算法[J]. 中国科学技术大学学报, 2015, 45(10): 836-845.

基于MapReduce的基因数据密度层次聚类算法

A density-based hierarchical clustering algorithm of gene data based on MapReduce

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价