Improvements And Extensions To The Blast Algorithms

点击翻译按钮获取中文摘要

Work this year has focused on an analysis of the application of the minimum description length (MDL) principle to the specification of pseudocounts for use with PSI-BLAST. In brief, PSI-BLAST estimates the probabilities of amino acids occurring in an alignment position by combining observed amino acid counts with data-dependent pseudocounts. The number of pseudocounts has in the past been chosen empirically. We have used the MDL principle to derive from theory the number of pseudocounts that should be employed. The theory suggests that for a realistic number n of sequences in a multiple alignment, the number of pseudocounts should be practically independent of n. However, the theory also suggests that the number of pseudocounts should depend on the composition of alignment columns, with more highly constrained columns receiving fewer pseudocounts. This has the effect of increasing the "contrast" in scores between protein profile columns. We have implemented a new procedure for specifying pseudocounts, and found that it improves PSI-BLAST retrieval accuracy to a statistically significant extent. This new procedure is now used by default by PSI-BLAST, and a manuscript describing the work is in preparation.