METHODS FOR COMPARISON OF PROTEIN THREE DIMENSIONAL STRUCTURE

我们已经开发了比较和比对的算法 蛋白质的三维结构。广域(向量 对齐搜索工具)确定子结构相似性 通过比较类型、连通性和相对 SSE(二级结构元素)的取向 令人惊讶的相似之处是客观地确定的，通过 考虑可重叠式的数量和分数 最佳对齐中的SSE对，以及 替代路线已采样。一个最优的 还识别了逐个残基的比对。 客观地说，因为这是最令人惊讶的组合 叠加残基和排列残基的数量。 今年的工作重点有三个方面：1)完善 快速搜索启发式，2)求精 统计显著性计算，以及3)计算 Entrez的完整结构邻居数据库。浩瀚的是 一种穷尽的搜索方法，因为它考虑了所有 通过集团检测可能的SSE对齐 算法，并根据叠加得分对它们进行排序。 我们发现，该方法的灵敏度提高到了99.5%以上。 通过两个简单的修改、松弛 定义集团中的边的几何标准 图形，以及将3D结构优先解析为紧凑结构 域名。VASS的显著性检验统计量是 最佳上证所的机会-发生可能性的乘积 路线，以及给定路线中可能的路线数 域对比较。我们发现精确度是 通过使用经验公式的显式卷积进行改进 上证所配对的分数分布，以至子结构大小 在实践中发现的，并通过精确的数字计算 可供选择的路线，通过动态规划 算法。Entrez邻居数据库包含结果 对10,000个域名进行全面比较 当前3D数据库中的结构。我们发现， Vavast每次比较大约需要0.5秒， 值，该值使第一个 时间到了。完整结构邻居的维护 数据库也是可行的，我们预计这将是 这是比较分析的有用资源。

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.