METHODS FOR COMPARISON OF PROTEIN THREE DIMENSIONAL STRUCTURE

我们已经开发了比较和对齐的算法

We have developed algorithms for comparison and alignment of protein three dimensional structures. VAST (vector alignment search tool) identifies substructure similarities by comparing the types, connectivity, and relative orientations of SSE's (secondary structure elements). Surprising similarities are identified objectively, by considering the number and scores of superimposable SSE-pairs in the best alignment, and the number of alternative alignments sampled. An optimal residue-by-residue alignments are also identified objectively, as that with the most surprising combination of superposition residual and number of aligned residues. Work this year has focused in three areas: 1) refinement of the rapid search heuristic, 2) refinement of the statistical significance calculation, and 3) calculation of a complete structural neighbor database for Entrez. VAST is an exhaustive search method in that it considers all possible SSE-pair alignments via a clique detection algorithm, and ranks them according to superposition score. We have found that sensitivity is improved to over 99.5% of BLAST similarities by two simple modifications, relaxation of the geometrical criteria defining edges in the clique graph, and prior parsing of 3D structure into compact domains. The significance test statistic for VAST is the product of the chance-occurrence likelihood of the best SSE alignment, and the number of possible alignments in a given domain-pair comparison. We have found that accuracy is improved by use of explicit convolution of the empirical score distribution for SSE pairs, up to substructure sizes found in practice, and by exact calculation of the number of alternative alignments, via a dynamic programming algorithm. The Entrez neighbor database contains results of an all-against-all comparison of the 10,000 domain structures in the current 3D database. We have found that VAST requires approximately .5 seconds per comparison, a value which makes this calculation possible for the first time. Maintenance of the complete structure neighbor database is also feasible, and we expect that this will be a useful resource for comparative analysis.