IMPROVEMENTS AND EXTENSIONS TO THE BLAST ALGORITHMS

BLAST家族的蛋白质和DNA数据库搜索程序构成了NCBI提供的关键服务之一。这些程序目前在NCBI服务器上运行约70，000次，在一个典型的工作日。这个项目代表了一个持续的努力，以改善和扩展这些程序的功能。今年的努力集中在IMPALA程序的开发上：PSI-BLAST使用位置特异性得分矩阵（PSSM）作为查询来搜索蛋白质序列数据库。所使用的PSSM通常是在运行中构建的，通过多次迭代的数据库搜索，以标准蛋白质序列开始。PSI-BLAST已被广泛用于注释从新的DNA序列推断的蛋白质，并生成代表大类蛋白质的PSSM集。这产生了对逆程序的需要，该逆程序将使用标准蛋白质序列作为查询来搜索PSI-BLAST生成的PSSM的数据库。新的IMPALA计划满足了这一需求。因为PSSM的数据库通常比标准蛋白质数据库小几个数量级，所以诸如IMPALA的程序可以在每个成对比较上比相应的BLAST程序运行得慢得多。因此，IMPALA实现了Smith-Waterman算法，适用于序列-PSSM比较。IMPALA的一个新特征是其对所产生的比对的统计显著性的评估。对于报告的每个比对，计算无空位比对的新的成对λ尺度参数[参见PNAS 87：2264-8]。该参数用于将PSSM重新缩放为具有在预先计算的间隙对准模拟中使用的相同λ的PSSM。这种方法导致在任何选择的统计显著性水平下的假阳性命中的数量大幅减少。它正在被添加到BLAST和PSI-BLAST程序中，并应提高这些程序的灵敏度。- 相似性检索，数据库检索，同源性，BLAST，PSI-BLAST，PHI-BLAST，IMPALA

The BLAST family of protein and DNA database search programs constitute one of the key services offered by the NCBI. These programs are currently run on NCBI servers about 70,000 times during a typical weekday. This project represents an ongoing effort to improve and extend the functionality of these programs. Efforts this year have focussed on the development of the IMPALA program:PSI-BLAST searches a database of protein sequences using a position-specific score matrix (PSSM) as query. The PSSMs used are generally constructed on the fly, through multiple iterations of database searching, initiated with a standard protein sequence. PSI-BLAST has been widely used to annotate proteins inferred from new DNA sequences, and to generate sets of PSSMs representing large classes of proteins. This has created the need for an inverse program, that will search a database of PSI-BLAST generated PSSMs using a standard protein sequence as query. The new IMPALA program answers this need. Because databases of PSSMs will typically be orders of magnitude smaller than standard protein databases, a program such as IMPALA can afford to run much more slowly on each pairwise comparison than the corresponding BLAST program. Accordingly, IMPALA implements the Smith-Waterman algorithm, adapted to sequence-PSSM comparison. One novel feature of IMPALA is its assessment of statistical significance of the alignments produced. For each alignment reported, a new pairwise lambda scale parameter[see PNAS 87:2264-8] is calculated for ungapped alignments. This parameter is used to rescale the PSSM to one with the same lambda used in precomputed gapped- alignment simulations. This approach leads to a substantial reduction in the number of false positive hits at any chosen level of statistical significance. It is in the process of being added to the BLAST and PSI- BLAST programs, and should improve those programs sensitivities. - similarity search, database search, homology, BLAST, PSI-BLAST, PHI- BLAST, IMPALA