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

doi:10.3969/j.issn.1001-2400.2014.06.016

Abstract

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

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

References

［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]	ZHANG Chunxiang,ZHOU Xuesong,GAO Xueyao,LIU Huan. Semi-supervised word sense disambiguation by combining k-means clustering and the LSTM network [J]. Journal of Xidian University, 2021, 48(6): 161-171.
[2]	LI Huadong,ZHANG Xueliang,WANG Xiaolei,LIU Hui,WANG Pengcheng,DU Junzhao. Multi-node cooperative game load balancing strategy in the Kubernetes cluster [J]. Journal of Xidian University, 2021, 48(6): 16-22.
[3]	ZHANG Jiaqi,TAO Haihong,ZHANG Xiushe,HAN Chunlei. A multi-frame track before detect algorithm utilizing measurement space clustering [J]. Journal of Xidian University, 2021, 48(5): 231-238.
[4]	HE Yunbin,LENG Xin,WAN Jing. Unbalanced data weighted boundary point integration undersampling method [J]. Journal of Xidian University, 2021, 48(4): 176-183.
[5]	ZHOU Jianyu,WEI Yinsheng,XU Rongqing. Improved ionospheric clutter classification method based on fuzzy C-means clustering [J]. Journal of Xidian University, 2021, 48(2): 35-41.
[6]	LI Jinze,WANG Zhonghao,LI Mengheng,QIN Tuanfa. Spectrum sharing management method for the small-area-blockchain based on district partition [J]. Journal of Xidian University, 2020, 47(6): 122-130.
[7]	LI Zhao,YUAN Wenhao,REN Chongguang,HUANG Chengcheng,DONG Xiaoxiao. Approximate computing method based on cross-layer dynamic precision scaling for the k-means [J]. Journal of Xidian University, 2020, 47(3): 50-57.
[8]	ZHEN Yan,ZHAO Hu. Resource scheduling strategy in hierarchical software defined wireless sensor networks [J]. Journal of Xidian University, 2019, 46(4): 87-98.
[9]	LIU Yongli,GUO Chengyi,LIU Jing,WU Yan. Multi-view fuzzy clustering algorithm using FCS [J]. Journal of Xidian University, 2019, 46(4): 99-106.
[10]	ZHANG Shubo,REN Shuxia,WU Tao. Improved spectral clustering community detection algorithm by combining the probability matrix [J]. Journal of Xidian University, 2019, 46(3): 167-172.
[11]	DUAN Zhao, LIU Kunlong. Dynamic program verification via a CPAChecker [J]. Journal of Xidian University, 2019, 46(1): 33-38.
[12]	LIU Jingmei,HAN Qingqing,SHEN Zhiwei,LIU Jingwei. Method for Secret key generation using k-means clustering [J]. Journal of Xidian University, 2019, 46(1): 8-13.
[13]	ZHAO Tong,LI Xiansheng,ZHANG Lei,DING Enjie,HU Yanjun. Algorithm for cooperational localization of the sectional interval and LOS node in a coal mine [J]. Journal of Xidian University, 2019, 46(1): 166-173.
[14]	LIU Daohua, HU Xiuyun, ZHAO Yansong, CUI Yushuang. Particle swarm optimization method based on dynamic sub-swarms with entropy weight [J]. Journal of Xidian University, 2018, 45(6): 69-74.
[15]	YANG Liying;YANG Shengnan;YUAN Xiguo;GENG Fangge;ZHANG Junying. Analyzing pan-cancer DNA methylation patterns via clustering [J]. Journal of Xidian University, 2018, 45(4): 23-28.

Novel cluster refinement algorithm for DNA motif discovery

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0