PROTEIN 3D STRUCTURE COMPARISON

我们开发了比较和对齐算法 蛋白质的三维结构。VAST（矢量 比对搜索工具）识别子结构相似性 通过比较类型、连通性和相对 SSE的方向（二级结构元素）。 令人惊讶的相似性是客观地确定的， 考虑到可重叠的数目和分数， 最佳比对中的SSE对，以及 抽样的备选路线。最佳 还确定了逐个残基的比对 客观地说，作为最令人惊讶的组合， 重叠残基和对齐残基的数量。 今年的工作重点有三个方面： 快速搜索启发式，2）细化 统计学显著性计算，以及3） 一个完整的结构化邻居数据库为dmz。VAST是 一种详尽的搜索方法，它考虑了所有 通过集团检测的可能SSE对比对 算法，并根据叠加得分进行排序。 我们已经发现，灵敏度提高到99.5%以上， BLAST相似性通过两个简单的修改，松弛 定义团中边的几何准则 图，并将3D结构预先解析为紧凑的 域. VAST的显著性检验统计量为 最佳SSE的机会-发生可能性的乘积 对齐，以及给定的对齐中可能的对齐数量 域对比较。我们发现，准确性 改进的显式卷积的经验 SSE对的分数分布，直到子结构大小 在实践中发现，并通过精确计算的数量 通过动态规划， 算法 Nodez邻居数据库包含结果 一个10,000个域名的所有对所有的比较， 在当前的3D数据库中。我们发现 VAST每次比较大约需要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.