基于优化k-mer频率的宏基因组聚类方法

doi:10.13229/j.cnki.jdxbgxb20170668

摘要/Abstract

摘要： k-mer频率是进行宏基因组分类时的一种重要的数字特征,然而该特征的维数随参数k的增加呈指数增长,利用该特征进行宏基因组分类易陷入“维数灾难”。为解决此问题,本文提出了一种基于优化k-mer频率的宏基因组DNA序列聚类方法。首先,提取DNA序列的k-mer频率特征;其次,使用非负矩阵分解算法对DNA序列的k-mer频率特征进行优化;最后,利用模糊C均值算法进行聚类。将本文方法在包含有不同物种个数的模拟宏基因组数据上运行的结果表明,其能有效地克服现有宏基因组数据分类方法计算量大的缺点,且分类性能优于同类算法。

关键词: 计算机应用, 模式识别与智能系统, k-mer, 非负矩阵分解, 模糊C均值, 宏基因组

Abstract: DNA sequence classification is a very important step in metagenomic study, and k-mer frequency is a commonly used feature for DNA sequence classification. The dimension of k-mer grows exponentially with k, easily leading to the “dimension disaster”. To solve this problem, this paper proposes a k-mer optimization based metagenomic DNA sequence classification method. First, the k-mer frequency is extracted for each DNA sequence. Second, the k-mer frequency is optimized based on Non-negative Matrix Factorization (NMF) algorithm. Finally, the fuzzy C-means clustering algorithm is used for DNA sequence clustering. Experimental results on metagenomic datasets containing different species show that the proposed method can effectively overcome the shortcoming of traditional classification method, and the classification performance is better than that of several similar algorithms.

Key words: computer application, pattern recognition and intelligent systems, k-mer, non-negative matrix factorization(NMF), fuzzy C-means method, metagenome

中图分类号:

TP391

刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.

LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.

参考文献

[1] Teeling H, Glöckner F O.Current opportunities and challenges in microbial metagenome analysis—a bioinformatic perspective[J]. Briefings in Bioinformatics, 2012, 13(6): 728-742.
[2] Burge C B, Karlin S.Finding the genes in genomic DNA[J]. Current Opinion in Structural Biology, 1998, 8(3): 346-354.
[3] Borodovskii M Y, Sprizhitskii Y A, Golovanov E I, et al.Statistical patterns in primary structures of functional regions in the E. coli genome. I. Oligonucleotide frequencies analysis[J]. Molecular Biology, 1986, 77(7): 3816-3820.
[4] Rosen G L, Reichenberger E R, Rosenfeld A M.NBC: the Naïve Bayes Classification tool webserver for taxonomic classification of metagenomic reads[J]. Bioinformatics, 2011, 27(1): 127-129.
[5] Gregor I, Dröge J, Schirmer M, et al.PhyloPythiaS+: a self-training method for the rapid reconstruction of low-ranking taxonomic bins from metagenomes[J]. Peer J, 2016, 4(10): e1603.
[6] Meinicke P, Aßhauer K P, Lingner T.Mixture models for analysis of the taxonomic composition of metagenomes[J]. Bioinformatics, 2011, 27(12): 1618-1624.
[7] 刘富,张潇,侯涛,等. 基于粗糙集的基因信号属性约简[J]. 吉林大学学报:工学版, 2015, 45(2): 624-629.
Liu Fu, Zhang Xiao, Hou Tao, et al.Attributes reduction of gene signal based on rough set[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2): 624-629.
[8] Koslicki D, Foucart S, Rosen G.Quikr: a method for rapid reconstruction of bacterial communities via compressive sensing[J]. Bioinformatics, 2013, 29(17): 2096-2102.
[9] Jiang X, Weitz J S, Dushoff J.A non-negative matrix factorization framework for identifying modular patterns in metagenomic profile data[J]. Journal of Mathematical Biology, 2012, 64(4): 697-711.
[10] Liang Z, Li Y, Zhao T.Projected gradient method for kernel discriminant nonnegative matrix factorization and the applications[J]. Signal Processing, 2010, 90(7): 2150-2163.
[11] Lin C J.On the convergence of multiplicative update algorithms for nonnegative matrix factorization[J]. IEEE Transactions on Neural Networks, 2014, 18(6): 1589-1596.
[12] 李华, 杨帆, 杨华民, 等. 条纹颜色分离与聚类[J]. 光学精密工程, 2016, 24(5): 1206-1214.
Li Hua, Yang Fan, Yang Hua-min, et al.Separating and clustering of structured light stripe colo[J]. Optics and Precision Engineering, 2016, 24(5): 1206-1214.
[13] 赵文昌, 李忠木. 融合改进人工蜂群和K均值聚类的图像分割[J]. 液晶与显示, 2017, 32(9): 726-735.
Zhao Wen-chang, Li Zhong-mu.Image segmentation algorithm based on improved artificial bee colony and K-mean clustering[J]. Chinese Journal of Liquid Crystal and Displays, 2017, 32(9): 726-735.
[14] 郭少军, 娄树理, 刘峰. 应用颜色聚类图像块的多舰船显著性检测[J]. 光学精密工程, 2016, 24(7): 1807-1817.
Guo Shao-jun, Lou Shu-li, Liu Feng.Multi-ship saliency detection via patch fusion by color clustering[J]. Optics and Precision Engineering, 2016, 24(7): 1807-1817.
[15] 王永,万潇逸,陶娅芝,等.基于K-medoids项目聚类的协同过滤推荐算法[J]. 重庆邮电大学学报:自然科学版,2017,29(4):521-526.
Wang Yong,Wan Xiao-yi,Tao Ya-zhi,et al.Collaborative filtering recommendation algorithm based on K-medoids item clustering[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2017,29(4):521-526.
[16] 杨玉梅. 基于信息熵改进的 K-means 动态聚类算法[J].重庆邮电大学学报:自然科学版,2016,28(2):254-259.
Yang Yu-mei.Improved K-means dynamic clustering algorithm based on information entropy[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2016,28(2):254-259.
[17] Leung H C, Yiu S M, Yang B, et al.A robust and accurate binning algorithm for metagenomic sequences with arbitrary species abundance ratio[J]. Bioinformatics, 2011, 27(11): 1489-1495.
[18] Alsop E B, Raymond J.Resolving prokaryotic taxonomy without rRNA: longer oligonucleotide word lengths improve genome and metagenome taxonomic classification[J]. Plos One, 2013, 8(7): e67337.
[19] 吴秋红, 吴谨, 朱磊, 等. 基于图论和FCM的图像分割算法[J]. 液晶与显示, 2016, 31(1): 112-116.
Wu Qiu-hong, Wu Jin, Zhu Lei, et al.Image segmentation algorithm based on graph theory and FCM[J]. Chinese Journal of Liquid Crystal and Displays, 2016, 31(1): 112-116.
[20] 王民, 张鑫, 贠卫国,等. 基于核模糊C-均值和EM混合聚类算法的遥感图像分割[J]. 液晶与显示, 2017, 32(12): 999-1005.
Wang Min, Zhang Xin, Yun Wei-guo, et al.Remote sensing image segmentation based on KFCM and EM hybrid clustering algorithm[J]. Chinese Journal of Liquid Crystal and Displays, 2017, 32(12): 999-1005.
[21] Liang J, Bai L, Dang C, et al.The K-means-type algorithms versus imbalanced data distributions[J]. IEEE Transactions on Fuzzy Systems, 2012, 20(4): 728-745.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[8]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[9]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[10]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[11]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[12]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[13]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[14]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
[15]	赵宏伟, 刘宇琦, 特日根, 陈长征, 臧雪柏. 基于有限序列的压缩新算法[J]. 吉林大学学报(工学版), 2018, 48(3): 882-886.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed