作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

一种基于哈夫曼判定的蛋白质分类方法

何红洲1,周明天2   

  1. (1. 绵阳师范学院数学与计算机科学学院,四川 绵阳 621000;2. 电子科技大学计算机科学与工程学院,成都 611731)
  • 收稿日期:2013-01-03 出版日期:2013-12-15 发布日期:2013-12-13
  • 作者简介:何红洲(1967-),男,副教授、博士研究生,主研方向:生物信息数据挖掘;周明天,教授、博士生导师
  • 基金资助:
    四川省教育厅自然科学研究基金资助项目(12ZB070)

A Classification Method of Protein Based on Huffman Decision

HE Hong-zhou 1, ZHOU Ming-tian 2   

  1. (1. College of Mathematics & Computer Science, Mianyang Normal University, Mianyang 621000, China; 2. School of Computer Science and Engineering, University of Electronic Science & Technology, Chengdu 611731, China)
  • Received:2013-01-03 Online:2013-12-15 Published:2013-12-13

摘要: 已有的仿射传播聚类算法不能很好地反映复杂蛋白质序列本身的聚类结构。为此,提出一种基于哈夫曼判定的蛋白质分类方法。在计算广义置换式匹配相似度的基础上,使用已有的自适应仿射传播算法聚类蛋白质序列。采用哈夫曼编码方法,通过限制平均码长使聚类结果能反映蛋白质序列家族的聚类结构。在蛋白质同源聚类数据库和蛋白质结构分类数据库的6个数据集上进行实验,结果表明,该方法与adAP、谱聚类、SMS和TribeMCL方法相比,不仅能获得更接近于数据集家族的聚类数目及更紧凑的聚类结构,而且F-measure指标平均估值分别高出19.67%、8.7%、9.5%和43.51%。

关键词: 聚类分析, 蛋白质序列, 广义置换式匹配相似度, 仿射传播聚类, 哈夫曼判定, F-measure指标

Abstract: Existed Affinity Propagation(AP) clustering algorithm can not reflect the clustering structure of the complex protein sequences, This paper proposes an adaptive AP classification method based on Generalized SMS and Huffman Decision(adAP/GSHD). Protein sequences are clustered via generalized Substitution Matching Similarity(gSMS) and existed adaptive affinity propagation(adAP) algorithm. It uses Huffman coding and confines the average code length of clustering results to embody the family clustering structure of protein sequences. By experiment of test adAP/GSHD and comparing its performance with other four classic clustering methods on six datasets of Clusters of Orthologous Groups(COG) of proteins database and Structural Classification of Proteins(SCOP) database, results demonstrate that this method not only can acquire number of clusters more approximately to the correct family number of clusters and more compact clustering structure for a given set of proteins, but also the average F-measure is 19.67%, 8.7%, 9.5% and 43.81% better than that of adAP, SMS, Spectral Clustering and TribeMCL respectively.

Key words: clustering analysis, protein sequence, generalized Substitution Matching Similarity(gSMS), Affinity Propagation(AP) clustering, Huffman decision, F-measure index

中图分类号: