文献类型：期刊文章

作　　者：李永光[1] 王镝[1] 王国仁[1] 马宜菲[1]

机构地区：[1]东北大学信息科学与工程学院计算机系统研究所,沈阳110004

出　　处：《计算机科学》

基　　金：教育部高等学校优秀青年教师学科研奖励计划基金资助项目;国家自然科学基金(60273079;60473074)资助

年　　份：2005

卷　　号：32

期　　号：12

起止页码：159-163

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSCD、CSCD2011_2012、IC、JST、RCCSE、UPD、ZGKJHX、核心刊

摘　　要：生物数据库中的查询是在生物序列数据集中查找与输入查询序列相似的目标,目前的一些流行工具如BLAST等,是利用启发式算法来提高查询的速度。然而,这些启发式算法无法找到所有的满足要求的结果,而一些精确算法,如动态规划算法,却需要非常高昂的代价。最近,一种新的技术,QASIS,提出了在后缀树的遍历中使用动态规划的精确查找算法,其性能与BLAST相当。但是它的主要缺点就是后缀树这种索引结构需要巨大的空间开销。本文采用基于无损压缩的块排序结构来索引超常的生物序列,减小索引的存储空间开销,有效地减少动态规划算法的计算代价。实验结果表明基于块排序索引的算法在性能方面优于OASIS算法。

关 键 词：生物序列 块排序索引  精确度  

分 类 号：TP311.13] TP311.12[计算机类]