Linear-Time Protein 3-D Structure Searchingwith Insertions and Deletions
Tetsuo Shibuya1 , Jesper Jansson2, and Kunihiko Sadakane3
1

Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan
2
Ochanomizu University, 2-1-1 Ohtsuka, Bunkyo-ku, Tokyo 112-8610, Japan
3
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430,
Japan
tshibuya@hgc.jp, Jesper.Jansson@ocha.ac.jp, sada@nii.ac.jp

Abstract. It becomes more and more important to search for similar
structures from molecular 3-D structure databases in the structural biology of the post genomic era. Two molecules are said to be similar if the
RMSD (root mean square deviation) of the two molecules is less thanor equal to some given constant bound. In this paper, we consider an
important, fundamental problem of ﬁnding all the similar substructuresfrom 3-D structure databases of chain molecules (such as proteins), withconsideration of indels (i.e., insertions and deletions). The problem has
been believed to be very diﬃcult, but its computational diﬃculty has
not been well known. In this paper, we ﬁrst show that the same problem in arbitrary dimension is NP-hard. Moreover, we also propose a newalgorithm that dramatically improves the average-case time complexity
for the problem, in case the number of indels k is bounded by some constant. Our algorithm solves the above problem in average O(N ) time,
while the time complexity of the best known algorithm was O(N mk+1 ),for a query of size m and a database of size N .

1Introduction

Molecules with similar 3-D structures are said to have similar functions. It meansthat we can predict the molecular function by searching for molecules with similar structures in the databases. Thus, ﬁnding similar 3-D structures from 3-D
databases is very important [2,10,12,17]. Due to recent technological evolutionof molecular structure determination methods, more and more structures of biomolecules, especially proteins, are solved, as shown in the PDB (Protein Structure
Data Bank) database [3]. Moreover, a huge number of molecular structures are
predicted with various computational techniques recently. Hence, faster searching techniques against these molecular structure databases are seriously needed.
A protein is a chain of amino acids, and its structure is often represented
by a sequence of 3-D coordinates that represents the positions of amino acids.
Usually, the 3-D coordinates of the Cα atom in each amino acid is used as therepresentative position of that amino acid. Note that there are also other important chain molecules in living cells, such as DNAs, RNAs, and glycans. In this
S.L. Salzberg and T. Warnow (Eds.): WABI 2009, LNBI 5724, pp. 310–320, 2009.
c Springer-Verlag Berlin Heidelberg 2009Linear-Time Protein 3-D Structure Searching with Insertions and Deletions

311

paper, we consider a problem of searching for similar structures from a structure
database of chain molecules, which consists of sequences of 3-D coordinates that
represent molecular structures.
The RMSD (Root Mean Square Deviation) [1,9,14,15,17,20,21] is the mostwidely-used similarity measure between molecular structures, which is also usedin various other ﬁelds, such as robotics and computer vision. It determines geometric similarity between two same-length sequences of 3-D coordinates. It isdeﬁned as the square root of the minimum value of the average squared distance
between each pair of corresponding atoms, over all the possible rotations andtranslations. (See section 2.2 for more details.) The RMSD measure corresponds
to the Hamming distance in the textual pattern matching, from the viewpointthat it does not consider any indels (i.e., insertions and deletions) between them.
In the case of textual string comparison, especially comparison of two textual
strings of bio-molecules (such as proteins and DNA), we often prefer to use
the string alignment score that considers indels to compare two bio-sequences,rather than the Hamming distance. Likewise, it is also important to consider
indels when we compare two molecular 3-D structures. But it is much harderthan the textual string cases to compare two 3-D structures with considerationof indels, though an ordinary pair-wise alignment algorithm for textual strings
requires only quadratic time.
In this paper, we consider a problem of searching for substructures of databasestructures whose RMSDs to a given query is within some constant, permitting
indels. It is widely known that the contact map problem [13] is NP-hard and thestructure alignment problems are believed to be very diﬃcult. But the diﬃcultyof our problem is unknown, as our problem is diﬀerent from the contact map
problem. We show in this paper that our problem is also NP-hard if the dimension of the problem is arbitrary. But it does not mean that our problem is always
diﬃcult. If the number of indels is at most some constant, the problem can besolved in polynomial time, though the time complexity of known algorithms isstill very large. The best-known algorithm for the problem is a straight-forward
algorithm that requires O(N mk+1 ) time for a database of size N and a queryof size m, where k is the maximum number of indels. It is the worst-case timecomplexity, but the average-case time complexity of the algorithm is still all
the same O(N mk+1 ). We propose in this paper a much faster algorithm thatruns in average-case O(N ) time, assuming that the database structures can beconsidered as random walks. The model under this assumption is called the’random-walk model’ (It is also called the ‘freely-jointed chain model’ or justthe ‘ideal chain model’. See section 2.3 for more details.), and is very often usedin molecular physics [4,8,11,18]. It is also used in the analysis of algorithms forprotein structure comparison [22]. As demonstrated in [22], theoretical analyses
based on the random-walk model have high consistency with the actual experimental results on the PDB database.
The organization of this paper is as follows. Section 2 describes the notations
used in this paper and previous related work as preliminaries. Section 3 describes
the problem that we solve. Section 4 describes the NP-hardness of our problem.

312

T. Shibuya, J. Jansson, and K. Sadakane

Section 5 describes our new algorithm and the computational time analysis of
the algorithm. Section 6 concludes our results.

2

Preliminaries

2.1

Notations and Definitions

A chain molecule S whose i-th 3-D coordinates (vector) is si is noted as
S = (s1 , s2 , . . . , sn ). The length n of S is denoted by |S|. A structure S[i..j] =(si , si+1 , . . . , sj ) (1 ≤ i ≤ j ≤ n) is called a substructure of S. A structureS = (sa1 , sa2 , . . . , sa ) (1 ≤ a1 < a2 < . . . < a ≤ n) is called a subsequencestructure of S. S is also called a k-reduced subsequence structure of S, wherek = |S| − |S |. R · S denotes the structure S rotated by the rotation matrix
R, i.e., R · S = (Rs1 , Rs2 , . . . , Rsn ). |v| denotes the norm of the vector v. 0
denotes the zero vector. x denotes the expected value of x. P rob(X ) denotes
the probability of the event X .
2.2

RMSD: Root Mean Square Deviation

The RMSD (root mean square deviation) [1,9,14,15,20,21] is the most widelyused geometric similarity measure between two sequences of 3-D coordinates.
The RMSD between two 3-D coordinates sequences S(s1 , s2 , . . . , sn ) and T == n1(t1 , t2 , . . . , tn ) is deﬁned as the minimum value of n i=1 |si − (R · ti + v)|2
over all the possible rotation matrices R and translation vectors v. Let
RM SD(S, T) denote the minimum value. RM SD(S, T) can be computed in
O(n) time [1,9,14,15]. Note that the RMSD can be deﬁned in any other dimensions, by considering the above vectors and matrices are in any d-dimensions.
2.3

Random-Walk Model for Chain Molecules

The random-walk model (also called the freely-jointed chain model, or just theideal chain model), is a very widely used simple model for analyzing behaviorof chain molecules in molecular physics [4,8,11,18]. The model is also used foranalyzing the computational time complexities of algorithms for protein structures [22]. In the model, we assume that the chain molecules can be considered
as random walks. The model ignores many physical/chemical constraints, but it
is known to reﬂect the behavior of real molecules very well. In fact, experiments
in [22] showed high consistency between the experimental results obtained fromthe PDB database and the theoretical results deduced from the random-walkmodel. Consider a chain molecule S = (s0 , s2 , . . . , sn ) of length n + 1, in which
the distance between any two adjacent atoms is ﬁxed to some constant r.1 In the
random-walk model, a bond between two adjacent atoms, i.e., bi = si+1 − si , is1

In the case of proteins, the distance between two adjacent Cα atoms is ﬁxed to 3.8Å.
We can let r = 1 by considering the distance between two adjacent atoms as theunit of distance.

Linear-Time Protein 3-D Structure Searching with Insertions and Deletions

313

considered as a random vector that satisﬁes |bi | = r, and bi is considered to be
independent from any other bond bj (j = i).
2.4

Shibuya’s Lower Bound of the RMSD [22]Let
Ulef tdenote(u1 , u2 , . . . , u/2 )andUrightdenote(u/2+1 , u/2+2 , . . . , u2·/2 ) for a structure U = (u1 , u2 , . . . , u ). Let G(U)denote the centroid of the structure U, i.e., G(U) = 1 i=1 ui . Let F (U) denote|G(Ulef t ) − G(Uright )|/2, and let D(S, T) denote 2 · |Slef t |/|S| · |F (S) − F (T)|for two structures such that |S| = |T|. Shibuya proved in [22] that D(S, T) is always smaller than or equal to RM SD(S, T). In [22], he also proved the following
lemma:√
Lemma 1 (Shibuya [22]). The probability P rob(D(S, T) < c) is in O(c/ n),where n = |S| = |T|, under the assumption that either S or T follows therandom-walk model.

3

The k-Indel 3-D Substructure Search Problem

From now on, we deal with the following problem.
k-Indel 3-D Substructure Search Problem: We are given a text structure
P of size N and a query structure Q of size m (1 < m ≤ N ), both of which
are represented by 3-D coordinates sequences of the residues. We are also given
a constant positive real c and a small constant positive integer k (k  m).
The problem is to ﬁnd all the positions i (1 ≤ i ≤ N − m + k + 1) such that
the RMSD between some k  -reduced subsequence structure of Q and some k  reduced subsequence structure of P[i..i − k  + k  + m − 1] is at most c, for some
non-negative integers k  and k  (k  + k  ≤ k, k  − k  ≤ N − m − i + 1).
If there exists some triple set {i, k  , k  } that satisﬁes the above condition, we
say that Q matches with P[i..i − k  + k  + m − 1] with threshold c and (atmost) k  + k  indels. Usually, c is set to a constant proportional to the distance
between two adjacent residue coordinates in the molecular structures. In thecase of protein structures, c is often set to 1–2Å, while the distance between
two adjacent Cα atoms is 3.8Å. Usual structure databases may contain morethan 1 structures, but problems against the databases with multiple structures
can be reduced to the above single-text problem by just concatenating all thestructures into a single long text structure and ignoring matches that cross overthe boundaries of two concatenated structures.
The same problem without indels, i.e., the problem in case k = 0, is studied
very well. If we directly apply the Kabsch’s algorithm [14,15] introduced in section 2.2, the problem without indels can be solved in O(N m) time. For the problem, Schwartz and Sharir [20] proposed an algorithm based on the fast Fouriertransform technique that runs in O(N log m) time.2 Recently, Shibuya [22]2

The original algorithm runs in O(N log N ) time. See [22] for the technique to improveit into O(N log m).

314

T. Shibuya, J. Jansson, and K. Sadakane

proposed a breakthrough average-case (expected) linear-time algorithm, assuming that the text structures follow the random-walk model. He showed that hisalgorithm is much faster than other algorithms also in practice. Moreover heshowed that the experimental results on the whole PDB database agrees withthe theoretical analysis based on the random-walk model. But none of thesealgorithms considers any indels.
On the other hand, there have been almost no algorithmic study for casesk > 0, due to the diﬃculty of the problem, though the problem is very important.
The diﬃculty of the problem is not well known, though the problem is similar
to the famous contact map problem, which is known to be NP-hard [13]. In
section 4, we will show that the problem is NP-hard, in case the dimension of
the problem is arbitrary.
According to section 2.2, the RMSD between two structures of size m can becomputed in O(m) time. The possible number of subsequence structures to becompared in the k-indel 3-D substructure search problem is less than 2m+k Ck ·N ,which is in O(N mk ). Thus, our problem can be computed in O(N mk+1 ) time,either in the worst-case analysis or in the average-case analysis. As far as weknow, it is the best-known time complexity, and there have been known no algorithms other than the above straight-forward algorithm. But it also means thatthe problem can be computed in polynomial time, in case the number of indels
is bounded by some constant. In section 5, we will propose the ﬁrst algorithmwith better average-case time complexity, i.e., O(N ), for the above problem incase the number of the indels is at most some constant, which is a substantial
improvement for the problem. Note that the worst-case time complexity of ouralgorithm is still the same as the above straight-forward algorithm. Note alsothat our analysis of the average-case time complexity is based on the assumptionthat the text structure follows the random-walk model,3 like the analyses in [22].

4An NP-Hardness Result

Consider the following variant of the k-indel 3-D substructure search problem.
k-Indel Structure Comparison Problem: We are given two structures P
and Q, both of whose lengths are n. Find a k-reduced subsequence structureP of P and a k-reduced subsequence structure Q of Q, such that the RMSD
between P and Q is at most some given threshold c.
It is trivial that the k-indel structure comparison problem is in the class NP, as
the correctness of any instance can be checked in linear time. Moreover, it is also
trivial that the k-indel 3-D substructure search problem is at least as diﬃcult
as the k-indel comparison problem in 3-D, and the k-indel 3-D substructure
search problem is NP-hard if the k-indel structure comparison problem in 3D is NP-complete. The two problems can be extended to the problems in any
3

We give this random-walk assumption only on the database structures, and we giveno assumption on the query structures.

Linear-Time Protein 3-D Structure Searching with Insertions and Deletions

315

dimensional space. From now on, we show the k-indel structure comparison
problem in arbitrary dimension is NP-complete, by reduction from the following
k-cluster problem (or the densest k-subgraph problem), whose decision problem
is known to be NP-complete [6].
k-Cluster Problem (Densest k-Subgraph Problem): Given a graph G =(V, E), ﬁnd a size k subset of V such that the number of edges induced by thesubset is the largest.
Let V = {v1 , v2 , . . . , vn }. Consider an arbitrary subset V  = {vg1 , vg2 , . . . , vgk } of
V , where g1 < g2 < . . . < gk , and let x be the number of edges induced by V  .
There must exist a sequence of points P = (p1 , p2 , . . . , pn ) in n−1 dimensional
space, such that |pi − pj | = α if {vi , vj } ∈ E and |pi − pj | = β if {vi , vj } ∈/ E,
where α and β are any constants that satisfy 0 < α < β < 2α. Let Q be asequence of n zero vectors (0, . . . , 0) in the same n − 1 dimensional space. Let
PV  = (pg1 , pg2 , . . . , pgk ), and QV  be a sequence of k zero vectors (0, . . . , 0) in
the n − 1 dimensional space.
It is well known that the translation of the two structures in 3-D is optimized
when the centroids of the two structures are placed at the same position (e.g., at
the origin of the coordinates) [1,14], in computing the RMSD. It is also true inany dimensions d, which can be easily proved as follows. Consider two arbitraryd-dimensional structures S = (s1 , s2 , . . . , sn ) and T = (t1 , t2 , . . . , tn ), and an
arbitrary d-dimensional translation vector v. Then the following equation holds:
n
n
n
n

{ i=1 (si − ti )}2(si − ti ) 2 } + (si −ti )2 −. (1)(si −ti +v)2 = n{v+ i=1
n
n
i=1
i=1
n

(s −t )

Thus the translation is optimized when v = − i=1 n i i . It means that thetranslation is optimized when the two structures are moved so that the centroidsof the two structures are at the same position.
From now on, we consider computing the RMSD between PV  and QV  . It istrivial that the centroid of QV  is at the origin of the coordinates, and moreover
QV  does not change its shape by any rotation, as all the vectors in QV  arezero vectors. Hence, we do not have to consider the optimization of the rotation
for computing the RMSD between the two structures. Therfore we obtain thefollowing equation:kk
j=1 pgj 2) /k}1/2
RM SD(PV  , QV  ) = { (pgi −
k
i=1
={

k−1


k


(pgi − pgj )2 /k}1/2

i=1 j=i+1= {(α2 · x + β 2 · (k(k − 1)− x))/k}1/2
2(2)

It means that RM SD(PV  , QV  ) is smaller if x is larger, as 0 < α < β. Thus
we can obtain the answer of the decision problem of the k-cluster problem by316

T. Shibuya, J. Jansson, and K. Sadakane

solving the (n − k)-indel n − 1 dimensional structure comparison problem on
the two structures P and Q. Hence the k-indel structure comparison problem
in arbitrary dimensional space is NP-complete, and consequently we conclude
that the k-indel substructure search problem in arbitrary dimensional space is
NP-hard:
Theorem 1. The k-indel substructure search problem in arbitrary dimensional
space is NP-hard.

5

The New Linear Expected Time Algorithm

5.1

The Algorithm

To improve the performance of the algorithms for approximate matching of ordinary textual strings, we often divide the query into several parts to improve
the query performance [19]. For example, in case we want to search for textual
strings with k indels, we can eﬃciently enumerate candidates for the matchesby dividing the query into k + 1 substrings and ﬁnding the exact matches ofthese substrings, as at least one of the divided substrings must exactly match
somewhere in the text. Similarly, we also divide the query 3-D structure into
several substructures in our algorithm.
In our algorithm, we ﬁrst divide the query Q of size m into 3k +2 equal-length
substructures of size m = m/(3k + 2) . Note that k is the number of maximum indels deﬁned in section 3, which is considered to be a small constant. We
call each substructure a ‘divided substructure’. Let Qj denote the j-th divided
substructure, i.e., Q[(j − 1)m + 1..j · m ]. We ignore the remaining part (i.e.,Q[(3k + 2)m + 1..m]) in case m is not a multiple of 3k + 2.
Consider the case that Q matches with Pi = P[i..i − k  + k  + m − 1] withthreshold c and (at most) k = k  + k  indels. Let Q and Pi denote the k  reduced subsequence structure of Q and the k  -reduced subsequence structureof P[i..i − k  + k  + m − 1] respectively, such that RM SD(Q , Pi ) ≤ c. Let Qjdenote the largest substructure of Q such that Qj is a subsequence structureof Qj . Let hj denote the ﬁrst index of Qj in Q , i.e., Qj = Q [hj ..hj+1 − 1](h3k+2 = m − k  + 1). Let Pi,j = P [hj ..hj+1 − 1]. It is easy to see that there
are at least 2k + 2 pairs of subsequence structures Qj and Pi,j such that Qj =Qj and Pi,j is a substructure of Pi . We call these (at least 2k + 2 pairs of)substructures ‘ungapped substructures’. Notice that the length of the ungapped
substructures is m . Let the index of an ungapped structure Pi,j in Pi be pj , i.e.,Pi,j = Pi [pj ..pj + m − 1]. It is easy to see that |(j − 1) · m + 1 − pj | ≤ k, as we
allow only at most k indels. Then, an inequality RM SD(Qj , Pi,j ) ≤ c · m/mholds for ungapped substructures Qj and Pi,j , according to the following lemma:
Lemma 2. Consider a pair of two structures S = (s1 , s2 , . . . , sn ) and T =(t1 , t2 , . . . , tn ), both of whose length is n. Let S = (sa1 , sa2 , . . . , san ) besome subsequence structure of S, and let T = (ta1 , ta2 , . . . , tan ). Then,
RM SD(S , T ) ≤ n/n · RM SD(S, T).

Linear-Time Protein 3-D Structure Searching with Insertions and Deletions

317

Proof. According to the deﬁnition of the RMSD, the following inequality holds:


n
1 


RM SD(S , T ) = min  |sa − (R · tai + v)|2R,v
n i=1 in
1 ≤ min  |si − (R · ti + v)|2
R,v
n i=1

= n/n · RM SD(S, T).
(3)

In summary, at least 2k + 2 divided substructures Qj = Q[(j − 1)m + 1..j · m ](among the 3k + 2 divided substructures) must satisfy the following constraint:– There must be some substructure P[.. + m − 1] of P such that
RM SD(Qj , P[.. + m − 1]) ≤ c · m/m and i + (j − 1)m − k ≤  ≤i + (j − 1)m + k.
These 2k + 2 (or more) divided substructures must also satisfy the following
weaker constraint, as an inequality D(S, T) ≤ RM SD(S, T) holds for any pairof same-length structures S and T (see section 2.4 for the deﬁnition of D(S, T)).
– There must be some substructure
P[.. + m − 1] of P such thatD(Qj , P[..+m −1]) ≤ c· m/m and i+(j−1)m −k ≤  ≤ i+(j−1)m +k.
We call the divided substructures that satisfy the latter weaker constraint ‘hit
substructures’ for the position i.
Based on the above discussions, we propose the following simple algorithm
for the k-indel 3-D substructure problem.
Algorithm
1. We ﬁrst enumerate all the positions i in P such that there are at least 2k + 2
hit substructures for the position i, by computing all the D(Qj , P[i..i + m −1]) values for all the pairs of i (1 ≤ i ≤ N − m + 1) and j (1 ≤ j ≤ 3k + 2).
2. For each position i found in step 1, we check the RMSDs between all thepairs of k  -reduced subsequence structure of Q and k  -reduced subsequence
substructure of P[i..i + m − k  + k  + m − 1] such that k  + k  ≤ k andk  − k  ≤ N − m − i + 1. If any one of the checked RMSDs is smaller or equal
to c, output i as the position of a substructure similar to the query Q.
In the next section, we analyze the average-case time complexity of thealgorithm.
5.2

The Average-Case Time Complexity of the Algorithm

For each Qj (whether it is a hit substructure or not), we can compute
D(Qj , P[i..i + m − 1]) for all i (1 ≤ i ≤ N − m + 1) in total O(N ) time,318

T. Shibuya, J. Jansson, and K. Sadakaneas G(P[i..i + m − 1]) (i.e., the centroid of P[i..i + m − 1]) can be computedin O(N ) time for all i. Thus, we can execute the step 1 of the algorithm insection 5.1 in O(k 2 · N ) time, which is in O(N ) as we consider k is a small ﬁxed
constant. Let N  denote the number of candidates enumerated in step 1 of thealgorithm in section 5.1. As the number of pairs to check in step 2 for each position is less than 2m+k Ck (which is in O(mk )), and each RMSD can be computedin O(m) time, the computational complexity of step 2 is O(N  mk+1 ). In total,
the computational complexity of the algorithm is O(N + N  mk+1 ). In the worst
case, the algorithm could be as bad as the naive O(N mk+1 )-time algorithm, asN  could be N at worst.
But, in the following, we show that N   is only in O(N/mk+1 ) and consequently the average-case (expected) time complexity of the algorithm is astonishingly O(N ), under the assumption that P follows the random-walk model.
According to Lemma 1 in section 2.4, the probability that a divided
substruc√
ture Qi is√a hit substructure for the position i is in O(k · c · m/m / m ) =O(c · k 2 / m), under the random-walk √assumption. Consider that the above
probability can be bounded by a · c · k 2 / m if m is large enough, where a is anappropriate constant. Then, the probability that √2k + 2 of the 3k + 2 divided
substructures are hit substructures is O((a · c · k 2 / m)2k+2 · 3k+2 C2k+2 ), whichis in O(c2k+2 · k 5k+4 /mk+1 ). Thus N   is in O(N · c2k+2 · k 5k+4 /mk+1 ), and thefollowing lemma holds, considering that both c and k are small ﬁxed constants.
Lemma 3. N   is in O(N/mk+1 ).
Consequently the expected time complexity of the step 2 of the above algorithm
is only in O(N ). (More precisely, it is O(c2k+2 · k 5k+4 · N ), but we consider thatboth c and k are small ﬁxed constants.) In conclusion, the total expected timecomplexity of the algorithm in section 5.1 is only O(N ), under the assumptionthat P follows the random walk model:4
Theorem 2. The total expected time complexity of our algorithm is O(N ), under the assumption that P follows the random walk model.

6Concluding Remarks

We considered the k-indel 3-D substructure search problem, in which we searchfor similar 3-D substructures from molecular 3-D structure databases, with consideration of indels. We showed that the same problem in arbitrary dimensional
space is NP-hard. Moreover, we proposed a linear expected time algorithm, under the assumption that the number of indels is bounded by a constant andthe database structures follow the random-walk model. There are several open
problems. First of all, the diﬃculty of our problem restricted to 3-D space is
not known. As for our algorithm, its expected time complexity is O(N ) for a
database of size N , but its coeﬃcient, i.e., c2k+2 · k 5k+4 , is very large (c is the4

The same discussion can be done if the query Q follows the random walk model,
instead of P.

Linear-Time Protein 3-D Structure Searching with Insertions and Deletions

319

threshold of the RMSD and k is the maximum number of indels, both of which
we consider as constant numbers). It would be more practical if we can design
algorithms with better coeﬃcients. Another open problem is whether we candesign a worst-case (deterministically) linear-time algorithm for our problem,
though no worst-case linear-time algorithm is known even for the no-indel case.
Acknowledgement. This work was partially supported by the Grant-in-Aid
from the Ministry of Education, Culture, Sports, Science and Technology ofJapan. Jesper Jansson was supported by the Special Coordination Funds for
Promoting Science and Technology.

References
1. Arun, K.S., Huang, T.S., Blostein, S.D.: Least-squares ﬁtting of two 3-D point sets.
IEEE Trans Pattern Anal. Machine Intell. 9, 698–700 (1987)
2. Aung, Z., Tan, K.-L.: Rapid retrieval of protein structures from databases. Drug
Discovery Today 12, 732–739 (2007)
3. Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H.,
Shindyalov, I.N., Bourne, P.E.: The protein data bank. Nucl. Acids Res. 28, 235–
242 (2000)
4. Boyd, R.H., Phillips, P.J.: The Science of Polymer Molecules: An Introduction Concerning the Synthesis, Structure and Properties of the Individual Molecules That
Constitute Polymeric Materials. Cambridge University Press, Cambridge (1996)
5. Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex
Fourier series. Math. Comput. 19, 297–301 (1965)
6. Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete
Appllied Mathematics 9(1), 27–39 (1984)
7. Dayantis, J., Palierne, J.-F.: Monte Carlo precise determination of the end-to-end
distribution function of self-avoiding walks on the simple-cubic lattice. J. Chem.
Phys. 95, 6088–6099 (1991)
8. de Gennes, P.-G.: Scaling Concepts in Polymer Physics. Cornell University Press(1979)
9. Eggert, D.W., Lorusso, A., Fisher, R.B.: Estimating 3-D rigid body transformations: a comparison of four major algorithms. Machine Vision and Applications 9,272–290 (1997)
10. Eidhammer, I., Jonassen, I., Taylor, W.R.: Structure comparison and structure
patterns. J. Computational Biology 7(5), 685–716 (2000)
11. Flory, P.J.: Statistical Mechanics of Chain Molecules. Interscience, New York (1969)
12. Gerstein, M.: Integrative database analysis in structural genomics. Nat. Struct.
Biol., Suppl., 960–963 (2000)
13. Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Proc. 40th Annual Symposium on Foundations of Computer
Science, pp. 512–522 (1999)
14. Kabsch, W.: A solution for the best rotation to relate two sets of vectors. Acta
Cryst. A32, 922–923 (1976)
15. Kabsch, W.: A discussion of the solution for the best rotation to relate two sets ofvectors. Acta Cryst. A34, 827–828 (1978)
16. Kallenberg, O.: Foundations of Modern Probability. Springer, Heidelberg (1997)

320

T. Shibuya, J. Jansson, and K. Sadakane

17. Koehl, P.: Protein structure similarities. Current Opinion in Structural Biology 11,
348–353 (2001)
18. Kramers, H.A.: The behavior of macromolecules in inhomogeneous ﬂow. J. Chem.
Phys. 14(7), 415–424 (1946)
19. Navarro, G.: A guided tour to approximate string matching. ACM Computing
Surveys 33(1), 31–88 (2001)
20. Schwartz, J.T., Sharir, M.: Identiﬁcation of partially obscured objects in two andthree dimensions by matching noisy characteristic curves. Intl. J. of Robotics Res. 6,
29–44 (1987)
21. Shibuya, T.: Eﬃcient substructure RMSD query algorithms. J. Comput.
Biol. 14(9), 1201–1207 (2007)
22. Shibuya, T.: Searching protein 3-D structures in linear time. In: Batzoglou, S. (ed.)
RECOMB 2009. LNCS (LNBI), vol. 5541, pp. 1–15. Springer, Heidelberg (2009)