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. 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 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. Recently, Dr. Carroll has completed the first stage of development of an iterative protein search tool using semi-global alignment and has incorporated the resulting code in the NCBI CoreTools. The heuristic acceleration of the GLOBAL code speeds it by about an order of magnitude, making its speed competitive with other domain-retrieval tools.

Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
National Library of Medicine
Zip Code
Carroll, Hyrum D; Williams, Alex C; Davis, Anthony G et al. (2015) Improving Retrieval Efficacy of Homology Searches Using the False Discovery Rate. IEEE/ACM Trans Comput Biol Bioinform 12:531-7
Frith, Martin C; Park, Yonil; Sheetlin, Sergey L et al. (2008) The whole alignment and nothing but the alignment: the problem of spurious alignment flanks. Nucleic Acids Res 36:5863-71