基于密度感知模式的生物序列分类算法

doi:10.11772/j.issn.1001-9081.2017071767

计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 427-432.DOI: 10.11772/j.issn.1001-9081.2017071767

基于密度感知模式的生物序列分类算法

胡耀炜¹, 段磊^1,2, 李岭³, 韩超¹

1. 四川大学计算机学院, 成都 610065;
2. 四川大学华西公共卫生学院, 成都 610041;
3. 四川大学生命科学学院, 成都 610041

收稿日期:2017-07-24 修回日期:2017-09-13 出版日期:2018-02-10 发布日期:2018-02-10
通讯作者: 段磊
作者简介:胡耀炜(1992-),男,河北邯郸人,硕士研究生,主要研究方向:数据挖掘;段磊(1981-),男,四川成都人,副教授,博士,CCF高级会员,主要研究方向:数据挖掘;李岭(1969-),男,四川成都人,教授,博士,主要研究方向:生物医学;韩超(1993-),男,甘肃庆阳人,硕士研究生,CCF会员,主要研究方向:数据挖掘、分布式计算。
基金资助:
国家自然科学基金资助项目（61572332，81473446）；中国博士后科学基金特别资助项目（2016T90850）；中央高校基本科研业务费资助项目（2016SCU04A22）。

Biological sequence classification algorithm based on density-aware patterns

HU Yaowei¹, DUAN Lei^1,2, LI Ling³, HAN Chao¹

1. College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China;
2. West China School of Public Health, Sichuan University, Chengdu Sichuan 610041, China;
3. College of Life Science, Sichuan University, Chengdu Sichuan 610041, China

Received:2017-07-24 Revised:2017-09-13 Online:2018-02-10 Published:2018-02-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572332, 81473446), the China Postdoctoral Science Foundation (2016T90850), the Fundamental Research Funds for the Central Universities (2016SCU04A22).

摘要/Abstract

摘要： 针对现有的基于模式的序列分类算法对于生物序列存在分类精度不理想、模型训练时间长的问题，提出密度感知模式，并设计了基于密度感知模式的生物序列分类算法——BSC。首先，在生物序列中挖掘具有"密度感知"的频繁序列模式；然后，对挖掘出的频繁序列模式进行筛选、排序制定成分类规则；最后，通过分类规则对没有分类的序列进行分类预测。在4组真实生物序列中进行实验，分析了BSC算法参数对结果的影响并提供了推荐参数设置；同时分类结果表明，相比其他四种基于模式的分类算法，BSC算法在实验数据集上的准确率至少提高了2.03个百分点。结果表明，BSC算法有较高的生物序列分类精度和执行效率。

关键词: 生物序列, 序列分类, 序列模式, 密度感知模式, 分类规则

Abstract: Concerning unsatisfactory classification accuracy and low efficiency of the existing pattern-based classification methods for model training, a concept of density-aware pattern and an algorithm for biological sequence classification based on density-aware patterns, namely BSC (Biological Sequence Classifier), were proposed. Firstly, frequent sequence patterns based on density-aware concept were mined. Then, the mined frequent sequence patterns were filtered and sorted for designing the classification rules. Finally, the sequences without classification were classified by classification rules. According to a number of experiments conducted on four real biological sequence datasets, the influence of BSC algorithm parameters on the results were analyzed and the recommended parameter settings were provided. Meanwhile, the experimental results showed that the accuracies of BSC algorithm were improved by at least 2.03 percentage points compared with other four pattern-based baseline algorithms. The results indicate that BSC algorithm has high biological sequence classification accuracy and execution efficiency.

Key words: biological sequence, sequence classification, sequential pattern, density-aware pattern, classification rule

中图分类号:

TP391.4

胡耀炜, 段磊, 李岭, 韩超. 基于密度感知模式的生物序列分类算法[J]. 计算机应用, 2018, 38(2): 427-432.

HU Yaowei, DUAN Lei, LI Ling, HAN Chao. Biological sequence classification algorithm based on density-aware patterns[J]. Journal of Computer Applications, 2018, 38(2): 427-432.

参考文献

[1] LI Y, LU Y, ZHANG F, et al. Protein classification using family profiles[C]//FSKD 2010:Proceeding of the 7th International Conference on Fuzzy Systems and Knowledge Discovery. New York:ACM, 2010:2212-2216.
[2] 杨旸.基于机器学习方法的生物序列分类研究[D].上海:上海交通大学,2009:1-2. (YANG Y. Research on biological sequence classification based on machine learning methods[D]. Shanghai:Shanghai Jiao Tong University, 2009:1-2.)
[3] LARRAÑAGA P, CALVO B, SANTANA R, et al. Machine learning in bioinformatics[J]. Briefings in Bioinformatics, 2006, 7(1):86-112.
[4] PEARSON W R, LIPMAN D J. Improved tools for biological sequence comparison[J]. Proceedings of the National Academy of Sciences of the United States of America, 1988, 85(8):2444-2448.
[5] ALTSCHUL S F, GISH W, MILLER W, et al. Basic local alignment search tool[J]. Journal of Molecular Biology, 1990, 215(3):403-410.
[6] DAO F-Y, YANG H, SU Z-D, et al. Recent advances in conotoxin classification by using machine learning methods[J]. Molecules, 2017, 22(7):1057.
[7] WEI L, XING P, SHI G, et al. Fast prediction of protein methylation sites using a sequence-based feature selection technique[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017, PP(99):1.
[8] LIU B, XU J, FAN S, et al. PseDNA-Pro:DNA-binding protein identification by combining Chou's PseAAC and physicochemical distance transformation[J]. Molecular Informatics, 2015, 34(1):8-17.
[9] 熊贇,陈越,朱扬勇.ProFaM:一个蛋白质序列家族挖掘算法[J].计算研究与发展,2007,44(7):1160-1168. (XIONG Y, CHEN Y, ZHU Y Y. ProFaM:an efficient algorithm for protein sequence family mining[J]. Journal of Computer Research and Development, 2007, 44(7):1160-1168.)
[10] ZHOU C, CULE B, GOETHALS B. Pattern based sequence classification[J]. IEEE Transactions on Knowledge and Data Engineer, 2016, 28(5):1285-1298.
[11] MULDER N J, KERSEY P, PRUESS M, et al. In silico characterization of proteins:UniProt, InterPro and Integr8[J]. Molecular Biotechnology, 2008, 38(2):165-177.
[12] ZHANG M, KAO B, CHEUNG D W, et al. Mining periodic:patterns with gap requirement from sequences[C]//SIGMOD'05:Proceeding of the 2005 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2005:623-633.
[13] WANG X, DUANG L, DDONG G, et al. Efficient mining of density-aware distinguishing sequential patterns with gap constraints[C]//DASFAA 2014:Proceeding of the 2014 International Conference on Database Systems for Advanced Applications, LNCS 8421. Cham:Springer, 2014:372-387.
[14] TSENG V S, LEE C-H. Effective temporal data classification by integrating sequential pattern mining and probabilistic induction[J]. Expert Systems with Applications, 2009, 36(5):9524-9532.
[15] LIU B, HSU W, MA Y. Integrating classification and association rule mining[C]//KDD'98:Proceeding of the 4th International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA:AAAI Press, 1998:80-86.
[16] LIN H, CHEN W. Prediction of thermophilic proteins using feature selection technique[J]. Journal of Microbiological Methods, 2010, 84(1):67-70.
[17] TANG H, ZOU P, ZHANG C M, et al. Identification of using feature selection technique[J]. Scientific Reports 6, 2016:30441.
[18] HALL M, FRANK E, HOLMES G, et al. The WEKA data mining software:an update[J]. ACM SIGKDD Explorations, 2009, 11(1):10-18.

基于密度感知模式的生物序列分类算法

Biological sequence classification algorithm based on density-aware patterns

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[2]	王淳颖, 张驯, 赵金雄, 袁晖, 李方军, 赵博, 朱小琴, 杨凡, 吕世超. 基于多源告警的攻击事件分析[J]. 计算机应用, 2020, 40(1): 123-128.
[3]	韩萌, 丁剑. 数据流频繁模式挖掘综述[J]. 计算机应用, 2019, 39(3): 719-727.
[4]	常炳国, 臧虹颖. 基于分段降维和路径修正DTW的时序特征分类器设计[J]. 计算机应用, 2018, 38(7): 1910-1915.
[5]	闫欣鸣, 孟凡荣, 闫秋艳. 基于趋势特征表示的shapelet分类方法[J]. 计算机应用, 2017, 37(8): 2343-2348.
[6]	孙其法, 闫秋艳, 闫欣鸣. 基于多样化top-k shapelets转换的时间序列分类方法[J]. 计算机应用, 2017, 37(2): 335-340.
[7]	公伟刘培玉贾娴. 基于改进PrefixSpan的序列模式挖掘算法[J]. 计算机应用, 2011, 31(09): 2405-2407.
[8]	刘栋宋国杰. 面向多维时间序列的过程决策树模型[J]. 计算机应用, 2011, 31(05): 1374-1377.
[9]	张洋陈未如陈姗姗. 并发序列模式挖掘方法研究[J]. 计算机应用, 2009, 29(11): 3096-3099.
[10]	李云徐涛田素方李拓. 带兴趣度的序列概念格模型及其构造[J]. 计算机应用, 2008, 28(3): 726-728.
[11]	常鹏陈;耿朱玉全. 一种分布式序列模式挖掘算法[J]. 计算机应用, 2008, 28(11): 2964-2966.
[12]	昝鑫郑庆华范宇倩韩九强. 攻击案例综合学习系统研究[J]. 计算机应用, 2007, 27(9): 2177-2179.
[13]	王燕李明 . 基于扩展概念格的分类规则获取算法[J]. 计算机应用, 2007, 27(10): 2376-2378.
[14]	江伟陈龙王国胤 . 用户行为异常检测在安全审计系统中的应用[J]. 计算机应用, 2006, 26(7): 1637-1639.
[15]	刘颖，林元烈，覃征. 含先验信息的学习机在生物序列分析中的应用[J]. 计算机应用, 2005, 25(09): 2169-2170.