基于位图索引和B+树的BLAST改进算法

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (11): 118-120.

• 数据库、数据挖掘、机器学习 • 上一篇下一篇

基于位图索引和B+树的BLAST改进算法

黄志洪1，吕威2，黄俊1

1.中山大学数学与计算科学学院，广州 510275
2.北京师范大学珠海分校信息技术学院，广东珠海 519085

出版日期:2013-06-01 发布日期:2013-06-14

Improved BLAST algorithm based on bitmap indexes and B+ tree

HUANG Zhihong1, LV Wei2, HUANG Jun1

1.School of Mathematics & Computational Science, Sun Yat-sen University, Guangzhou 510275, China
2.School of Information Technology, Beijing Normal University Zhuhai Campus, Zhuhai, Guangdong 519085, China

Online:2013-06-01 Published:2013-06-14

摘要/Abstract

摘要： 针对BLAST算法在查找命中的过程中需要遍历数据库造成计算资源消耗的问题，提出了基于位图索引和B+树的数据存储方式以加快数据的检索。改进算法利用位图索引的原理建立数据库的单词-位向量表，并对这个表使用B+树再次进行索引，最终达到加快BLAST程序的运算速度。对于DNA序列这个方法能够使BLAST查找命中耗费的时间得到极大的减少。

关键词: 序列比对, BLAST算法, 位图索引, B+树

Abstract: It concentrates on the time consuming procedure that goes through the database in the first step of BLAST. In order to speed up the program, it introduces a new approach which using bit map index and B+ tree. The developed method builds up a word-bit_vector table according to the database, and reorganizes it with B+ tree. It proves theoretically that it decreases the word searching time of BLAST substantially.

Key words: sequence alignment, BLAST algorithm, bitmap index, B+ tree

黄志洪1，吕威2，黄俊1. 基于位图索引和B+树的BLAST改进算法[J]. 计算机工程与应用, 2013, 49(11): 118-120.

HUANG Zhihong1, LV Wei2, HUANG Jun1. Improved BLAST algorithm based on bitmap indexes and B+ tree[J]. Computer Engineering and Applications, 2013, 49(11): 118-120.

[1]	洪征，田益凡，张洪泽，吴礼发. 基于扩展前缀树的协议格式推断方法[J]. 计算机工程与应用, 2018, 54(12): 14-20.
[2]	刘应波1，3，王锋1，2，3，季凯帆2，邓辉2，戴伟1，2，3，梁波2. 基于压缩-字对齐位图的天文海量数据实时索引[J]. 计算机工程与应用, 2016, 52(1): 37-41.
[3]	张艳辉，王晓明. 一种改进的外包数据库查询验证技术[J]. 计算机工程与应用, 2012, 48(6): 73-76.
[4]	祁长红1，郁芸2，韩新焕2. Dijkstra算法在蛋白质序列比对中的研究[J]. 计算机工程与应用, 2012, 48(24): 122-126.
[5]	张宇，文中领，张延枫. 一种在存储子系统中实现依赖快照的技术[J]. 计算机工程与应用, 2011, 47(5): 53-56.
[6]	曾波，潘少彬，陆璐. 改进的LCS方法在测试脚本序列比对中的应用[J]. 计算机工程与应用, 2011, 47(35): 71-76.
[7]	文凤春¹，金人超²，肖枝洪¹. 训练隐马尔可夫模型的BW-GA方法[J]. 计算机工程与应用, 2010, 46(17): 236-238.
[8]	崔鑫,钟诚,陆向艳. 异构机群系统上双序列全局比对并行算法[J]. 计算机工程与应用, 2009, 45(8): 58-61.
[9]	宋孜攀,陆汝占. 机器可读词典中词汇属性信息的获取[J]. 计算机工程与应用, 2009, 45(5): 138-140.
[10]	李邵梅，郭云飞，卫红权. 基于分布特征统计的说话人识别[J]. 计算机工程与应用, 2009, 45(34): 118-120.
[11]	彭东海¹，骆嘉伟²，袁辉勇¹. 基于改进蚁群算法的多序列比对[J]. 计算机工程与应用, 2009, 45(33): 114-116.
[12]	骆嘉伟¹,陈斐¹,彭东海². 基于混合行为的蚁群双序列比对方法[J]. 计算机工程与应用, 2009, 45(11): 150-153.
[13]	吴德敏^1,2,陈俊³. 双序列比对的算法研究[J]. 计算机工程与应用, 2008, 44(36): 48-50.
[14]	杜娟,呼广跃. 数据压缩在序列比对中的应用[J]. 计算机工程与应用, 2008, 44(22): 241-243.
[15]	陈富强^1,2,奚建清¹. 用改进的游程编码方法压缩值索引[J]. 计算机工程与应用, 2008, 44(19): 140-141.

基于位图索引和B+树的BLAST改进算法

Improved BLAST algorithm based on bitmap indexes and B+ tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics