基于码书索引变换的高通量DNA序列数据压缩算法

doi:10.3969/j.issn.0372-2112.2015.05.026

电子学报 ›› 2015, Vol. 43 ›› Issue (5): 1007-1013.DOI: 10.3969/j.issn.0372-2112.2015.05.026

基于码书索引变换的高通量DNA序列数据压缩算法

谭丽, 孙季丰

华南理工大学电子与信息学院, 广东广州 510641

收稿日期:2014-01-07 修回日期:2014-04-17 出版日期:2015-05-25
- 作者简介:
- 谭丽女,1984年生于湖南常德.现为华南理工大学信息与通信工程专业博士研究生.研究方向为生物信息学,计算智能,图像与视频处理.E-mail:t.li07@mail.scut.edu.cn;孙季丰 男,1962年生于广东揭阳,现为华南理工大学电信学院教授,博士生导师.研究方向包括智能信号处理、图像与视频处理、自组织通信网等.
- 基金资助:
- 国家自然科学基金青年科学基金 (No.61202292); 广东省自然科学基金 (No.9151064101000037)

High-Throughput DNA Sequence Data Compression Method Based on Codebook Index Transformation

TAN Li, SUN Ji-feng

School of Electronic and Information Engineering, South China University of Technology, Guangzhou, Guangdong 510641, China

Received:2014-01-07 Revised:2014-04-17 Online:2015-05-25 Published:2015-05-25

摘要/Abstract

摘要：

提出一种高通量DNA序列数据的压缩算法.该算法先采用码书索引变换模型,将传统码书索引值的表示方法变换成由四个标准碱基字符替代的四进制数值方式,并采用一种界定替换串与非替换串的简明编码方法,接着通过信息熵的大小来决定是否进行块排序压缩变换(BWT),最后进行前移编码变换和Huffman熵编码.在多种测序数据集上的实验结果表明,CITD在大多数情况下可以获得比本文所对比的高通量DNA专用压缩方法更优的压缩性能.

关键词: 高通量DNA序列, 码书索引变换模型, 块排序压缩变换, 前移编码, 信息熵, 数据压缩算法

Abstract:

A novel high-throughput DNA sequence compression method based on codebook index transformation (CITD) is proposed.In CITD,we used the codebook index transformation (CIT) model,to substitute the traditional represatation of codebook indexes by the quaternary values which are expressed by the four standard base characters,and adopted a simple encoding method to distinguish the replaced and non-replaced substring,and subsequently determined whether need to use the Burrow Wheeler Transformation (BWT) according to the value of information entropy,finally used move to front (MTF) transformation and Huffman entropy coding to compress the data.Experimental results on several sequencing data sets demonstrate better performance of CITD than the high-throughput DNA sequence compression algorithms cited in this paper,in most cases.

Key words: high-throughput DNA sequence, codebook index transformation(CIT)model, burrow wheeler transfarmation(BWT), move to front(MTF), information entropy, data compression algorithm

中图分类号:

TP391

谭丽, 孙季丰. 基于码书索引变换的高通量DNA序列数据压缩算法[J]. 电子学报, 2015, 43(5): 1007-1013.

TAN Li, SUN Ji-feng. High-Throughput DNA Sequence Data Compression Method Based on Codebook Index Transformation[J]. Acta Electronica Sinica, 2015, 43(5): 1007-1013.

参考文献

[1] 朱泽轩,张永朋,等.高通量DNA测序数据压缩研究进展[J].深圳大学学报理工版,2013,30(4):409-415. Zhu Ze-xuan,Zhang Yong-peng,et al.Advance in the compression of high-throughput DNA sequencing data[J].Journal of Shenzhen University Science and Engineering,2013,30(4):409-415.(in Chinese)
[2] 纪震,周家锐,等.DNA序列数据压缩技术综述[J].电子学报,2010,38(5):1113-1121. Ji Zhen,Zhou Jia-rui,et al.Overview of DNA sequence data compression techniques[J].Acta Electronica Sinica,2010,38(5):1113-1121.(in Chinese)
[3] 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.
[4] Zhu Zexuan,Zhou Jiarui,et al.DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm[J].IEEE Transactions on Evolutionary Computation,2011,15(5):643-658.
[5] 周家锐,纪震,等.基于Memetic优化的智能DNA序列数据压缩算法[J].电子学报,2013,41(3):513-518. Zhou Jia-rui,Ji Zhen,et al.Intelligent DNA sequence data compression using memetic algorithm[J].Acta Electronica Sinica,2013,41(3):513-518.(in Chinese)
[6] Kuruppu S,Puglisi S J,et al.Optimized relative Lempel-Ziv compression of genomes[A].Proceeding of the 34th Australasian Computer Science Conference[C].Australia:ACSC,2011.91-98.
[7] Wang Congmao,Zhang Dabing.A novel compression tool for efficient storage of genome resequencing data[J].Nucleic Acids Research,2011,39(7):E45-U74.
[8] Jones D,Ruzzo W,et al.Compression of next-generation sequencing reads aided by highly efficient de novo assembly[J].Nucleic Acids Research,2012,40(22):E171.
[9] Kuruppu S,Beresford-Smith B,et al.Iterative dictionary construction for compression of large DNA data sets[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2012,9(1):137-149.
[10] Li Cong,Ji Zhenzhou,et al.Efficient parallel design for BWT-based DNA sequences data multicompression algorithm[A].Proceeding of International Conference on Automatic Control and Artificial Intelligence[C].Xiamen:ACAI,2012.967-970.
[11] Wikipedia.Move-to-front Transformation[DB/OL].http://en.wikipedia.org/wiki/Move-to-front-transform,2013-12-09.
[12] Wikipedia.FASTA[DB/OL].Http://blast.ncbi.nlm.nih.gov/blastcgihelp.shtml,2013-12-09.
[13] Shamir.Gil I.Universal lossless compression with unknown alphabets-the average case[J].IEEE Transactions on Information Theory,2006,52(11):4915-4944.
[14] Kuruppu S,Beresford-Smith B,et al.Iterative dictionary construction for compression of large DNA datasets:supplementary material[OL].http://www.computer.org/csdl/trans/tb/2012/01/ttb2012010137Abs.html,2013-12-09.
[15] 纪震,周家锐,等.基于生物信息学特征的DNA序列数据压缩算法[J].电子学报,2011,38(4):991-995. Ji Zhen,Zhou Jia-rui,et al.Bioinformatics features based DNA sequence data compression algorithm[J].Acta Electronica Sinica,2011,38(4):991-995.(in Chinese)

基于码书索引变换的高通量DNA序列数据压缩算法

High-Throughput DNA Sequence Data Compression Method Based on Codebook Index Transformation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张宏伟, 张小虎, 曹勇. 贝叶斯序贯重要性积分滤波器[J]. 电子学报, 2022, 50(4): 823-831.
[2]	陈孟元, 丁陵梅, 张玉坤. 基于改进关键帧选取策略的快速PL-SLAM算法[J]. 电子学报, 2022, 50(3): 608-618.
[3]	胡钢, 牛琼, 许丽鹏, 卢志宇, 过秀成. 基于网络超链接信息熵的节点重要性序结构演化建模分析[J]. 电子学报, 2022, 50(11): 2638-2644.
[4]	魏钰轩, 陈莹. 基于自适应层信息熵的卷积神经网络压缩[J]. 电子学报, 2022, 50(10): 2398-2408.
[5]	李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.
[6]	王树亮, 毕大平, 阮怀林, 杜明洋, 潘继飞. 基于信息熵准则的认知雷达机动目标跟踪算法[J]. 电子学报, 2019, 47(6): 1277-1284.
[7]	程玉胜, 赵大卫, 王一宾, 裴根生. 非平衡化标签补全核极限学习机多标签学习[J]. 电子学报, 2019, 47(3): 719-725.
[8]	吴宁博, 彭长根, 牟其林. 面向关联属性的差分隐私信息熵度量方法[J]. 电子学报, 2019, 47(11): 2337-2343.
[9]	邓大勇, 薛欢欢, 苗夺谦, 卢克文. 属性约简准则与约简信息损失的研究[J]. 电子学报, 2017, 45(2): 401-407.
[10]	李玉鑑, 张亚红. 三元变量间一维流形依赖关系的检测[J]. 电子学报, 2016, 44(3): 639-645.
[11]	孙雪, 李昆仑, 韩蕾, 白晓亮. 基于特征项分布的信息熵及特征动态加权概念漂移检测模型[J]. 电子学报, 2015, 43(7): 1356-1361.
[12]	唐振华, 梁祥严, 覃团发, 常侃. 分布式视频编码中基于多概率混合分布的相关噪声建模方法[J]. 电子学报, 2015, 43(2): 365-370.
[13]	吴成茂. 基于后验概率熵的正则化Otsu阈值法[J]. 电子学报, 2013, 41(12): 2474-2478.
[14]	张洁, 景晓军, 张博, 王栋. 基于细节点与方向场信息的指纹残缺区域重建算法[J]. 电子学报, 2012, 40(10): 2112-2116.
[15]	胡昌华;司小胜;周志杰;王鹏. 新的证据冲突衡量标准下的D-S改进算法[J]. 电子学报, 2009, 37(7): 1578-1583.