Improvements And Extensions To The Blast Algorithms

蛋白质和DNA数据库搜索程序的BLAST家族构成了NCBI提供的关键服务之一。在一个典型的工作日，这些程序目前在NCBI服务器上运行约7万次。该项目是为改进和扩展这些项目的功能而进行的持续努力。 今年的努力主要集中在使用成分调整的氨基酸替代矩阵和“Blastp”，这是一个将蛋白质查询与蛋白质数据库进行比较的程序。初步结果表明，这种分数矩阵主要用于长度相似(小于两个差异的因子)的序列的比较，以及通过相对熵测量的组成相对相似的序列的比较。在算法上，当使用的替换矩阵被修改时，我们需要重写用于产生缺口比对的启发式规则。这是因为用于成分调整的统计量的重新定标过程基本上从未产生更长的比对，而新的成分调整的矩阵经常产生扩展的比对。

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 primarily on the use of compositionally adjusted amino acid substitution matrices with "Blastp", the program for comparing protein queries to protein databases. Preliminary results indicate that such score matrices are useful primarily for the comparison of sequences with similar lengths (less than a factor of two difference), and for sequences whose compositions are relatively similar, as measured by relative entropy. Algorithmically, we have needed to rewrite the heuristic for producing gapped alignments when the substitution matrix used is modified. This is due to the fact that the rescaling procedure employed for compositionally adjusted statistics essentially never produced longer alignments, whereas the new compositionally adjusted matrices frequently yield extended alignments.