Improvements And Extensions To The Blast Algorithms

BLAST家族的蛋白质和DNA数据库搜索程序构成了NCBI提供的关键服务之一。这些程序目前在NCBI服务器上运行约70，000次，在一个典型的工作日。这个项目代表了一个持续的努力，以改善和扩展这些程序的功能。今年的努力集中在PSI-BLAST程序的改进上：PSI-BLAST使用位置特异性得分矩阵（PSSM）作为查询来搜索蛋白质序列的数据库。所使用的PSSM通常是在运行中构建的，通过多次迭代的数据库搜索，以标准蛋白质序列开始。PSI-BLAST已被广泛用于注释从新的DNA序列推断的蛋白质，并生成代表大类蛋白质的PSSM集。为了提高PSI-BLAST程序对远距离序列关系的敏感性，我们在前几年开发了一个系统来评估程序的性能。对于一组约100个查询序列，该小组的专家编制了酵母中相关蛋白质的详尽清单。然后可以通过任意数量的PSI-BLAST迭代将查询与全面的蛋白质序列数据库进行比较，并且将所得PSSM与完整的酵母序列进行比较。该程序生成按E值排序的酵母序列列表，从中绘制假阳性vrs图。可以获得真阳性。我们继续使用我们的评估系统来测试PSI-BLAST在检测远亲关系方面的潜在改进，并将PSI-BLAST与其他相关程序进行比较。今年我们采用了几种方法：1）我们测试了BLOSUM和OPTIMA评分系统的相对灵敏度，发现BLOSUM更上级; 2）我们调查了与BLAST算法的启发式性质相关的哪些参数对PSI-BLAST准确性影响最大，以及在调整这些参数时隐含的速度和灵敏度之间的权衡; 3）将PSI-BLAST与相关程序SAM进行了比较，发现PSI-BLAST在检测远亲关系方面更快、更准确：4）进一步研究了“基于窗口”的组成计算的效果，并确定研究这一程序需要更大的测试集; 5）我们开始实施一个“混合”的局部对齐评分系统，该系统应允许引入位置特定的差距成本。 在另一个方面，我们测试了在DNA和蛋白质背景下使用连续和非连续“命中”进行BLAST的相对灵敏度。非连续命中似乎对蛋白质BLAST搜索没有优势，但可以为DNA BLAST搜索提供实质性的改进。

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 improvement of the PSI-BLAST 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. In order to improve the sensitivity of the PSI-BLAST program to distant sequence relationships, we developed in previous years a system to evaluate the program's performance. For a set of about 100 query sequences, experts in the group compiled an exhaustive list of related proteins in yeast. The queries can then be compared to a comprehensive protein sequence databease through an arbitary number of PSI-BLAST iterations, and the resulting PSSM compared to the complete yeast sequence. This procedure generates a list of yeast sequences ordered by E-value, from which a plot of false positives vrs. true positives may be obtained. We continued to use our evaluation system to test potential improvements to PSI-BLAST in detecting distant relationships, and to compare PSI-BLAST to other related programs. Several avenues were pursued this year: 1) We tested the relative sensitivity of the BLOSUM and OPTIMA scoring systems, and found BLOSUM to be superior; 2) We investigated which parameters relating to the heuristic nature of the BLAST algorithm had the most bearing on PSI-BLAST accuracy, as well as the tradeoff between speed and sensitivity implicit in adjusting these parameters; 3) We compared PSI-BLAST to the related program SAM, and found PSI-BLAST to be both faster and much more accurate in detecting distant relationships; 4) We investigated further the effects of "window-based" composition calculations, and determined that a larger test set will be required to study this procedure; 5) We began implementation of a "hybrid" local alignment scoring system that should permit the introduction of position-specific gap costs. On a separate front, we tested the relative sensitivity of using contiguous and non-contiguous "hits" for BLAST in both the DNA and protein contexts. Non-contiguous hits appear to yield no advantage for protein BLAST searches, but may provide a substantial improvement for DNA BLAST searches.