Global Alignment of Protein Sequences with Position-Specific Scoring Matrices.

NCBI目前使用本地比对工具“RPS-BLAST”来搜索CDD。局部比对工具本质上不适合CDD检索，因为完整结构域(根据定义)是进化中保守的单位。因此，检索应该将完整的结构域与蛋白质的子序列进行比较，这是“半全局”的比对。因此，我们开发了一种半全局比对算法和一种新的统计近似，它可以在查询的蛋白质序列中发现完整的蛋白质结构域，从而为了解新的蛋白质序列的功能提供线索。仿真结果表明，这种近似方法比HMMer和RPS-BLAST等工具中的p值近似方法要好得多，使GLOBAL成为蛋白质序列数据库中一种有前途的迭代搜索工具。谢尔盖·希特林博士将我们的方法作为一种动态编程算法在一个名为“global”的程序中实现。Kann博士分析了几种竞争方法的检索效率，其中包括HMMer，这是隐马尔可夫模型(HMM)的一种实现，并表明检索效率的顺序是：HMMer(全局模式)-与全局模式大致相同，全局-优于RPS-BLAST。Global实际上是一个退化的HMM。在保持HMM检索效率的同时，GLOBAL算法足够简单，可以通过BLAST等局部比对方法中使用的相同启发式算法来加速。因此，卡罗尔博士使用BLAST单词启发式加快了全球搜索速度，使其速度提高了约一个数量级，使其速度与其他领域检索工具相媲美。他已经将生成的代码合并到NCBI CoreTool中。

NCBI currently uses the local alignment tool "rps-BLAST" to search the CDD. Local alignment tools are inherently inappropriate for CDD retrieval, because complete domains (by definition) are the units conserved in evolution. Thus, retrieval should compare complete domains to protein subsequences, which is "semi-global" alignment. Accordingly, we developed a semi-global alignment algorithm and a novel statistical approximation that discovers whole protein domains within a query protein sequence, thereby giving clues as to the function of novel protein sequences. Simulations show that the approximation is much better than the p-value approximations in other tools like HMMer and rps-BLAST, making GLOBAL a promising candidate for an iterative search tool in protein sequence databases. Dr Sergey Sheetlin implemented our method as a dynamic-programming algorithm in a program called "GLOBAL". Dr Kann analyzed the retrieval efficacy of several competitive methods, including HMMer, an implementation of Hidden Markov models (HMMs), and shown that the retrieval efficacies are in the order: HMMer (in global mode) - about the same as GLOBAL, GLOBAL - better than rps-BLAST. GLOBAL is in fact a degenerate HMM. While retaining HMM retrieval efficacies, GLOBAL is simple enough to be accelerated by the same heuristics used in local alignment methods like BLAST. Accordingly, Dr. Carroll accelerated GLOBAL using the BLAST word-heuristic, speeding it by about an order of magnitude, making its speed competitive with other domain-retrieval tools. He has incorporated the resulting code in the NCBI CoreTools.