Finding Longest Common Segments in Protein Structures in Nearly Linear Time
Finding Longest Common Segments in Protein Structures in Nearly Linear Time
复制标题
在近线性时间内找到蛋白质结构中最长的共同片段
DOI：
10.1007/978-3-642-31265-6_27
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Shuai Cheng Li
中科院分区：
文献类型：
--
作者：
Yen Kaow Ng;Hirotaka Ono;Ling Ge;Shuai Cheng Li
局部/全局比对 (Zemla, 2003) 或 LGA 是比较蛋白质结构的流行方法。 LGA 的两个组成部分之一要求我们计算两个蛋白质结构之间最长的公共连续片段。也就是说，给定两个结构A= (a1,…,an)和B= (b1,…,bn)，其中bk∈ ℝ3，我们要在所有满足相似性标准的f= (ai,…,aj)和g= (bi,…,bj)中找到最大长度的片段。我们考虑以下标准：（1）f 和 gi 之间的均方根偏差（RMSD）在给定的 t∈ ℝ 内； (2)f和g可以叠加使得对于每个k，i≤k≤j，||ak−bk|| ≤t 对于给定的 t∈ ℝ。当第一个要求适用时，我们给出一个时间复杂度为 $O(n\log n+n\mbox{\it \textbf{l}})$ 的算法，其中 $\mbox{\it \textbf{l}}$ 是满足标准的段的最大长度。我们展示了一个 FPTAS，对于任何 εε ℝ，它在 O(nlogn+n/ε) 时间内找到长度至少为 l，但 RMSD 高达 (1 +ε)t 的段。我们提出了一个FPTAS，对于任何给定的εε ℝ，找到可以叠加的最大长度的所有段fandg，使得对于每个k，i≤k≤j，||ak−bk|| ≤ (1 +ε)t，从而近似满足第二个要求。当 A 中的连续点间隔相同距离时（蛋白质结构就是这种情况），该算法的时间复杂度为 O(nlog2n/ε5)。
The Local/Global Alignment (Zemla, 2003), or LGA, is a popular method for the comparison of protein structures. One of the two components of LGA requires us to compute the longest common contiguous segments between two protein structures. That is, given two structuresA= (a1, …,an) andB= (b1, …,bn) whereak,bk∈ ℝ3, we are to find, among all the segmentsf= (ai,…,aj) andg= (bi,…,bj) that fulfill a certain criterion regarding their similarity, those of the maximum length. We consider the following criteria: (1) the root mean square deviation (RMSD) betweenfandgis to be within a givent∈ ℝ; (2)fandgcan be superposed such that for eachk,i≤k≤j, ||ak−bk|| ≤tfor a givent∈ ℝ. We give an algorithm of $O(n\log n+n\mbox{\it \textbf{l}})$ time complexity when the first requirement applies, where $\mbox{\it \textbf{l}}$ is the maximum length of the segments fulfilling the criterion. We show an FPTAS which, for anyε∈ ℝ, finds a segment of length at leastl, but of RMSD up to (1 +ε)t, inO(nlogn+n/ε) time. We propose an FPTAS which for any givenε∈ ℝ, finds all the segmentsfandgof the maximum length which can be superposed such that for eachk,i≤k≤j, ||ak−bk|| ≤ (1 +ε)t, thus fulfilling the second requirement approximately. The algorithm has a time complexity ofO(nlog2n/ε5) when consecutive points inAare separated by the same distance (which is the case with protein structures).