基于块排序索引的生物序列局部比对查询技术.doc

《基于块排序索引的生物序列局部比对查询技术.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、-基于块排序索引的生物序列局部比对查询技术*BlockSortingIndex-basedTechniquesforLocalAlignmentSearchesonBiologicalSequences李永光王镝王国仁马宜菲(东北大学信息科学与工程学院计算机系统研究所110004)AbstractAcommonqueryagainstlargeproteinandgenesequencedatasetsistolocatetargetsthataresimilartoaninputquerysequen

2、ce.Thecurrentsetpopularsearchtools,suchasBLAST,employsheuristicstoimprovethespeedofsuchsearches.However,suchheuristicscansometimesmisstargets,whichinmanycasesisundesirable.ThealternativetoBLASTistouseanaccuratealgorithm,SuchasSmith-Waterman(S-W)algorithm

3、.However,theseaccuratealgorithmsarecomputationallyveryexpensive.Recently,anewtechnique,OASIS,hasbeenproposedtoimprovetheefficiencyandaccuracybyemployingdynamicalprogrammingduringtraversingsuffixtreeanditsspeediscomparabletoBLAST.Butitsmaindrawbackistoomu

4、chmemoryconsuming.Weproposeanefficientandaccuratealgorithmforlocallyaligninggenomesequences.Weconstructablocksortingindexstructureforthelargesequence.Theindexstructureislessthanthesuffixtreeindexandcanbefitforlargedatasize.Experimentalresultsshowthatoura

5、lgorithmhasbetterperformancethanOASIS.Keywordssequence;blocksortingindex;accuracy.--1.引言随着人类基因组计划的不断发展，在结构基因学和功能基因学的研究过程中，生物序列的相似性分析成为一种有效的手段[1]。通常情况下，两条DNA长序列，可能只在很小的区域内(密码区)存在关系；不同家族的蛋白质往往具有功能和结构上的相同的一些区域。因而，研究序列局部相似性比研究全序列相似性往往更有意义。序列局部比对是一种关于片段相似性的定性

6、描述[1]。通常的方法是通过动态规划[2]进行精确查找两个序列的最优局部比对，但因其代价太大，对超长生物序列直接应用这种技术是不可行的。为了提高查询速度，启发式算法当前被广泛应用，这些算法可以分为三类：基于哈希表的算法、基于频率空间过滤的算法、基于后缀树索引的算法。基于哈希表的典型算法有FASTA[5]和BLAST[6]。FASTA的核心思想是对数据库序列中的所有模式进行哈希索引。在查询时基于哈希索引可以快速检索出可能的匹配模式。然后根据这些模式的扩展得到更长的序列。BLAST算法是建立在严格的统计学的

7、基础之上，它主要用于发现具有较高的相似性的局部比对。在大多数情况下，根据局部比对参数会产生若干个HSP(High-scoreSequencePairs)。然后把所有匹配分值大于阈值的HSP作为结果。这种基于启发式算法的过滤原理尽管在一定程度上尽量减少丢失局部比对的结果，但精确率却不可能达到100%，一些符合条件的匹配序列可能不在查询结果中。MRS[4]是基于频率空间过滤的代表方法，它采用滑动窗口和小波变换技术，设计了一种高效的生物序列搜索方法。根据频率距离是编辑距离的上界的过滤原理，可以节省大约50%的

8、编辑距离计算。这种技术比较适合长的DNA序列，但不适合蛋白质序列的比对分析。另外一些方法是基于后缀树技术的,该类方法一般是通过对一条序列构建后缀树，然后利用后缀树快速查找到匹配的模式。对于后缀树中的某个分支，如果完全匹配的模式的个数超过给定阈值，那么就对该分支使用BLAST作进一步的查询。这类算法对阈值比较低的查询处理效率太低。OASIS[3]通过在遍历后缀树的同时运用动态规划算法，提供了一种精确的序列局部比对的搜索方法。其实验结果表明，它