Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (11): 118-120.

Previous Articles     Next Articles

Improved BLAST algorithm based on bitmap indexes and B+ tree

HUANG Zhihong1, LV Wei2, HUANG Jun1   

  1. 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

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

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

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

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

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

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