Data Clustering Algorithm for DNA Microarray Based on Graph Theory

doi:10.3969/j.issn.1000-3428.2014.05.008

Computer Engineering

Previous Articles Next Articles

Data Clustering Algorithm for DNA Microarray Based on Graph Theory

SONG Jia ^1,2, XU Li ¹, SUN Hong ²

(1. Electrical Engineering College, Zhejiang University, Hangzhou 310027, China;2. Department of Electronic and Information Engineering, Suzhou Vocational University, Suzhou 215104, China)

Received:2013-04-22 Online:2014-05-15 Published:2014-05-14

基于图论的DNA微阵列数据聚类算法

宋佳^1,2，许力¹，孙洪²

(1. 浙江大学电气工程学院，杭州 310027；2. 苏州市职业大学电子信息工程系，江苏苏州 215104)

作者简介:宋佳(1980－)，女，讲师、博士研究生，主研方向：生物信息学，智能控制；许力，教授；孙洪，讲师、博士。
基金资助:
江苏省自然科学基金资助项目(BK2011319)；苏州市职业大学青年基金资助项目(SZDQ09L02)。

Abstract

Abstract: Clustering is an effective and practical method to mine the huge amount of DNA microarray data to gain important genetic and biological information. However, most traditional clustering algorithms can only provide a single clustering result, and are unable to identify distinct sets of genes with similar expression patterns. This paper presents an algorithm that can cluster DNA microarray data with a graph theory based algorithm. In particular, a DNA microarray dataset is represented by a graph whose edges are weighted, then an algorithm which can compute the minimum weighted and second minimum weighted graph cuts is applied to the graph respectively. Test results show that this approach can achieve improved clustering accuracy, compared with other clustering methods such as Fuzzy-Max, Fuzzy-Alpha, Fuzzy-Clust.

Key words: microarray, gene expression data, clustering analysis, graph cut, graph theory, minimum cut

摘要： 传统的聚类算法用于DNA微阵列数据分析时，多数只能生成一种聚类结果，无法识别出与多组不同基因表达模式相类似的基因。针对该问题，提出一种基于图论的聚类算法，采用一个有向无权图来描述需要分析的DNA微阵列数据，分别计算该图具有最小割权值和第二小割权值的图割。测试结果表明，该算法可以有效地探测聚类结果空间并输出一组可能性较高的聚类结果，与Fuzzy-Max、Fuzzy-Alpha、Fuzzy-Clust等聚类算法相比具有更高的准确性。

关键词: 微阵列, 基因表达数据, 聚类分析, 图割, 图论, 最小割

CLC Number:

TP309

SONG Jia, XU Li, SUN Hong. Data Clustering Algorithm for DNA Microarray Based on Graph Theory[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.05.008.

宋佳，许力，孙洪. 基于图论的DNA微阵列数据聚类算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.05.008.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2014.05.008

http://www.ecice06.com/EN/Y2014/V40/I5/36

References

参考文献 [1] 岳峰, 孙亮, 王宽全, 等. 基因表达数据的聚类分析研究进展[J]. 自动化学报, 2008, 34(2): 113-120. [2] Bertoni A, Valentini G. Randomized Embedding Cluster Ensembles for Gene Expression Data Analysis[C]//Proc. of IEEE International Conference on Science of Electronic, Technologies of Information and Telecommunications. Hammamet, Tunisia: IEEE Press, 2007: 246-252. [3] Avogadri R, Valenini G. Fuzzy Ensemble Clustering for DNA Microarray Data Analysis[C]//Proc. of the 4th International Conference on Bioinformatics and Biostatistics. Camogli, Italy: Springer, 2007: 537-543. [4] Avogadri R, Valentini G. Fuzzy Ensemble Clustering Based on Random Projections for DNA Microarray Data Analysis[J]. Artificial Intelligence in Medicine, 2009, 45(2): 173-183. [5] Avogadri R, Valentini G. Ensemble Clustering with a Fuzzy Approach[M]. [S. l.]: Springer, 2008. [6] Karypis G, Han E H, Kumar V. CHANELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. Computer, 1999, 32(8): 68-75. [7] Estivill C V, Lee I. AUTOCLUST: Automatic Clustering via Boundary Extraction for Mining Massive Point-data Sets[C]//Proc. of the 5th International Conference on Geocomputation. Greenwich, UK: [s. n.], 2000: 23-25. [8] Elghazel H, Yoshida T, Deslandres V, et al. A New Greedy Algorithm for Improving B-coloring Clustering[J]. Lecture Notes in Computer Science, 2007, 45(38): 228-239. [9] Li Yujian. A Clustering Algorithm Based on Maximal ?-distant Subtrees[J]. Pattern Recognition, 2007, 40(5): 1425-1431. [10] von Luxburg. A Tutorial on Spectral Clustering[J]. Statistics and Computing, 2007, 17(4): 395-416. [11] 郑加明, 陈昭炯. 带连通性约束的快速交互式Graph-Cut算法[J]. 计算机辅助设计与图形学学报, 2011, 23(3): 399-405. [12] Strandmark P, Kahl F. Parallel and Distributed Graph Cuts by Dual Decomposition[C]//Proc. of IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA: IEEE Press, 2010: 2085-2092. [13] Candemir S, Akgul Y S. Adaptive Regularization Parameter for Graph Cut Segmentation[C]//Proc. of International Conference on Image Analysis and Recognition. Povoa de Varzim, Portugal: Springer, 2010: 117-126. [14] James B O. A Faster Strongly Polynomial Time Algorithm for Submodular Function Minmization[J]. Mathematical Program- ming: Series A and B, 2009, 118(2): 237-251. [15] Hartuv E, Shamir R. A Clustering Algorithm Based on Graph Connectivity[J]. Information Processing Letters, 2000, 76(4): 175-181. 编辑任吉慧

Please choose a citation manager

Content to export

Data Clustering Algorithm for DNA Microarray Based on Graph Theory

基于图论的DNA微阵列数据聚类算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	DAI Haolei, HUANG Yonghui, ZHOU Guoxu. Clustering Analysis Based on Hyper-graph Regularized Non-Negative Tensor Train Decomposition [J]. Computer Engineering, 2023, 49(6): 81-89.
[2]	CHEN Luyao, LIU Qilong, XU Yunxia, CHEN Zhen. Image Clustering Algorithm Based on Hypergraph Regularized Nonnegative Tucker Decomposition [J]. Computer Engineering, 2022, 48(4): 197-205.
[3]	CAI Ruichu, HOU Yongjie, HAO Zhifeng. Cross-platform Gene Expression Data Classification Based on Hierarchical Rule Tree [J]. Computer Engineering, 2019, 45(7): 26-31.
[4]	LI Daoquan, ZHANG Yuxia, WEI Yanting. Energy Consumption Balanced Clustering Algorithm for Wireless Sensor Network Based on Clustering Analysis [J]. Computer Engineering, 2019, 45(10): 116-121.
[5]	SHENG Yibin,ZHANG Zhongzhi. Research on Pseudo-fractal Network Based on Weighted Scale-free [J]. Computer Engineering, 2019, 45(1): 303-307,314.
[6]	SHENG Yunxia,HUO Guanying,LIU Jing. Side-scan Sonar Image Segmentation Algorithm Based on Super-pixels Clustering [J]. Computer Engineering, 2018, 44(6): 219-225,232.
[7]	ZHU Jinshan,LIU Liangxu,ZHOU Chaolan,GUAN Bo. Public Bike Station Clustering Algorithm Based on SimRank [J]. Computer Engineering, 2018, 44(4): 12-16.
[8]	ZHANG Yaonan,ZHOU Sheng,NIU Lechuan,WANG Yuanyi. A Mesh Segmentation Method Based on Ant Colony Optimization [J]. Computer Engineering, 2018, 44(2): 277-281.
[9]	LI Qiang,WANG Mei,LIU Zhenghong. Tag Positioning Method Based on RFID Coverage and Scanning [J]. Computer Engineering, 2017, 43(3): 294-298.
[10]	FAN Zijing,LUO Ze,MA Yongzheng. A Spectral Clustering Algorithm Based on Fuzzy Kernel Clustering [J]. Computer Engineering, 2017, 43(11): 161-165,172.
[11]	DAI Qingyan,ZHU Zhongjie,DUAN Zhiyong,LI Weijie. Image Segmentation Based on Super-pixel and Improved Iterated Graph Cut Algorithm [J]. Computer Engineering, 2016, 42(7): 220-226.
[12]	ZHANG Zhe,SUN Lijun. Gene Feature Selection Algorithm Based on Discrete Particle Swarm Optimization and Neighborhood Reduction [J]. Computer Engineering, 2016, 42(3): 188-191,197.
[13]	YUAN Jian,WANG Tao. Detection Algorithm of Network Storage Covert Channel Based on Clustering Analysis [J]. Computer Engineering, 2015, 41(9): 168-173.
[14]	ZHENG Xuedong. Optimization of DNA Coding Based on Clustering Niche Genetic Algorithm [J]. Computer Engineering, 2015, 41(2): 135-140.
[15]	AI Lingmei,LI Ke,MA Miao. Application of fGn Model in Colon Cancer Gene Expression Dataset Denoising [J]. Computer Engineering, 2015, 41(11): 303-307.

模态框（Modal）标题

Please choose a citation manager

Content to export

Data Clustering Algorithm for DNA Microarray Based on Graph Theory

基于图论的DNA微阵列数据聚类算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments