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

National Library Of Medicine

Investigators

Linked publications & trials

Abstract

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.