Eﬃcient Substructure RMSD Query Algorithms*Tetsuo Shibuya
Human Genome Center, Institute of Medical Science,
University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, JAPANE-mail: tshibuya@hgc.jp
Keywords: algorithm, computational complexity,
protein 3-D structure comparison
Abstract
Protein structure analysis is a very important research topic in the molecular biology of the postgenomic era. The RMSD (root mean square deviation) is the most frequently used measure for comparing
two protein 3-D structures. In this paper, we deal with two fundamental problems related to the RMSD.
We ﬁrst deal with a problem called the ‘range RMSD query’ problem. Given an aligned pair of structures,the problem is to compute the RMSD between two aligned substructures of them without gaps. This
problem has many applications in protein structure analysis. We propose a linear-time preprocessing
algorithm that enables constant-time RMSD computation. Next, we consider a problem called the ‘substructure RMSD query’ problem, which is a generalization of the above range RMSD query problem. It
is a problem to compute the RMSD between any substructures of two unaligned structures without gaps.
Based on the algorithm for the range RMSD problem, we propose an O(nm) preprocessing algorithm
that enables constant-time RMSD computation, where n and m are the lengths of the given structures.
Moreover, we propose O(nm log r/r)-time and O(nm/r)-space preprocessing algorithm that enables O(r)query, where r is an arbitrary integer such that 1 ≤ r ≤ min(n, m). We also show that our strategy
also works for another measure called the URMSD (unit-vector root mean square deviation), which is avariant of the RMSD.

1Introduction

In the post-genomic molecular biology, analysis of protein 3-D structures becomes more and more important.
Recently, enormous amount of protein 3-D structures are solved and the number of them are still increasing,as seen in the PDB database [Berman et al. 2000]. As a result, faster algorithms to deal with such structuresare seriously needed. Two proteins are said to have similar functions if their 3-D structures are similar to eachother, and structure comparison is one of the keys to the protein function analysis. There are many structurecomparison algorithms for proteins [Eidhammer et al. 2000]. Many of these algorithms are dedicated to alignthe structures by inserting gaps so as to minimize some score, as in the cases of ordinary sequence alignment
algorithms. But the alignment is not the goal of the protein analysis. For example, we must search for
speciﬁc domains like conserved substructures or hinge-mediated domains from the aligned result.
The most famous similarity measure for protein structures is the RMSD (root mean square deviation) [Arun et al. 1987, Eggert et al. 1997, Kabsch 1976, Kabsch 1978, Schawrtz et al. 1987]. There
are several variations of the RMSD measure. The URMSD (unit-vector root mean square deviation) [Chew et al. 1999, Kedem et al. 1999] is an example. To analyze the aligned protein structures,
we often need to compute local RMSDs (or URMSDs) of aligned substructures. For example, in[Huang et al. 1993], they compute all the RMSDs between all the possible aligned substructures in the1

aligned pair of structures to ﬁnd hinge-mediated domains. Similar techniques are used also in many others [Nigham et al. 2007, Shibuya 2007]. Hence, we consider the following problem in this paper.
Problem 1 (Range RMSD Query Problem) Given a pair of aligned1 protein structures represented bylists of points: P = P[1..n] and Q = Q[1..n], the problem is to compute the RMSD between P[i..j] andQ[i..j] for a query pair of integers i and j (1 ≤ i < j ≤ n).
Without any preprocessing, we need O(k) time to compute it, where k = j − i (see section 2 for details). We
propose an algorithm that answers the above problem in constant time, with linear-time preprocessing. Notethat naive preprocessing algorithm would require O(n2 ) time or more, as there are O(n2 ) possible aligned
substructures. Moreover, we will show that the same strategy works for the URMSD.
We next consider the following problem, which is a generalization of the above range RMSD query
problem.
Problem 2 (Substructure RMSD Query Problem) Given two protein structures P = P[1..n] andQ = Q[1..m], the problem is to compute the RMSD (without considering gaps) between P[i..i + ℓ − 1]
and Q[j..j + ℓ − 1] for a query set of integers i, j and ℓ (1 ≤ i ≤ i + ℓ − 1 ≤ n, 1 ≤ j ≤ j + ℓ − 1 ≤ m).
By straightforwardly using our range RMSD query algorithm, we can solve this problem in constant time afterO(nm)-time preprocessing. Note that we would require O(nm min(n, m)) time or more for preprocessing if
we do it naively. For this problem, we also propose O(nm log r/r)-time and O(nm/r)-space preprocessing
algorithm that enables O(r) query, where r is an arbitrary integer such that 1 ≤ r ≤ min(n, m).
The substructure RMSD query problem is more general than the range RMSD query problem, and musthave many applications in protein structure analysis. This problem appears everywhere, e.g., as a subroutine
for alignment algorithms. Most protein alignment algorithms take very large time and is sometimes requires
more than O(nm) time. Thus we assume our algorithm can be very valuable for designing such alignment
algorithms.
The organization of this paper is as follows. In section 2, we present the deﬁnitions of the RMSD and the
URMSD. Then, we present an algorithm for the range RMSD query problem in section 3, and we present
algorithms for the substructure RMSD query problem in section 4. Finally in section 5, we conclude ourresults.

2

Preliminaries

2.1

RMSD: The Root Mean Square Deviation

A protein is a chain of amino acids. Each amino acid has one unique carbon atom named Cα , and thecoordinates of the Cα atom is often used as the representative position of the amino acid. The set of Cα
atom positions in a protein is called the backbone of the protein. The backbone structures are topologicallylinear, which can be represented by just a list of points in 3-D space, regardless of how complex the structures
are. In this paper, we deal with this coordinates list, as in the most structural research on proteins.
The similarity between two backbone structures is often measured by the RMSD (root mean squaredeviation) [Arun et al. 1987, Eggert et al. 1997, Kabsch 1976, Kabsch 1978, Schawrtz et al. 1987].2 Let thetwo sets of points (i.e., protein structures) to be compared be P = {⃗p1 , p⃗2 , . . . , p⃗n } and Q = {⃗q1 , ⃗q2 , . . . , ⃗qn },where p⃗i and ⃗qi are coordinates of the i-th Cα atoms of P and Q. We here consider p⃗i corresponds to ⃗qi for

1 We mean by ‘aligned’ that we do not consider gaps, i.e., P[i] corresponds to Q[i].
2 To do so, we need to know the correspondence between atoms of the two structures.

There are many cases that we know
it, such as the cases of structures formed by the same ﬂexible protein. If we do not know the correspondence, we must use
some structural alignment algorithms to ﬁnd the correspondence, and remove the atoms with no corresponding atoms. In thispaper, we do not deal with alignment algorithms.

2each i. Then the RMSD between P and Q is deﬁned as the minimum value of
v
u n
u1 X
dR,⃗v (P, Q) = t∥⃗
pi − (R · ⃗qi + ⃗v )∥2
n i=1

(1)

over all the possible rotation matrices R and translation vectors ⃗v , where ∥·∥ denotes the norm. Let R̂(P, Q)
and ⃗vˆ(P, Q) denote the R and ⃗v that minimize the value.
Let R · X denote the structure X rotated by the rotation matrix R. If the rotation matrix R is ﬁxed,dR,⃗v (P, Q) is known to be minimized when the centroid of R · Q is translated to the centroid of P by thetranslation vector ⃗v , regardless of what the rotation matrix R is. Thus, the following equation holds:n1X(⃗pi − R̂(P, Q) · ⃗qi ).
⃗vˆ(P, Q) =
n i=1

(2)

Hence, if both P and Q are translated so that their centroids are moved to the origin of the coordinates, theRMSD problem is reduced to a problem of ﬁnding R (i.e., R̂(P, Q)) that minimizes the following value:fR (P, Q) =nX∥⃗pi − R · ⃗qi ∥2 .

(3)

i=1

We can ﬁnd R̂(P, Q) in linear time by using thePnsingular value decomposition (SVD) [Arun et al. 1987,
Kabsch 1976, Kabsch 1978] as follows. Let H = i=1 p⃗i · ⃗qi t , where ⃗v t means the transpose of ⃗v . Clearly,
H can be computed in O(n) time. Then fR (P, Q) can be described asfR (P, Q) =n
X(⃗
pi t p⃗i + ⃗qi t ⃗qi ) − trace(R · H),

(4)

i=1

and trace(RH) is maximized when R = V U T , where U ΛV is the SVD of H and AT means the transposeof matrix A. Thus R̂(P, Q) can be obtained from H in constant time, as H is a 3 × 3 matrix and the SVD
can be computed in O(d3 ) time for a d × d matrix [Golub et al. 1996]. Note that there are rare degeneratecases where det(V U T ) = −1, which means that V U T is a reﬂection matrix. We ignore the degenerate casesin this paper. We can compute the RMSD value in linear time once we have obtained R̂(P, Q). In total, we
can compute the RMSD value in O(n) time.

2.2

URMSD: The Unit-Vector Root Mean Square Deviation

The URMSD (unit-vector root mean square deviation) [Chew et al. 1999, Kedem et al. 1999] is a variationof the RMSD. The RMSD is sometimes inﬂuenced badly by very distant pairs of points, and the URMSD
is designed to avoid such inﬂuence. Let p⃗′i = (⃗pi+1 − p⃗i )/∥⃗
pi+1 − p⃗i ∥ and ⃗qi′ = (⃗qi+1 − ⃗qi )/∥⃗qi+1 − ⃗qi ∥. Thenthe URMSD is the minimum value ofv
uu 1 n−1X′
dR (P, Q) = t∥⃗
p′ − R · ⃗qi′ ∥2(5)n − 1 i=1 iover possible rotation matrices R. Let Ř(P, Q) denote R that minimizes the value. The URMSD can also
be computed in the same way as the RMSD, which can be easily imagined from the fact that the equationof d′R (P, Q) resembles that of fR (P, Q) very much.
Pn−1
Let H ′ = i=1 p⃗′i · (⃗qi′ )t . Then d′R (P, Q) can be described as (fR′ (P, Q)/(n − 1))1/2 , where fR′ (P, Q) =Pn−1 ′ t ′pi p⃗i + ⃗qi′ t ⃗qi′ ) − trace(R · H ′ ). Thus, d′R (P, Q) is minimized when R = V ′ U ′T where U ′ ΛV ′ is thei=1 (⃗SVD of H ′ .3 It is obvious that we can compute the URMSD value from Ř(P, Q) in linear time. Hence thetotal computation time for the URMSD is also linear.
3 Like in the case of the RMSD computation, there are rare degenerate cases where V ′ U ′T becomes a reﬂection matrix, but
we do not deal with these cases in this paper.

3

3Preprocessing for the Range RMSD Query Problem

In this section, we show an algorithm for the range RMSD query problem introduced in section 1. Let
the two given aligned structures be P = {⃗p1 , p⃗2 , . . . , p⃗n } and Q = {⃗q1 , ⃗q2 , . . . , ⃗qn }. Let P[i..j] denote thesubstructure {⃗pi , p⃗i+1 , . . . p⃗j }, and Q[i..j] denote the substructure {⃗qi , ⃗qi+1 , . . . ⃗qj }, Then the range RMSD
query problem is a problem to compute the RMSD between P[i..j] and Q[i..j] for any i and j (i ≤ j),without considering gaps.
Pj
Let ⃗c(X) denote the centroid of structure X. Then, ⃗c(P[i, j]) = k=i p⃗k /(j − i + 1), and ⃗c(Q[i, j]) =Pjqk /(j − i + 1). Let p⃗¯k = p⃗k − ⃗c(P[i..j]), and ⃗q¯k = ⃗qk − ⃗c(Q[i..j]). Note that p⃗¯k is the coordinates
k=i ⃗of the atom p⃗k translated so that the centroid of P[i..j] is at the origin of the coordinates, and so is the⃗q¯k . According to the equations of fR (P, Q) in section 2.1, the RMSD between P[i..j] and Q[i..j] can bePjobtained in constant time if we are given the value g(i, j) =⃗¯k t p⃗¯k + ⃗q¯k t ⃗q¯k ) and the 3 × 3 matrix
k=i (pPj ¯ ¯ tH̄(i, j) = k=i p⃗k · ⃗qk .
Pj
Pj
Pj
Let ⃗hP (i, j) = k=i p⃗k , and h2P (i, j) = k=i p⃗k t p⃗k . Similarly, let ⃗hQ (i, j) = k=i ⃗qk , and h2Q (i, j) =PjPjqk t ⃗qk . Add to them, let G(i, j) = k=i p⃗k ⃗qk t . Note that ⃗hX (i, j) is a vector of length 3, h2X (i, j) is ak=i ⃗numerical value, and G(i, j) is a 3 × 3 matrix. Then, the following two equations hold:g(i, j) = h2P (i, j) + h2Q (i, j) −⃗hP (i, j)t⃗hP (i, j) ⃗hQ (i, j)t⃗hQ (i, j)
−
j−i+1
j−i+1

H̄(i, j) = G(i, j) −⃗hP (i, j)⃗hQ (i, j)t
j−i+1

(6)

(7)

These equations suggest that the RMSD value can be obtained in constant time if we are given ⃗hP (i, j),⃗hQ (i, j), h2 (i, j), h2 (i, j), and G(i, j). Note that similar techniques are used in [Shibuya 2006] for increPQ
mental RMSD computation.
⃗hX (i, j) can be computed in constant time, if we are given ⃗hX (1, k) for all k (1 ≤ k ≤ n), as ⃗hX (i, j) =⃗hX (1, j) − ⃗hX (1, i − 1) for either case of X = P or X = Q.4 It is obvious that ⃗hX (1, k) can be computed
for all k in linear time. h2X (i, j) can also be computed in constant time, if we are given h2X (1, k) for all k(1 ≤ k ≤ n), as h2X (i, j) = h2X (1, j) − h2X (1, i − 1). Here, it is also obvious that ⃗hX (1, k) can be computed for
all k in linear time. The same technique also works for G(i, j). G(i, j) can be computed in constant time, if
we are given G(1, k) for all k (1 ≤ k ≤ n), as G(i, j) = G(1, j) − G(1, i − 1). G(1, j) can also be computed
for all k in linear time.
Hence we can compute the RMSD between P[i..j] and Q[i..j] in constant time, if we are given ⃗hP (1, k),⃗hQ (1, k), h2 (1, k), h2 (1, k), and G(1, k) for all k (1 ≤ k ≤ n), all of which can be computed in linear timeP
Q
before the query. Note that the corresponding optimal rotation matrix and the translation vector can beobtained at the same time.
The same strategy also works for the URMSD. This case is much easier because we do not have to consider
the translation vector. According to the equation of fR′ (P, Q), we can compute the URMSD between
Pj−1 ′
Pj−1 ′ t ′P[i..j] and Q[i..j] in constant time, if we are given H ′ (i.j) =⃗k · (⃗qk′ )t andpk p⃗k + ⃗qk′ t ⃗qk′ ).
k=i p
k=i (⃗′′2′2
Furthermore, we can compute them if we are given H (1, k), h P (1, k) and h Q (1, k), letting h′2P (i, j) =Pj
Pj⃗′k t p⃗′k , and h′2Q (i, j) = k=i ⃗qk′ t ⃗qk′ . As p⃗′k and ⃗qk′ can be easily computed from p⃗k , p⃗k+1 , ⃗qk , and ⃗qk+1
k=i p
in constant time, we conclude that the URMSD can also be computed in constant time after linear-time
preprocessing.

4 To ease discussion, we let ⃗hX (i, j) = ⃗0 (zero vector) if i > j. Similarly, we let h2X (i, j) = 0 and G(i, j) = O (zero matrix) if
i > j.

4

4

Preprocessing for the Substructure RMSD Query Problem

In this section, we propose algorithms for the substructure RMSD query problem introduced in section 1.
Given two structures P = {⃗p1 , p⃗2 , . . . , p⃗n } and Q = {⃗q1 , ⃗q2 , . . . , ⃗qm },5 the range RMSD query problem is aproblem to compute the RMSD between P[i..i+ℓ−1] and Q[j..j+ℓ−1] for any i, j and ℓ (0 ≤ i ≤ i+ℓ−1 ≤ n,
0 ≤ j ≤ j + ℓ − 1 ≤ m). From now on, we let i ≤ j without loss of generality.6 Then, by preprocessing(as discussed in section 3) straightforwardly for all the range RMSD query problems between P[1..n′ ] andQ[k..k + n′ − 1] for all k (1 ≤ k ≤ m) where n′ = min(n, m − k + 1), we can solve the substructure RMSD
query problem in constant time. This straightforward preprocessing algorithm requires O(nm) time andspace in total. From now on, we discuss how to reduce the preprocessing time and space, permitting larger
query time, as the O(nm) time/space can sometimes be too large.
According to the discussion in section 3, we can compute the RMSD between P[i..i+ℓ−1] and Q[j..j+ℓ−1]
in constant time, if we are given the followings:⃗hP (i, i + ℓ − 1) =

i+ℓ−1
X

p⃗k

(8)

k=i

⃗hQ (j, j + ℓ − 1) =

j+ℓ−1
X

⃗qk

(9)

p⃗k t · p⃗k

(10)

k=i

h2P (i, i + ℓ − 1) =

i+ℓ−1
X
k=i

j+ℓ−1
X

⃗qk t · ⃗qk(11)p⃗i+k−1 · ⃗qj+k−1 t(12)h2Q (j, j + ℓ − 1) =k=j

E(i, j, ℓ) =

ℓ
X
k=1

Note that E(i, j, ℓ) is the G(i, i + ℓ − 1) for the range RMSD query problem between P[1..n′′ ] and Q[j − i +1..n′′ + j − i], where n′′ = min(n, m − j + i). As for ⃗hP (i, i + ℓ − 1), ⃗hQ (j, j + ℓ − 1), h2P (i, i + ℓ − 1) andh2Q (j, j + ℓ − 1), they can be computed in constant time after linear time preprocessing by the same technique
discussed in section 3, i.e., we need to compute ⃗hP (1, k), ⃗hQ (1, k), h2P (1, k) and h2Q (1, k) for all k before thequery. As for E(i, j, ℓ), if we compute E(1, j, ℓ) for all possible j and ℓ beforehand, we can compute it inconstant time, as E(i, j, ℓ) = E(1, j, ℓ) − E(1, i − 1, ℓ) if i > 1. This preprocessing requires O(nm) time andspace. But if we permit O(r) time (1 ≤ r ≤ min(n, m)) to compute the E(i, j, ℓ), we can reduce them toO(nm log r/r) time and O(nm/r) space as follows.
Let r be an integer such that 1 ≤ r ≤ min(n, m). To ease discussion, we consider that both n and m
are multiples of r. Then we can divide P into n/r substructures of length r. Let them be P1 , P2 , . . . , Pn/r .
Note that Pp = P[(r · (p − 1) + 1)..r · p]. Likewise, Q can be divided into m/r substructures of length r, and5 In this section, the length of Q can be diﬀerent from that of P.
6 In the case of i > j, we can do the same discussion by changing P and Q.

5

let them be Q1 , Q2 , . . . , Qm/r . For Pp , Qq , and k such that −r < k < r, consider the following value:7

r−k
X



Pp [s] · Qq [s + k]tEp,q (k) =







s=1
r
X

(k ≥ 0)(13)

Pp [s] · Qq [s + k]t(k < 0)s=1−k

For each pair of p and q, we can compute Ep,q (k) for all k in O(r log r) time, by the convolution techniquebased on the FFT (fast Fourier transform) (see [Cooley et al. 1965] for details). Thus we need O(nm log r/r)time to compute them for all the O(nm/r2 ) pairs of p and q. Next, we consider the following Fp,q (k) for all
the set of p, q and k (1 ≤ p ≤ n/r, 1 ≤ q ≤ m/r, p ≤ q, −r < k < r).
Fp,q (k) =pXEt,t−p+q (k)

(14)

t=1

Obviously, Fp,q (k) can be computed in O(nm/r) time for all the O(nm/r) sets of p, q and k, if we are given
all the Ep,q (k) values.
Recall that E(i, j, ℓ) = E(1, j, ℓ) − E(1, i − 1, ℓ) (i > 1). Thus, if we can compute E(1, j, ℓ) in O(r) time,
we can also compute E(i, j, ℓ) in O(r) time for any i, j and ℓ. Thus, hereinafter, we discuss how to computeE(1, j, ℓ) in O(r) time by using the Fp,q (k) values. Let a = ⌊ℓ/r⌋ and b = ⌈j/r⌉. To ease discussion, we let
Fp,q (k) = 0 if p = 0 or k ≥ r, and E(i, j, ℓ) = 0 if ℓ ≤ 0. Then, E(1, j, ℓ) can be described as follows:E(1, j, ℓ) =Fa,a+b−1 (j + r − b · r − 1)
+Fa,a+b (b · r − j + 1)
+E(a · r + 1, j + a · r, ℓ − a · r)

(15)

Notice that 0 ≤ ℓ − a · r < r, and E(a · r + 1, j + a · r, ℓ − a · r) can be computed in O(r) time. Thus, weconclude that E(1, j, ℓ) can be computed in O(r) time, after O(nm log r/r) time preprocessing time in total.
The space required for the preprocess is O(nm/r).
Consequently, we conclude that we can compute the RMSD in O(r) time after O(nm log r/r) time andO(nm/r) space preprocessing. It is trivial that the same techniques can be applied to the substructure
URMSD query problem, and it can also be computed in O(r) time after O(nm log r/r) time and O(nm/r)
space preprocessing.

5

Conclusions

In this paper, we dealt with two fundamental problems called the ‘range RMSD query problem’ and the‘substructure RMSD query problem’, both of which are very important for protein structure analysis. For therange RMSD query problem, we proposed a constant-time query algorithm after linear-time preprocessing.
Based on the algorithm, we showed that we can solve the substructure RMSD query problem in constanttime after O(nm) time preprocessing, where n and m are the lengths of the structures to be compared.
Moreover, for the latter problem, we also developed an O(r) query algorithm after O(nm log r/r) time and(nm/r) space preprocessing, where r is an arbitrary integer such that 1 ≤ r ≤ min(n, m).
Our algorithms can be used in various scenes in protein structure research. Actually, we have developed a hinge detection algorithm for ﬂexible protein 3-D structures based on our algorithm [Shibuya 2007].
Development of faster query algorithms, or more ﬂexible query algorithms remains as future work.

7P⃗r(p−1)+s . Similarly, Qq [s + k] is same as q⃗r(q−1)+s+k
p [s] is same as p

6

References[Arun et al. 1987] Arun, K. S., Huang, T. S., and Blostein, S. D. 1987. Least-squares ﬁtting of two 3-D pointsets. IEEE Trans Pattern Anal. Machine Intell., 9, 698-700,[Berman et al. 2000] Berman, H. M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T. N., Weissig, H.,
Shindyalov, I. N., and Bourne.P. E. 2000. The protein data bank. Nucl. Acids Res., 28, 235-242.
[Chew et al. 1999] Chew, L. P., Huttenlocher, D., Kedem K., and Kleinberg. J. 1999. Fast detection ofcommon geometric substructure in proteins. J. Comput. Biol., 6(3), 313-325.
[Cooley et al. 1965] Cooley, J. W., and Tukey, J. W. 1965. An algorithm for the machine calculation ofcomplex Fourier series, Math. Comput., 19, 297-301.
[Eggert et al. 1997] Eggert, D. W., Lorusso, A., and Fisher. R. B. 1997. Estimating 3-D rigid body transformations: a comparison of four major algorithms. Machine Vision and Applications, 9, 272-290.
[Eidhammer et al. 2000] Eidhammer, I., Jonassen, I., and Taylor. W. R. 2000. Structure Comparison and
Structure Patterns. J. Comput. Biol., 7(5), 685-716,[Golub et al. 1996] Golub, G. H., and Van Loan, C. F. 1996. Matrix Computation. 3rd eds., John Hopkins
University Press,[Huang et al. 1993] Huang, E. S., Rock, E. P., and Subbiah, S. 1993. Automatic and accurate method foranalysis of proteins that undergo hinge-mediated domain and loop movements, Curr. Biol, 3(11), 740748.
[Kabsch 1976] Kabsch, W. 1976. A solution for the best rotation to relate two sets of vectors. Acta Cryst.,
A32, 922-923.
[Kabsch 1978] Kabsch, W. 1978. A discussion of the solution for the best rotation to relate two sets ofvectors. 1978. Acta Cryst., A34, 827-828,[Kedem et al. 1999] Kedem, K., Chew, P., and Elber, R. 1999. Unit-vector RMS (URMS) as a tool to analyze
molecular dynamics trajectories. Proteins: Struct. Funct. Genet., 38, 1-12.
[Nigham et al. 2007] Nigham, A., and Hsu, D. 2007. Protein Conformational Flexibility Analysis with Noisy
Data, International Conference on Research in Computational Molecular Biology (RECOMB).
[Schawrtz et al. 1987] Schwartz, J. T., and Sharir, M. 1987. Identiﬁcation of partially obscured objects in
two and three dimensions by matching noisy characteristic curves. Intl. J. of Robotics Res., 6, 29-44.
[Shibuya 2006] Shibuya, T. 2006. Geometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures,
Combinatorial Pattern Matching 2006 (CPM 2006), LNCS 4009, 84-93,[Shibuya 2007] Shibuya, T. 2007. RMSDh: A New Measure for Comparing Flexible Protein Structures with
Hinges, submitted to J. Comput. Biol..

7