一种新的DNA模体发现聚类求精算法

doi:10.3969/j.issn.1001-2400.2014.06.016

J4 ›› 2014, Vol. 41 ›› Issue (6): 95-99.doi: 10.3969/j.issn.1001-2400.2014.06.016

一种新的DNA模体发现聚类求精算法

张懿璞

(西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2013-12-17 出版日期:2014-12-20 发布日期:2015-01-19
通讯作者: 张懿璞
作者简介:张懿璞(1985-)，男，西安电子科技大学博士研究生，E-mail：zephyr26026@gmail.com．
基金资助:
陕西省自然科学基金青年人才资助项目(2013JQ8037)；中央高校基本科研业务费专项资金资助项目(K5051303002)

Novel cluster refinement algorithm for DNA motif discovery

ZHANG Yipu

(School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2013-12-17 Online:2014-12-20 Published:2015-01-19
Contact: ZHANG Yipu

摘要/Abstract

摘要：

模体发现问题是分析基因转录调控关系的一个重要方面．提出了一种新的基于熵的聚类求精算法——ECRmotif，用于DNA序列中的模体发现问题．ECRmotif使用灵活的概率模型从背景序列中鉴别模体．它首先使用一个基于熵的聚类过程将数据集划分为若干子集，并对各候选子集压缩其实例的搜索空间，求精得到模体．通过模拟数据和真实数据的实验，表明ECRmotif算法可以有效地提高运行速度和效率，并准确地找出模体．

关键词: 模体发现, 聚类, 求精

Abstract:

The motif discovery problem is an important aspect of the analysis of gene transcriptional regulatory relationship. This paper describes a novel entropy-based cluster refinement algorithm (ECRmotif) for motif discovery in DNA sequences. ECRmotif employs a flexible probabilistic model to identify motif from the background sequences. It first utilizes an entropy-based cluster process to divide the dataset into several subsets, and then reduces the instances searching space for each candidate subset and refines the motif from the candidate subsets. Experiments by using both synthetic and real datasets demonstrate that our algorithm increases the running speed and efficiency and finds motif accurately.

Key words: motif discovery, cluster, refinement

张懿璞. 一种新的DNA模体发现聚类求精算法[J]. J4, 2014, 41(6): 95-99.

ZHANG Yipu. Novel cluster refinement algorithm for DNA motif discovery[J]. J4, 2014, 41(6): 95-99.

参考文献

［1］覃桂敏, 高琳, 呼加璐. 生物网络模体发现算法研究综述［J］. 电子学报, 2009, 37(10): 2258-2265.
Qin Guimin, Gao Lin, Hu Jialu. A Review on Algorithms for Network Motif Discovery in Biological Networks ［J］. Acta Electronica Sinica, 2009, 37(10): 2258-2265.
［2］ Zambelli F, Pesole G, Pavesi G. Motif Discovery and Transcription Factor Binding Sites Before and After the Next-generation Sequencing Era ［J］. Briefings in Bioinformatics, 2013, 14(2): 225-237.
［3］李婷婷, 蒋博, 汪小我, 等. 转录因子结合位点的计算分析方法［J］. 生物物理学报, 2008, 24(5): 334-347.
Li Tingting, Jang Bo, Wang Xiaowo, et al. Tutorial for Computational Analysis of Transcription Factor Binding Sites ［J］. Acta Biophysica Sinica, 2008, 24(5): 334-347.
［4］ Ghosh D, Qin Z S. Statistical Issues in the Analysis of ChIP-Seq and RNA-Seq Data ［J］. Genes, 2010, 1(2): 317-334.
［5］霍红卫, 郭丹丹, 于强, 等. (l, d)-模体识别问题的遗传优化算法［J］. 计算机学报, 2012, 35(7): 1429-1439.
Huo Hongwei, Guo Dandan, Yu Qiang, et al, Genetic Optimization for (l, d)-Motif Discovery ［J］. Chinese Journal of Computers, 2012, 35(7): 1429-1439.
［6］ Zhang Y, Huo H, Yu Q. A Heuristic Cluster-based EM Algorithm for the Planted (l, d) Problem ［J］. Journal of Bioinformatics and Computational Biology, 2013, 11(4): 1350009.
［7］ Hu J, Li B, Kihara D. Limitations and Ppotentials of Ccurrent Mmotif Ddiscovery Aalgorithms ［J］. Nucleic Acids Res, 2005, 33(15): 4899-4913.
［8］ Liu J S, Neuwald A F, Lawrence C E. Bayesian Models for Multiple Local Sequence Alignment and Gibbs Sampling Strategies ［J］. Journal of the American Statistical Association, 1995, 90(432): 1156-1170.
［9］ Liu X S, Brutlag D L, Liu J S. An Algorithm for Finding Protein-DNA Binding Sites with Applications to Chromatin-immunoprecipitation Microarray Experiments ［J］. Nature Biotechnology, 2002, 20(8): 835-839.
［10］ Pevzner P A, Sze S H. Combinatorial Approaches to Finding Subtle Signals in DNA Sequences ［C］//Proceedings of 8th International Conference on Intelligent Systems for Molecular Biology. San Diego: AAAI Press, 2000: 269-277.
［11］ Huang C W, Lee W S, Hsieh S Y. An Improved Heuristic Algorithm for Finding Motif Signals in DNA Sequences ［J］. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8(4): 959-975.

[1]	张春祥,周雪松,高雪瑶,刘欢. 融合k均值聚类与LSTM网络的半监督词义消歧[J]. 西安电子科技大学学报, 2021, 48(6): 161-171.
[2]	张佳琦,陶海红,张修社,韩春雷. 一种利用量测空间聚类的多帧检测前跟踪算法[J]. 西安电子科技大学学报, 2021, 48(5): 231-238.
[3]	王波,邓科. DB-SMOTE及多层堆叠用于心律失常识别[J]. 西安电子科技大学学报, 2021, 48(4): 136-143.
[4]	何云斌,冷欣,万静. 不平衡数据加权边界点集成欠采样方法[J]. 西安电子科技大学学报, 2021, 48(4): 176-183.
[5]	周建宇,位寅生,许荣庆. 一种改进模糊C均值聚类的电离层杂波分类方法[J]. 西安电子科技大学学报, 2021, 48(2): 35-41.
[6]	孙骞,张家瑞,高岭,王宇翔,杨建锋. 一种改进的边缘层节点健康态势预估方法[J]. 西安电子科技大学学报, 2020, 47(3): 32-39.
[7]	李钊,袁文浩,任崇广,黄程程,董霄霄. 跨层精度自动调节的k均值聚类近似计算方法[J]. 西安电子科技大学学报, 2020, 47(3): 50-57.
[8]	刘永利,郭呈怡,刘静,吴岩. 结合FCS的多视图模糊聚类算法[J]. 西安电子科技大学学报, 2019, 46(4): 99-106.
[9]	张书博,任淑霞,吴涛. 结合概率矩阵的改进谱聚类社区发现算法[J]. 西安电子科技大学学报, 2019, 46(3): 167-172.
[10]	刘景美,韩庆庆,沈志威,刘景伟. 采用k均值聚类的物理层密钥生成方案[J]. 西安电子科技大学学报, 2019, 46(1): 8-13.
[11]	赵彤,李先圣,张雷,丁恩杰,胡延军. 煤矿井下区间分段视距节点合作定位算法[J]. 西安电子科技大学学报, 2019, 46(1): 166-173.
[12]	刘道华, 胡秀云, 赵岩松, 崔玉爽. 一种动态分群带熵权的粒子群优化方法[J]. 西安电子科技大学学报, 2018, 45(6): 69-74.
[13]	杨利英;杨胜楠;袁细国;耿芳歌;张军英. 泛癌症DNA甲基化位点聚类分析[J]. 西安电子科技大学学报, 2018, 45(4): 23-28.
[14]	续拓;李洁;王颖. 叠加信息熵游走数据聚类算法[J]. 西安电子科技大学学报, 2018, 45(4): 75-79+154.
[15]	崔华;袁超;魏泽发;李盼侬;宋鑫鑫;纪宇;刘云飞. 利用FCM对静态图像进行交通状态识别[J]. 西安电子科技大学学报, 2017, 44(6): 79-84.

一种新的DNA模体发现聚类求精算法

Novel cluster refinement algorithm for DNA motif discovery

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0