Fast Hinge Detection Algorithms for Flexible Protein Structures
Fast Hinge Detection Algorithms for Flexible Protein Structures
复制标题
DOI：
10.1109/tcbb.2008.62
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
T. Shibuya
中科院分区：
文献类型：
--
作者：
T. Shibuya
构象变化的分析是理解蛋白质功能和相互作用的关键之一。为了进行分析，我们经常比较两种蛋白质结构，并考虑铰链区等柔性区域。均方根偏差（RMSD）是比较两种蛋白质结构最常用的方法，但它只适用于没有铰链区域的刚性结构。在本文中，我们提出了一种新的测量方法RMSD，称为考虑铰链（RMSDh）及其变体RMSDh(k)来比较两种具有铰链区域的柔性蛋白。我们还提出了一种新的高效的计算算法，可以同时检测铰链位置。RMSDh适用于在两个目标结构中每个都有一个小铰链区域的情况。计算RMSDh的新算法在线性时间内运行，这与计算RMSD的时间复杂度相同，并且比以往任何一种铰链检测算法都要快。RMSDh(k)设计用于比较具有多个铰链区域的结构。RMSDh(k)测度最多考虑k个小铰域，即除了最多k个铰域外，如果两个结构相似，则RMSDh(k)值应该很小。为了计算该值，我们提出了一种基于新的动态规划技术的O（kn2）时间和O(n)空间算法。在相同的计算时间和空间下，我们可以列举出预测的铰链位置。我们还针对实际的柔性蛋白质结构测试了我们的算法，并表明我们的算法可以正确地检测铰链位置。
Analysis of conformational changes is one of the keys to the understanding of protein functions and interactions. For the analysis, we often compare two protein structures, taking flexible regions like hinge regions into consideration. The Root Mean Square Deviation (RMSD) is the most popular measure for comparing two protein structures, but it is only for rigid structures without hinge regions. In this paper, we propose a new measure called RMSD considering hinges (RMSDh) and its variant RMSDh(k) for comparing two flexible proteins with hinge regions. We also propose novel efficient algorithms for computing them, which can detect the hinge positions at the same time. The RMSDh is suitable for cases where there is one small hinge region in each of the two target structures. The new algorithm for computing the RMSDh runs in linear time, which is the same as the time complexity for computing the RMSD and is faster than any of previous algorithms for hinge detection. The RMSDh(k) is designed for comparing structures with more than one hinge region. The RMSDh(k) measure considers at most k small hinge region, i.e., the RMSDh(k) value should be small if the two structures are similar except for at most k hinge regions. To compute the value, we propose an O(kn2)-time and O(n)-space algorithm based on a new dynamic programming technique. With the same computational time and space, we can enumerate the predicted hinge positions. We also test our algorithms against actual flexible protein structures, and show that the hinge positions can be correctly detected by our algorithms.