基于Memetic优化的智能DNA序列数据压缩算法

doi:10.3969/j.issn.0372-2112.2013.03.016

电子学报

基于Memetic优化的智能DNA序列数据压缩算法

周家锐^1,2,3, 纪震^2,3, 朱泽轩^2,3, 陈思平^1,2,3

1. 浙江大学生物医学工程与仪器科学学院, 浙江杭州 310027;
2. 深圳大学计算机与软件学院, 广东深圳 518060;
3. 深圳市嵌入式系统设计重点实验室, 广东深圳 518060

收稿日期:2010-08-11 修回日期:2012-09-11 出版日期:2013-03-25
- 作者简介:
- 周家锐 男,1984年7月生于广东省韶关市,2010年获深圳大学模式识别与智能系统硕士学位,现为浙江大学生物医学工程与仪器科学学院博士研究生.主要研究方向包括计算智能、生物信息学等. E-mail:jrzhou@zju.edu.cn; 纪震 男,1973年8月生于江苏省溧阳市,1999年毕业于西安交通大学,博士学位,2004年晋升为教授,曾赴英国利物浦大学任访问学者.主要研究方向包括智能信号处理、嵌入式系统、生物医学工程. E-mail:jizhen@szu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61171125,No.60872125,No.61001185,No.61211130120); 霍英东高等院校青年教师基金基础性研究课题; 教育部重点研究项目; 广东省自然科学基金 (No.10151806001000002); 深圳市杰青项目

Intelligent DNA Sequence Data Compression Using Memetic Algorithm

ZHOU Jia-rui^1,2,3, JI Zhen^2,3, ZHU Ze-xuan^2,3, CHEN Si-ping^1,2,3

1. College of Biomedical Engineering and Instrument Science, Zhejiang University, Hangzhou, Zhejiang 310027, China;
2. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060, China;
3. Shenzhen Key Laboratory of Embedded System Design, Shenzhen, Guangdong 518060, China;

Received:2010-08-11 Revised:2012-09-11 Online:2013-03-25 Published:2013-03-25

摘要/Abstract

摘要： 提出近似重复矢量(Approximate Repeat Vector,ARV)模型用于DNA序列冗余片段的描述.通过将数据生物信息学特征引入压缩预处理,并使用ARV矢量构造编码码本,提出了非对称DNA序列压缩算法BioLZMA-2.算法引入基于粒子群优化的Memetic改进方法CLIPSO-MA用于压缩码本的智能优化设计,有效提升了编码性能.在标准测试序列上的实验结果表明,BioLZMA-2可获得比现有DNA序列数据压缩方法更高的压缩率.

关键词: DNA序列数据压缩, 生物信息学, 近似重复矢量, Memetic算法

Abstract: A data model namely the approximate repeat vector (ARV) is introduced to describe the similar fragments in DNA sequences.By employing bioinformatics features in data preprocessing,and using ARVs in compression codebook's construction,we propose an asymmetric DNA sequence compression algorithm of biological Lempel-Ziv-Markov chain algorithm 2(BioLZMA-2).The particle swarm optimization (PSO) based memetic algorithm improvement namely the comprehensive learning intelligent particle swarm optimization memetic algorithm (CLIPSO-MA) is employed in the compression codebook's design.Experimental results on benchmark sequences demonstrate better performance of BioLZMA-2 than the original DNA sequence compression algorithms.

Key words: DNA sequence data compression, bioinformatics, approximate repeat vector, memetic algorithm

中图分类号:

TP391

周家锐, 纪震, 朱泽轩, 陈思平. 基于Memetic优化的智能DNA序列数据压缩算法[J]. 电子学报, DOI: 10.3969/j.issn.0372-2112.2013.03.016.

ZHOU Jia-rui, JI Zhen, ZHU Ze-xuan, CHEN Si-ping. Intelligent DNA Sequence Data Compression Using Memetic Algorithm[J]. Acta Electronica Sinica, DOI: 10.3969/j.issn.0372-2112.2013.03.016.

参考文献

[1] Galperin M Y,Cochrane G R.Petabyte-scale innovations at the European nucleotide archive[J].Nucleic Acids Research,2009,37:D1-D4.
[2] Srinivasa K G,Jagadish M,et al.Efficient compression of non-repetitive DNA sequences using dynamic programming [A].Proceeding of International Conference on Advanced Computing and Communications [C].Mangalore:ADCOM,2006.569-574.
[3] Chen X,Kwong S,et al.A compression algorithm for DNA sequences and its applications in genome comparison [A].Proceeding of the 10th Workshop on Genome Informatics [C].Tokyo:GIW,1999.51-61.
[4] Matsumoto T,Sadakane K,et al.Biological sequence compression algorithms [A].Proceeding of Genome Informatics Workshop [C].Tokyo:CIW,2000.43-52.
[5] Chen X,Li M,et al.DNACompress:fast and effective DNA sequence compression[J].Bioinformatics,2002,18(12):1696-1698.
[6] Korodi G,Tabus I.An efficient normalized maximum likelihood algorithm for DNA sequence compression[J].ACM Transactions on Information Systems,2005,23(1):3-34.
[7] 林毅申,林丕源,等.基于字典的DNA序列压缩算法研究及应用[J].计算机应用研究,2007,24(6):265-267. Lin Y S,Lin P Y,et al.Research and mplementation of dictionary-based DNA compression algorithm[J].Application Research of Computers,2007,24(6):265-267.(in Chinese)
[8] 纪震,周家锐,等.基于生物信息学特征的DNA序列数据压缩算法[J].电子学报,2011,39(5):991-995. Ji Z,Zhou J R,et al.Bioinformatics features based DNA sequence data compression algorithm[J].Acta Electronica Sinica,2011,39(5):991-995.(in Chinese)
[9] 王玉,饶妮妮,等.基于小波变换技术预测DNA序列的编码区[J].电子学报,2007,35(1):141-144. Wang Y,Rao N N,et al.Predicting protein coding regions of DNA sequences based on wavelet translation technique[J].Acta Electronica Sinica,2007,35(1):141-144.(in Chinese)
[10] Nordin A,Yazid M,et al.A guided dynamic programming approach for searching a set of similar DNA sequences [A].Proceeding of International Conference on the Applications of Digital Information and Web Technologies [C].London:IEEE,2009.512-517.
[11] Liang J J,Qin A K.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation,2006,10(3):281-295.
[12] 周家锐,纪震,等.基于自适应智能单粒子优化算法的Gabor人脸识别方法 [A].全国模式识别学术会议 [C].重庆:CCPR,2010.1-5. Zhou J R,Ji Z,et al.Face recognition using Gabor wavelet and self-adaptive intelligent single particle optimizer.Proceeding of Chinese Conference on Pattern Recognition.Chongqing:CCPR,2010.1-5.(in Chinese)
[13] Wu S,Manber U.Fast text searching:allowing errors[J].Communications of the ACM,1992,35(10):83-91.
[14] Osborne M.Predicting DNA Sequences Using a Backoff Language Model [DB/OL].http://www.cogsci.ed.ac.uk/~osborne/dna-backoff.ps.gz,2009-05-15.
[15] Benson D A,Karsch-Mizrachi I,et al.GenBank[J].Nucleic Acids Research,2008,36:D25-D30.

基于Memetic优化的智能DNA序列数据压缩算法

Intelligent DNA Sequence Data Compression Using Memetic Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

[1]	李敏, 王晓桐, 罗慧敏, 孟祥茂, 王建新. 随机游走技术在网络生物学中的研究进展[J]. 电子学报, 2018, 46(8): 2035-2048.
[2]	莫宏伟, 徐立芳. 基于Memetic算法的电路演化设计研究[J]. 电子学报, 2013, 41(5): 1036-1040.
[3]	周家锐;;纪震;沈琳琳;朱泽轩;陈思平;. 基于Gabor小波与Memetic算法的人脸识别方法[J]. 电子学报, 2012, 40(4): 642-646.
[4]	邹权;李旭斌;林子雨;江弋;林琛. 下一代测序技术数据中的选择性剪切计算识别方法研究[J]. 电子学报, 2012, 40(2): 350-357.
[5]	纪震;周家锐;朱泽轩;Q H Wu. 基于生物信息学特征的DNA序列数据压缩算法[J]. 电子学报, 2011, 39(5): 991-995.
[6]	刘峤;王娟;陈伟;秦志光. 基于随机复杂度约束的高维特征自动选择算法[J]. 电子学报, 2011, 39(2): 370-374.
[7]	邹权;郭茂祖;王晓凯;张涛涛. 基于关键字树的DNA多序列星比对算法[J]. 电子学报, 2009, 37(8): 1746-1750.
[8]	刘立芳, 霍红卫, 王宝树. 生物序列模体的混合Gibbs抽样识别算法[J]. 电子学报, 2008, 36(4): 750-755.
[9]	卢欣华, 孙吉贵, . Analog-Cell:一种新的电子细胞图形模型[J]. 电子学报, 2007, 35(1): 49-53.
[10]	刘海涛, 洪炳熔, 朴松昊, 王雪梅. 不确定性环境下基于进化算法的强化学习[J]. 电子学报, 2006, 34(7): 1356-1360.
[11]	刘文斌, 朱翔鸥, 王向红, 陈丽春. DNA计算的研究进展[J]. 电子学报, 2006, 34(11): 2053-2057.
[12]	庄永龙, 马飞, 周敏, 沈岩, 李衍达. 基于多Agent的生物信息数据整合系统-BioAgent1[J]. 电子学报, 2005, 33(1): 78-82.
[13]	赵明生, 尚彤, 孙冬泳, 蒋景宏, 汤健, 吴佑寿. 电子细胞的研究现状与展望[J]. 电子学报, 2001, 29(S1): 1740-1743.