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

Improved BLAST algorithm based on bitmap indexes and B+tree

作　　者：黄志洪[1] 吕威[2] 黄俊[1] 

机构地区：[1]中山大学数学与计算科学学院,广州510275 [2]北京师范大学珠海分校信息技术学院,广东珠海519085

出　　处：《计算机工程与应用》2013年第11期118-120,157,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11126039)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]