1

Fast Hinge Detection Algorithms
for Flexible Protein Structures
Tetsuo Shibuya

Abstract— 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 RMSD (Root Mean Square Deviation)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
RMSDh (Root Mean Square Deviation considering hinges)
and its variant RMSDh(k) for comparing two flexible
proteins with hinge regions. We also propose novel efficientalgorithms for computing them, which can detect the hinge
positions at the same time. The RMSDh is suitable forcases where there is one small hinge region in each of thetwo target structures. The new algorithm for computing
the RMSDh runs in linear time, which is the same as thetime complexity for computing the RMSD and is fasterthan any of previous algorithms for hinge detection. The
RMSDh(k) is designed for comparing structures with morethan 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 basedon a new dynamic programming technique. With thesame computational time and space, we can enumerate
the predicted hinge positions. We also test our algorithms
against actual flexible protein structures, and show thatthe hinge positions can be correctly detected by ouralgorithms.
Index Terms— algorithm, protein hinge detection, protein 3-D structure comparison, dynamic programming

3-D structures [7], [19], [28]. Structure comparison algorithms can be categorized into two types: rigid structurecomparison methods and flexible structure comparison
methods. The former methods consider protein structures
as rigid bodies. But there are many proteins whose structures change conformationally. Most of their structures
can be divided into several (almost) rigid substructures
separated by small flexible parts (which often consistsof only one atom) called hinge regions or just ‘hinges’(Figure 1).1 They change their structures by rotatingaround the hinge, due to their physical conditions, relations to other proteins, or some point mutations. The
latter flexible structure comparison methods take hinges
into consideration when they compare structures. The
hinges sometimes take very important roles for theirfunctions [28]. Due to the importance of the roles ofthese flexible proteins, the number of the entries in the
databases of such flexible proteins increases rapidly [5],[9], [11], [23].
There are three tasks when we compare two flexible
structures. At first we have to find the correspondence
between atoms. We next have to find locations of hinges
and finally we have to calculate superposition for eachrigid fragment. But if we have determined the corre-

Hinge

I. I NTRODUCTION
Proteins play enormous variety of roles in living
systems. The functions of the proteins are said to be
determined by their 3-D structures, and consequently the
analysis of protein structures is one of the most importantresearch topics in molecular biology. The analysis ofprotein structures often starts with a comparison of
two similar structures, and there have been proposed atremendous number of methods to compare two protein
T. Shibuya is with Human Genome Center, Institute of Medical
Science, University of Tokyo

Fig. 1. Hinge bending of a protein. A protein sometimes changes
its structure by rotating around an atom, which is called a hinge.
1
Notice that the ‘hinge region’ is different from the notion called‘hinge domain’.

2spondence and the hinge positions, it is not difficult
to compute the superposition. Thus, flexible structurecomparison methods can be categorized into two types.
One is a type of methods that does everything —they find the atom correspondence, the hinge positions,and the superposition simultaneously [4], [25], [30].
The other type of methods is dedicated to only hinge
detection and calculation of superposition [3], [15], [20],[21], [29], assuming that the atom correspondence isgiven. The methods of the former type are more generalthan those of the latter, but they are definitely moredifficult. Note that there are many situations in which
only the latter methods are needed. For example, wealways know the atom correspondence in two structuresof the same, or significantly similar proteins. In casetheir amino acid sequences are similar, we can easilyfind the correspondence by using the ordinary sequencealignment. Our algorithms proposed in this paper are themethods of the latter type, and we do not deal with how
to find the atom correspondence. Note that there is athird approach for hinge detection which predicts hinge
positions from a single structure without comparing withother structures [8], [10], unlike the above comparisonbased methods. But we do not deal with them in thispaper.
When we compare two structures (by either of thetwo approaches), some appropriate scoring measure isdesired. The measure must be mathematically clear andmoreover easy to compute. The RMSD (Root Mean
Square Deviation) [1], [6], [17], [18], [24] is the mostcommonly used measure for comparing two rigid structures (see section II for details). It is defined very clearlyand can be computed very efficiently (in linear time).
But it is designed only for rigid structures. There are nostandard measures to be optimized for flexible structurecomparison, as it seems very difficult to design a measurethat can be efficiently computed.
In this paper, we propose measures for comparing
flexible protein structures, and fast algorithms to compute them. With either of the algorithms, we can obtain
the predicted positions of the hinges at the same time.
We first propose a measure called the RMSDh (RootMean Square Deviation considering hinges), which isa generalization of the RMSD with consideration of asingle hinge region. We also propose an algorithm thatcomputes the RMSDh in linear time, which is the sameas the time complexity for computing the RMSD, eventhough our algorithm detects the hinge position at thesame time. It is much faster than any previous hinge
detection algorithms, which require at least quadratic
time. We then generalize the RMSDh for proteins withat most k hinges, and call the generalized measure the

RMSDh(k) . We propose an O(kn2 )-time and O(n)-spacealgorithm for computing it, where n is the length of thestructures to be compared. We will also show that we candetect the hinge positions with the same time and spacecomplexity, by using a divide-and-conquer technique.
In these algorithms, we assume that each hinge region
consist of only one atom (residue). Precisely, if the hinge
region consists of a single atom, the angles of the rotation
is limited due to physical/chemical restrictions. On theother hand, the limitation can be ignored if we consider
hinge regions with several residues. In this paper, we
assume that each hinge region consist of only one atom,
but we ignore the limitation. By doing so, we cansimplify the problem and fast algorithms can be designed
as shown in later sections. Moreover, the algorithms canbe used as a heuristic algorithm for proteins with nonsingle residue hinges, as shown in the computational
experiments in section V.
Availability: FastHinge 1.0, the program developed for this research, can be downloaded fromhttp://www.hgc.jp/˜tshibuya/softwares/. Currently, theprogram runs only on Windows or SunOS.
Organization of this paper: In section II, we present
the definition of the RMSD and algorithms for computing it as preliminaries. Then we propose the new
RMSDh measure and algorithms for it in section III.
We propose the RMSDh(k) measure and algorithms for
it in section IV. In section V, we show computational
experiments. Finally in section VI, we conclude ourresults and discuss future work.
II. P RELIMINARIES
A. RMSD: The Root Mean Square Deviation
A protein 3-D structure can be represented by various
ways, but one popular way is to represent it by a list of
3-D coordinates of its backbone Cα atoms. The RMSD
(root mean square deviation) [1], [6], [17], [18], [24]is the most common way to compare two lists of 3-D
coordinates.
Let the two 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 the coordinates of
the i-th Cα atoms of P and Q, respectively. Then the
RMSD between P and Q is defined as the minimum
value ofvun
u1 XDR,⃗v (P, Q) = t∥⃗
pi − (R · ⃗qi + ⃗v )∥2

n i=1

over all the possible rotation matrices R and translation vectors ⃗v , where ∥ · ∥ denotes the norm. Let
RM SD(P, Q) denote the minimum value, and let

3R̂(P, Q) and ⃗vˆ(P, Q) denote the R and ⃗v that satisfy
DR,⃗v (P, Q) = RM SD(P, Q).

III. RMSD H : A L INEAR -T IME C OMPUTABLEM EASURE FOR H INGE D ETECTION
A. Definition of the RMSDh

B. How to compute the RMSD
In this section, we briefly describe how to compute
the RMSD. Let R · X denote the structure X rotatedby the rotation matrix R. If the rotation matrix R is
fixed, DR,⃗v (P, Q) is known to be minimized when thecentroid of R · Q is translated to the centroid of P by
the translation vector ⃗v , regardless of what the rotation
matrix R is. Hence, if both P and Q are translated so that
their centroids are moved to the origin of the coordinates,
the RMSD problem is reduced to a problem of finding RP(i.e., R̂(P, Q)) that minimizes FR (P, Q) = ni=1 ∥⃗pi −2R · ⃗qi ∥ .
From now on, we consider that both structures havebeen already translated so that both centroids are moved
to the origin of the coordinates. Then we can computeR̂(P, Q) in linear time [1], [17], [18] as follows. LetPn
H =⃗i · ⃗qi t , where ⃗v t means the transpose ofi=1 p
vector ⃗v . Clearly, H can be computed in O(n) time. ThenP
FR (P, Q) can be described as ni=1 (⃗pi t p⃗i + ⃗qi t ⃗qi ) −trace(R · H), and trace(RH) is maximized when R =V U T , where U ΛV is the singular value decomposition(SVD) of H and AT means the transpose of 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 computedin O(d3 ) time for a d × d matrix [13]. Note that there
are degenerate cases where det(V U T ) = −1, whichmeans that V U T is a reflection matrix. See [1], [6]for details to deal with the degenerate cases. We cancompute the RMSD value in linear time once we haveobtained R̂(P, Q). In total, we can compute the RMSD
value in O(n) time.
Let S[i..j] denote the substructure of S from the i-th
atom to the j -th atom (e.g., P[i..j] = {⃗pi , p⃗i+1 , . . . , p⃗j }).
According to [26], the RMSD and corresponding superposition between two substructures P[i..j] and Q[i..j]can be computed in constant time for any i and j , after
linear-time preprocessing, as follows: RM SD(P[i..j],Q[i..j]), R̂(P[i..j], Q[i..j]) and ⃗vˆ(P[i..j], Q[i..j]) canP
be computed in O(1) time if we are given jk=i p⃗k ,
Pj
Pj
Pj
Pj
⃗k ⃗qk t .
qk t ⃗qk , andqk ,⃗k t p⃗k ,
k=i p
k=i ⃗
k=i ⃗
k=i p
These values can be computed also in constant time, ifP
we compute the following values in advance: ℓk=1 p⃗k ,PPPPℓ⃗k t p⃗k , ℓk=1 ⃗qk , ℓk=1 ⃗qk t ⃗qk , and ℓk=1 p⃗k ⃗qk t , for
k=1 p
all ℓ (1 ≤ ℓ ≤ n). It is easy to see that all of these values
can be computed in O(n) time in total. Thus we conclude
that the RMSD and corresponding superposition between
P[i..j], and Q[i..j] can be computed in O(1) time after
linear-time preprocessing.

In this section, we consider a new measure to compare
two flexible protein 3-D structures that are very similar
except for one small hinge region. We consider thatthe hinge region is so small that it can be considered
as only a single backbone atom.2 Note that there areatoms other than the Cα atoms on the backbone, andthe hinge can be located at any of them. Let the two
structures to be compared be P = {⃗p1 , p⃗2 , . . . , p⃗n } and
Q = {⃗q1 , ⃗q2 , . . . , ⃗qn }, and consider that the hinge islocated at a backbone atom between the ℓ-th Cα atomand the (ℓ+1)-th Cα atom, or at the ℓ-th Cα atom. ThenP[1..ℓ] and Q[1..ℓ] should be similar to each other, andP[ℓ+1..n] and Q[ℓ+1..n] should also be similar to eachother. Thus if the two rigid parts of Q are rotated andtranslated appropriately with different rotation matrices
and translation vectors, P and the transformed Q shouldbe very similar to each other, and consequently shouldhave a small RMSD value. It means thatrGℓ (P, Q) =min

R1 ,R2 ,⃗v1 ,⃗v2

1
n (R , ⃗{K ℓ (R1 , ⃗v1 ) + Kℓ+1
2 v2 )}
n 1

must be a very small value, where
Kxy (R, ⃗v ) =yX∥⃗pi − (R · ⃗qi + ⃗v )∥2 .

i=xHere, R1 and R2 are (possibly different) rotation matrices and ⃗v1 and ⃗v2 are (also possibly different) translation
vectors. It can be used as the similarity measure between
P and Q, if the hinge is at or around the ℓ-th atom. Thisvalue is the same as the RMSD if R1 = R2 and ⃗v1 = ⃗v2when they are optimized.
But we do not know the actual hinge position inmost cases when we compare two structures. Hence, we
consider the minimum value of Gℓ (P, Q) over all thepossible hinge positions ℓ, i.e. min1≤ℓ<n Gℓ (P, Q), as
the measure to compare a pair of flexible structures with
one hinge. We call it the RMSDh (Root Mean Square
Deviation considering hinges), and let RM SDh(P, Q)
denote this value. Note that the RMSDh is always
smaller than or equal to the RMSD. Let ℓ̂ denote theℓ that minimizes Gℓ (P, Q). Then we can predict thatthe hinge is located between the ℓ̂-th residue and the(ℓ̂ + 1)-th residue.
The above optimized translations and rotations does
not consider any restrictions on the locations of P [ℓ],2

We do not consider longer hinge regions. But it does not meanthat our algorithms cannot be applied to flexible proteins with longer
hinge regions.

4Q[ℓ], P [ℓ+1], and Q[ℓ+1], i.e. the distance between P [ℓ]and P [ℓ+1] and that between Q[ℓ] and Q[ℓ+1] should be
fixed. But in the ideal case where the structures P [1..ℓ]and Q[1..ℓ] are all the same structure, and the structures
P [ℓ+1..n] and Q[ℓ+1..n] are also all the same structure,
we can ignore the restriction, as the above optimized
RMSDh value becomes zero. In practice, these fragments
structures should be very similar (almost the same) toeach other, and thus we think that there is no problem
in ignoring the restriction.

B. How to compute the RMSDh
The problem of computing RM SDh(P, Q) can be
reduced to the problem computing
min Lℓ1 (P, Q) + Lnℓ+1 (P, Q),

1≤ℓ<n

where
Lyx (P, Q) = min
R,v

y
X

∥⃗
pi − (R · ⃗qi + ⃗v )∥2 .

i=x

Noticethat
Lji (P, Q)=
2n·(RM SD(P[i..j], Q[i..j])) , which means that we cancompute the RMSDh value by computing 2n − 2 RMSD
values, i.e., RM SD(P[1..ℓ], Q[1..ℓ]) and RM SD(P[ℓ+1..n], Q[ℓ + 1..n]) for all ℓ (1 ≤ ℓ < n). According
to section II-B, the computation of each RMSD can bedone in constant time after linear-time preprocessing.
Hence, the RMSDh value can be computed in O(n)time, including the preprocessing phase. Moreover, we
can detect the corresponding hinge position at the sametime.
IV. RMSD H(k) : M ORE F LEXIBLE M EASURES
A. Definition of the RMSDh(k)In the previous section, we considered only one hinge
region, but many flexible protein structures are known
to have more than one hinge region. In this section,
we consider that the target structures have k hinges at
most, which means they can be divided into k + 1 rigid
fragments. Again, let P = {⃗p1 , p⃗2 , . . . , p⃗n } and Q ={⃗q1 , ⃗q2 , . . . , ⃗qn } be the flexible structures to be compared, and let the positions of the hinges be ℓ1 , ℓ2 , . . . , ℓk .
To ease discussion, let ℓ0 = 1 and ℓk+1 = n + 1. Then,with discussion similar to section III-A, the value
Hℓ1 ,...,ℓk (P, Q) =min

R0 ,...,Rk ,⃗v0 ,...,⃗vk

v
u
k
u1 X
u
ℓ
−1
t
Kℓjj+1 (Rj , ⃗vj )n j=0

should be a very small value, where Kxy (R, ⃗v ) denotes
the expression defined in section III-A, R0 , R1 , . . . , Rk

are possible rotation matrices, and ⃗v0 , ⃗v1 , . . . , ⃗vk arepossible translation vectors.
But, as in section III-A, we do not know the actual
hinge positions in most cases. Thus we propose to use
the minimum value of the above expression over all thepossible sets of k hinge positions {ℓ1 , ℓ2 , . . . , ℓk }, i.e.,min1≤ℓ1 <ℓ2 <···<ℓk ≤n

Hℓ1 ,...,ℓk (P, Q),

as the measure for comparing such flexible proteins. We
call it RMSDh(k) , and let RM SDh(k) (P, Q) denote thevalue. As in section III-A, the positions ℓ1 , ℓ2 , . . . , ℓk thatminimizes the above value can be used as the predicted
locations of the hinges. Note that the RMSDh(1) is thesame as the RMSDh. Note also that the RMSDh(k) isalways smaller than or equal to the RMSDh(k−1) , for any
k , and that RMSDh(n−1) = 0 no matter how different
the proteins are.
B. How to Compute the RMSDh(k)As in the case of computing the RMSDh, the problem
of computing the RMSDh(k) can be reduced to the
problem of computing
min

k
X

1≤ℓ1 <ℓ2 <···<ℓk ≤n

ℓ

Lℓi+1
i

−1

(P, Q),

i=0

where Lji (P, Q) is the same expression as defined in
section III-B. There are n−1 Ck possible sets of k hinge
positions, which means that we might need O((k + 1) ·n−1 Ck ) time or more if we naively compute it. But, in thefollowing, we propose an algorithm based on dynamic
programming (DP), which compute the RMSDh(k) inO(kn2 ) time and O(n) space.
To compute the RMSDh(k) , we consider the following
value:
Ii,r =

min1≤ℓ1 <ℓ2 <···<ℓr ≤i

r
X

ℓ

Lℓj+1
j

−1

(P[1..i], Q[1..i]),j=0where we let ℓ0 = 1 and ℓr+1 = i + 1 to ease discussion.
1
Then the RMSDh(k) is described as (In,k /n) 2 . Note that
Ii,r is defined only when 0 ≤ r < i ≤ n. In case r =0, it can be easily seen from the definition that Ii,0 =Li1 (P, Q) for any i. In addition, the following equation
holds when r ≥ 1:
Ii,r = min {Ij,r−1 + Lij+1 (P, Q)}.
r≤j<i

The above equation represents a DP algorithm forcomputing In,k and consequently the RMSDh(k) (i.e.,
1(In,k /n) 2 ). During the DP procedure, we compute In,rfor all r (1 ≤ r ≤ k ), from which we can immediately
obtain the RMSDh(r) values (1 ≤ r ≤ k ) too.

5

Recall that the Lji (P, Q) can be computed in constant time after linear-time (O(n)) preprocessing (seesection III-B). Thus the values Ii,0 for all i can becomputed in O(n) time in total. Moreover, in case r > 0,
the value Ii,r can also be computed in O(i − r) time byusing the values of Ij,r−1 (j < i). It means that theoverall computation time required for computing In,k(and consequently the RMSDh(k) ) is O(kn2 ). The spacerequired for computing the RMSDh(k) is only O(n),because we only need the information of Ij,r−1 values(for all j such that j < i) to compute the Ii,r values forany i.
To compute the positions of the corresponding hinges,
we can use the ordinary tracing back technique for DP
algorithms, without increasing the time complexity of theoverall algorithm. But the space requirement increasesto O(nk) space, if we do it naively by using a table ofO(nk) size for tracing back. It can be reduced to O(n)space by using a divide-and-conquer technique similar to
the Hirschberg algorithm for sequence alignment [14], asfollows.
Let
Ji,r =rX

mini≤ℓ1 <ℓ2 <···<ℓr ≤n

ℓ

Lℓj+1
j

−1

(P[i..n], Q[i..n]),j=0where we let ℓ0 = i and ℓr+1 = n+1 to ease discussion.
Ji,r can also be computed by DP, as the following
equation holds:
Ji,r = min {Lji (P, Q) + Jj+1,r−1 }.
i≤j<nMoreover the In,k can be described as follows,3 lettingk ′ = ⌊k/2⌋ and k ′′ = k − k ′ − 1:
In,k =mink′ <i<n−k′′Ii,k′ + Ji+1,k′′ .

The i that minimizes this value is the position of the(k ′ + 1)-th hinge. Let the position be p. To compute it,
we need O(kn2 ) time and O(n) space.
Similarly, we can next compute the position of the′(⌊k ′ /2⌋ + 1)-th hinge by computing the RMSDh(k )between P[1..p − 1] and Q[1..p − 1] in O(k ′ p2 ) timeand O(p) space. Moreover, we can also compute theposition of the (k ′ + 1 + ⌊k ′′ /2⌋)-th hinge by computing′′
the RMSDh(k ) between P[p + 1, n] and Q[p + 1, n]in O(k ′′ (n − p)2 ) time and O(n − p) space. Notice thatk ′ p2 +k ′′ (n−p)2 < kn2 /2, and kn2 +kn2 /2+kn2 /22 +· · · < 2kn2 . It means that we can compute all the hinge
positions in O(kn2 ) time and O(n) space by repeating
the above until we obtain all of them.
3
Once we get the In,k , we can immediately compute
the RMSDh(k) value, as 1 was described before, i.e.,
RM SDh(k) (P, Q) = (In,k /n) 2 .

V. E XPERIMENTAL R ESULTS
We tested our algorithms against the 14 pairs of proteins shown in Table I, taken from the PDB database [2].
In the table, the RMSD column shows the RMSD
between two structures in each set. The top 12 pairs ofproteins in the table are flexible proteins. The adenosylcobinamide kinase [27] in the set AK is known
to be a flexible protein with shearing movement. The
HIV-1 protease [22] in the set HIV is the major drug
target against the AIDS (acquired immunodeficiency
syndrome), whose flexibility is said to affect the effectiveness of drugs. The lactate dehydrogenase (LDH) [12]is known to be a flexible protein with very dynamic
movement, i.e., more than 10Å. The other 9 flexible
protein sets are pairs of flexible proteins listed in the
Hinge Atlas database [11], which contains very accurate
annotations on hinge positions. As for the sets other than
the above 12 flexible proteins, the AT set consists of two
independently determined structures of the same proteinin the same state, and the MR set is a pair of unrelated
proteins.
Tables II and III show the experimental results against
the 12 flexible protein pairs. In the table, the ‘Our
results’ rows show our results of the computation of
the RMSDh(k) for 1 ≤ k ≤ 5, and the corresponding
hinge positions (by showing the fragments divided by
the predicted hinge positions). See section V-A for themeaning of the mark ‘†’ in these rows. The ‘FlexProt’rows show the results of the FlexProt program [25] withthe default parameter settings (i.e., 3.0Å is set to the
maximal RMSD between matched fragments, and 15 is
set to the minimal size of matched fragments), which
is one of the most widely used tools for detection of
hinge positions. The ‘RMSDh(k) ’ column shows our
RMSDh(k) values for 5 different k s (k = 1, 2, . . . , 5).
The ‘Fragments divided by hinges’ column shows thefragments divided by the predicted hinges (or annotatedhinges). In the column, ‘[x..y ]’ denotes the fragment thatstarts at the x-th residue and ends at the y -th residue.
‘(rÅ)’ written after the fragment means that the RMSD
between the two fragments at the position is rÅ. Notethat ‘(rÅ)’ is omitted for the FlexProt results and theannotations. The fragments that end at (or near to) the
annotated hinge positions are marked with ‘*’ (i.e., theirdistance to the annotated position are at most 3 residues).
The ‘Annotation in ...’ rows and the ‘Hinge Atlas’ rows
show the protein pairs’ known annotations in literatureor the Hinge Atlas database. In the experiment for the set
AK, HIV, and LDH, we show the annotations given in[27], [16] and [12], respectively. These annotations are
based on manual analysis on the structures. For other6

TABLE IP ROTEIN STRUCTURES TESTED IN OUR EXPERIMENTS .

Sets
AK
HIV
LDH
BTL
DPB
EPA
ENL
GB
LF
LB
RB
TC
AT
MR

Proteins
Adenosylcobinamide kinaseHIV-1 protease
Lactate dehydrogenase (LDH)
Bacteriophage T4 Lysozyme
DNA Polymerase beta
Elastase of Pseudomonas Aeruginosa
EnolaseGlutamine Binding Protein
Lactoferrin
LAO Binding Protein
Ribose Binding Protein
Troponin C
Asparatate transcarbamoylase
Myoglobin / Rhodopsin

PDB IDs
1CBU(B),1C9K(B)
3HVP, 4HVP(A)1LDM, 6LDH
149L, 1L53
1BPD, 2BPG
1EZM, 1U4G
3ENL(A), 1EBG
1GGG(A), 1WDN (residues: 2–221)
1LFG, 1LFH
2LAO, 1LST
1URP(A), 2DRI
4TNC(A, residues: 3–157), 2TN4
1RAB(A), 1RAC(A)101M, 1AYR(A) (residues:1–154)

datasets, we show the annotations in the Hinge Atlas
database. The Hinge Atlas annotations are made also
by manual annotation, but utilizing many state-of-the-art
hinge detection methods, such as the FlexProt.

A. Estimation of the Numbers of Hinges
In this section, we discuss how to estimate the numberof hinges in the given pair of protein structures, andthe accuracy of the method. In the tables II and III,
we show the RMSD value for each pair of fragments
divided by the predicted hinges.4 As these fragments
should be ‘rigid’ fragments, these RMSD values shouldbe very small. Thus we can predict the number of hinges
by finding the smallest k (k ≥ 1) such that all thefragments have RMSDs smaller than some threshold.
In the experiments, we used 1.5Å as the threshold. Intables II and III, we marked the predicted number ofhinges with ‘†’ in the ‘Methods’ column of the ‘Our
results’ rows. In all the experiments except for the set
ENL, the predicted numbers of hinges were at most 3.
Note that it was 7 in the experiment for the ENL set,
which is not shown in the table.
With the above method, we succeeded in predicting
the number of hinges correctly (i.e. same as the annotations) for 9 of the 12 data sets, i.e., HIV, LDH, DPB,
EPA, GB, LF, LB, RB, and TC. On the other hand,
the FlexProt program with the default parameter settings
could predict them correctly only for 4 of the 12 sets,i.e., AK, GB, LF and LB.
4Computation of these fragments’ RMSDs requires only additionalO(k) time, by using the technique described in section II-B.

#residues
180
97
329
164
324
298
436
220
691
238
271
155
310
154

RMSD (Å)
3.1092
1.24501.78861.8707
10.3347
1.2194
1.4662
5.33806.42854.69854.06243.72630.171419.3841

TABLE IV
RMSD/RMSD H /RMSD H(k) OF SETS AT AND MR ( IN Å).
Sets
AT
MR
Sets
AT
MR

RMSD
0.171419.3841
RMSDh(3)0.150810.7877

RMSDh
0.167215.9145
RMSDh(4)0.14309.3194

RMSDh(2)0.155513.4793
RMSDh(5)0.13808.3340B. Correctness of the Detected Hinge Positions
As for the hinge positions, we succeeded in predicting
all the hinge positions correctly for 6 of the 12 sets,that is, LDH, EPA, GB, LF, LB, and RB, by using theestimated number of hinges described in the previous
section. Moreover, we could succeeded in predictingsome of the hinge positions correctly for other 3 sets(HIV, BTL, and TC). Our prediction was different fromthe annotations for the other 3 sets, i.e., AK, HIV, andENL. But even for these unsuccessful 3 sets, we can findsome of the hinge positions correctly, if we set somedifferent k .
On the other hand, the FlexProt (with the default
parameters) predicted all the hinge positions correctly
only for 1 of the 12 sets (i.e., AK). The FlexProt
predicted some of the hinge positions correctly for 4 sets
(i.e., DPB, GB, RB and TC). For the other 7 sets, the
FlexProt could not predict any correct hinge positions
with the default parameter settings.
C. Other experiments
We also computed the RMSD, RMSDh, and
RMSDh(k) values for two independently determined
structures of the same protein in the same state (i.e.,

7

TABLE VT IME ( SEC ) FOR COMPUTING RMSD H(k) FOR ALL k (1 ≤ k < n).
SetsTime (sec)SetsTime (sec)SetsTime (sec)

AK
0.203
EPA
0.531
RB
0.437

HIV
0.047
ENL
1.234
TC
0.172

LDH
0.640
GB
0.313
AT
0.594

BTL
0.156
LF
3.516
MR
0.141

DPB
0.640
LB
0.344

the AT set), which are shown in Table IV. Note that thesame set is used in [20] for a test on a pair of almost-thesame proteins. Of course all the values are very small,
including the RMSD value. We consider that we do nothave to compute RMSDh/RMSDh(k) values if the RMSD
is very small like in this case.
In contrary, we compared two totally different structures in the set MR (i.e., a myoglobin and a rhodopsin iscompared). In this case, all the values are far larger thanthose in any other experiments. These experiments showthat our measures are effective for discriminating flexible
protein pairs from other normal rigid protein pairs, unlessthe two flexible proteins have a very similar structure.
D. Computation time
Table V shows the time for computing the RMSDh(k)values and corresponding hinge positions for all k (1 ≤k < n), using a single 3.2 GHz Pentium D processor
with 2 GB memory. It shows that the computation timeis very reasonable (most are less than a second), which isfaster than any other known hinge detection algorithms.
Note that the computation time is much smaller in casek is smaller.
VI. C ONCLUSIONS AND F UTURE W ORK
We proposed two new measures for comparing two
flexible proteins, which can be very efficiently computed.
The first measure, RMSDh, can be computed in linear time, while the other measure, RMSDh(k) can becomputed in O(kn2 ) time, where k is the number ofhinges, and n is the length of the structures. Moreover,
we can detect the hinge positions while we computethe measures. Both of the measures are tested on actual
flexible proteins to demonstrate the accuracy and theefficiency of our algorithms.
Some flexible proteins have large flexible regions. Our
measure considers only small flexible regions, and somemore flexible measure might be desired for structureswith larger flexible regions. Moreover, our algorithms
suppose that we know the correspondence between
residues of two proteins in advance, but we do not inmany cases. Thus, we should develop as future worka flexible structure alignment algorithm that finds theresidue correspondence minimizing the RMSDh or the
RMSDh(k) .
Not so many 3-D structures of flexible proteins are
solved today, but the number is now increasing. In
the future, there should be more sample structures forevery flexible protein, which means we should develop
multiple alignment algorithms for flexible proteins tocompare them simultaneously.
ACKNOWLEDGEMENT
This work was partially supported by the Grant-in-Aid
for Young Scientist (B) No. 20700264 from the Ministryof Education, Culture, Sports, Science and Technologyof Japan.
R EFERENCES[1] Arun, K. S., Huang, T. S., and Blostein, S. D. 1987. Leastsquares fitting of two 3-D point sets. IEEE Trans Pattern Anal.
Machine Intell., 9, 698–700.
[2] 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.
[3] Boutonnet, N. S., Rooman, M. J., and Wodak, S. J. 1995. Automatic analysis of protein conformational changes by multiple
linkage clustering, J. Mol. Biol., 253, 633–647.
[4] Damm, K. L., and Carlson, H. A. 2006. Gaussian-weighted
RMSD superposition of proteins: a structural comparison for
flexible proteins and predicted protein structures, Biophys. J.,
90, 4558–4573.
[5] Echols, N., Milburn, D., and Gerstein, M. 2003. MolMovDB:
analysis and visualization of conformational change and structural flexibility, Nucleic Acids Res., 31(1), 478–482.
[6] Eggert, D. W., Lorusso A., and Fisher, R. B. 1997. Estimating
3-D rigid body transformations: a comparison of four majoralgorithms. Machine Vision and Applications, 9, 272–290.
[7] Eidhammer, I., Jonassen, I., and Taylor, W. R. 2000. Structure
Comparison and Structure Patterns, J. Comput. Biol., 7(5), 685–
716.
[8] Emekil, U., Schneidman-Duhovny, D., Wolfson, H. J., Nussinov, R., and Haliloglu, T. 2008. HingeProt: Automated prediction of hinges in protein structures, Proteins, 79, 1219–1227.
[9] Flores, S., Echols, N., Milburn, D., Hespenheide, B., Keating,K., Lu, J., Wells, S., Yu, E. Z., Thorpe, M., and Gerstein, M.,
2006. The database of macromolecular motions: new features
added at the decade mark, Nucleic Acids Res., 34, D296–D301.
[10] Flores, S. C., and Gerstein, M. B. 2007. FlexOracle: predicting flexible hinges by identification of stable domains, BMC
Bioinformatics, 8, 215.
[11] Flores, S. C., Lu, L. J., Yang, J., Carriero, N., and Gerstein,
M. B. 2007. Hinge Atlas: relating protein sequence to sites ofstructural flexibility, BMC Bioinformatics, 8, 167.
[12] Gerstein M., and Chothia, C. 1991. Analysis of protein loop
closure, two types of hinges produce one motion in lactate
dehydrogenase, J. Mol. Biol., 220, 133–149.
[13] Golub, G. H., and Van Loan, C. F. 1996. Matrix Computation.
3rd eds., John Hopkins University Press,[14] Hirschberg, D. S. 1975. A linear space algorithm for computing
maximal common subsequences, Commun. ACM, 18, 341–343.

8[15] Huang, E. S., Rock, E. P., and Subbiah, S. 1993. Automatic andaccurate method for analysis of proteins that undergo hingemediated domain and loop movements, Curr. Biol., 3(11), 740–
748.
[16] Jacobs, D. J., Rader, A. J., Kuhn, L. A., and Thorpe, M. F. 2001.
Protein flexibility predictions using graph theory, Proteins:
Structure, Function, and Genetics, 44. 150–165.
[17] Kabsch, W. 1976. A solution for the best rotation to relate two
sets of vectors. Acta Cryst., A32, 922–923.
[18] Kabsch, W. 1978. A discussion of the solution for the bestrotation to relate two sets of vectors. Acta Cryst., A34, 827–828,[19] Lemmen, C., and Lengauer, T. 2000. Computational methods
for the structural alignment of molecules, J. Computer-Aided
Molecular Design, 14, 215–232.
[20] Nigham A., and Hsu, D. 2007. Protein Conformational Flexibility Analysis with Noisy Data, International Conference on
Research in Computational Molecular Biology (RECOMB),[21] Ochagavia, M. E., Richeele, J., and Wodak, S. J. 2002. Advanced pairwise structure alignments of proteins and analysis
of conformational changes, Bioinformatics, 18(4), 637–640.
[22] Perryman, A. L., Lin, J., and McCammon. A. 2004. Hiv1 protease molecular dynamics of a wild-type and of thev82f/i84v mutant: Possible contributions to drug resistance anda potential new target site for drugs, Protein Science, 13, 1108–
1123.
[23] Qi, G., Lee, R., and Hayward, S., 2005. A comprehensive
and non-redundant database of protein domain movements,
Bioinformatics, 21(12), 2832-2838.
[24] Schwartz J. T., and Sharir, M. 1987. Identification of partiallyobscured objects in two and three dimensions by matching noisy
characteristic curves. Intl. J. of Robotics Res., 6, 29–44.
[25] Shatsky, M., Nussinov, R., and Wolfson, H. J. 2004. FlexProt:
Alignment of Flexible Protein Structures without a Predefinitionof Hinge Regions, J. Comput. Biol., 11(1), 83–106.
[26] Shibuya, T. 2007. Efficient Substructure RMSD Query Algorithms, J. Comput. Biol., 14(9), 1201–1207.
[27] Thompson, T. B., Thomas, M. G., Escalante-Semerena, J. C.,
and Rayment, I. 1998. Three-dimensional structure of adenosylcobinamide kinase/adenosylcobinamide phosphate guanylyltransferase from salmonella typhimurium determined to 2.3 aresolution, Biochemistry, 37(21), 7686–7695.
[28] Wolfson, H. J., Shatsky, M., Scheneidman-Duhovny, D., Dror,O., Shulman-Peleg, A., Ma, B., and Nussinov, R. 2005. From
Structure to Function: Methods and Applications, Current Protein and Peptide Science, 6, 171–183.
[29] Wriggers, W., and Schulten, K. 1997. Protein domain movements: detection of rigid domains and visualization of hinges incomparisons of atomic coordinates, Proteins: Structure, Function, and Genetics, 29, 1–14.
[30] Ye, Y., and Godzik, A. 2003. Flexible structure alignment by
chaining aligned fragment pairs allowing twists, Bioinformatics,
19, Suppl. 2, ii246–ii255.

Tetsuo Shibuya, Ph.D. received the Bachelorof Science, the Master of Science, and the
Ph.D. of Science from University of Tokyo,
in 1995, 1997, and 2002 respectively. His
research interest is on algorithms in computational biology. He was a researcher at
IBM Tokyo Research Laboratory from 1997
to 2004. He was also a visiting researcher at
RIKEN from 2001 to 2008. He is an assistantprofessor at University of Tokyo from 2004. He is a board member of Japanese Society for Bioinformatics, SIG Bioinformatics ofInformation Processing Society of Japan, and many others. He has
also been in program committees of many conferences, including
Genome Informatics Workshop, VLDB bioinformatics, Workshop
of Data Mining in Bioinformatics, and Workshop on Algorithms
and Computation. He is a member of the JSBi (Japanese Society
for Bioinformatics), the IPSJ (Information Processing Society ofJapan), and the IEICE (Institute of Electronics, Information andCommunication Engineers).

9

TABLE IIR ESULTS OF HINGE DETECTION (1/2). F RAGMENTS WHICH END NEAR AT THE ANNOTATED HINGE POSITIONS ARE MARKED WITH ‘*’.

Sets

AK

HIV

Methods
k=1
k=2†k = 3
Our
results
k=4

RMSDh(k)2.4417 Å
0.9773 Å
0.7467 Å

k=50.4755 Å

FlexProt
Annotation in [27]k=1
†k = 2
k=3
Ourresults
k=4
k=5

LDH

FlexProt
Annotation in [16]k=1
†k = 2
k=3
Ourresults
k=4
k=5

BTL

DPB

EPA

FlexProt
Annotation in [12]†k = 1
k=2
k=3
Our
resultsk=40.5386 Å

––
1.1064 Å
0.7267 Å
0.6483 Å
0.5795 Å
0.5359 Å
––
1.6160 Å
1.1436 Å
0.8902 Å
0.7234 Å
0.6496 Å
––
0.8614 Å
0.5334 Å
0.4684 Å
0.4266 Å

k=5

0.3820 Å

FlexProt
Hinge Atlas
k=1†k = 2
k=3
Ourresultsk=4––1.8047 Å
1.0460 Å
0.8625 Å

k=50.8011 Å

FlexProt
Hinge Atlas†k = 1
k=2
k=3
Our
resultsk=4––0.6392 Å
0.5612 Å
0.5187 Å

k=5

0.4325 Å

FlexProt
Hinge Atlas

0.8368 Å

0.4867 Å

––Fragments divided by hinges[1..52](4.47Å), [53..180](0.51Å)[1..34](1.00Å)*, [35..51](1.85Å), [52..180](0.79)Å)[1..34](1.00Å)*, [35..47](1.44Å), [48..52](1.19Å), [53..180](0.51Å)[1..32](0.40Å)*, [33..35](0.33Å), [36..47](0.77Å), [48..52](1.19Å),[53..180](0.51Å)[1..32](0.40Å)*, [33..35](0.33Å)*, [36..45](0.44Å), [46..50](0.55Å),[51..53](0.58Å), [54..180](0.49Å)[1..36]*, [39..180][1..34], [35..180][1..33](0.64Å)*, [34..97](1.28Å)[1..44](0.78Å)*, [45..56](0.71Å)*, [57..97](0.67Å)[1..23](0.66Å)*, [24..44](0.54Å)*, [45..56](0.71Å)*, [57..97](0.67Å)[1..23](0.66Å)*, [24..38](0.35Å)*, [39..53](0.73Å)*, [54..80](0.57Å),[81..97](0.48Å)[1..8](0.26Å), [9..23](0.58Å)*, [24..38](0.35Å)*, [39..53](0.73Å)*,[54..80](0.57Å), [81..97](0.48Å)— No hinge detected —[1..15], [25..34], [55..97] (i.e., [16..24] and [35..54] are flexible regions)[1..116](2.05Å), [117..329](1.32Å)[1..97](0.42Å)*, [98..109](1.07Å)*, [110..329](1.35Å)[1..97](0.42Å)*, [98..109](1.07Å)*, [110..324](1.01Å), [325..329](1.51Å)[1..97](0.42Å)*, [98..109](1.07Å)*, [110..305](0.80Å), [306..324](0.45Å),[325..329](1.51Å)[1..96](0.406Å)*, [97..109](0.92Å)*, [110..121](0.45Å), [122..305](0.72Å),[306..324](0.45Å), [325..329](1.51Å)— No hinge detected —[1..97], [98..109], [110..329][1..74](1.08Å), [75..164](0.62Å)[1..11](0.48Å)*, [12..75](0.41Å), [76..164](0.61Å)[1..11](0.48Å)*, [12..73](0.39Å), [74..93](0.37Å), [94..164](0.55Å)[1..11](0.48Å)*, [12..73](0.39Å), [74..93](0.37Å), [94..161](0.47Å),[162..164](0.32Å)[1..11](0.48Å)*, [12..73](0.39Å), [74..93](0.37Å), [94..130](0.32Å),[131..161](0.41Å), [162..164](0.32Å)— No hinge detected —[1..12], [13..80], [81..167][1..83](0.81Å), [84..324](2.04Å)[1..83](0.81Å), [84..252](1.15Å), [253..324](1.02Å)[1..82](0.79Å), [83..139](0.80Å), [140..252](0.83Å), [253..324](1.02Å)[1..82](0.79Å), [83..139](0.80Å), [140..252](0.83Å), [253..299](1.03Å),[300..324](0.66Å)[1..82](0.79Å), [83..139](0.80Å), [140..252](0.83Å), [253..291](0.72Å),[292..296](0.88Å), [297..324](0.80Å)[9-88]*, [89-324][1..88], [89..263], [264..324][1..133](0.80Å)*, [134..298](0.47Å)[1..83](0.39Å), [84..133](0.96Å)*, [134..298](0.47Å)[1..81](0.38Å), [82..95](0.36Å), [96..133](0.90Å)*, [134..298](0.47Å)[1..78](0.38Å), [79..98](0.57Å), [99..115](0.31Å), [116..132](0.89Å)*,[133..298](0.48Å)[1..78](0.38Å), [79..98](0.57Å), [99..114](0.24Å), [115..119](0.16Å),[120..135](0.34Å)*, [136..298](0.46Å)— No hinge detected —[1..134], [135..298]

10

TABLE IIIR ESULTS OF HINGE DETECTION (2/2). F RAGMENTS WHICH END NEAR AT THE ANNOTATED HINGE POSITIONS ARE MARKED WITH ‘*’.

Sets

ENL

GB

LF

LB

RB

TC

Methods
k=1
k=2
k=3
Our
results k = 4

RMSDh(k)1.1942 Å
1.0680 Å
0.9053 Å

k=5

0.6612 Å

FlexProt
Hinge Atlas
k=1†k = 2
k=3
Ourresults k = 4––
3.7358 Å
0.9282 Å
0.8057 Å

k=5

0.5381 Å

FlexProt
Hinge Atlas
k=1†k = 2
k=3
Ourresults k = 4––
3.8646 Å
1.1503 Å
0.9290 Å

k=5

0.7130 Å

FlexProt
Hinge Atlas
k=1†k = 2
k=3
Ourresults k = 4––
3.1264 Å
0.4734 Å
0.4234 Å

k=5

0.3469 Å

FlexProt
Hinge Atlas
k=1†k = 2
k=3
Ourresults k = 4––
1.9967 Å
0.5462 Å
0.4505 Å

k=50.3640 Å

FlexProt
Hinge Atlas
k=1
k=2†k = 3
Our
results k = 4––
3.1267 Å
1.6408 Å
1.2040 Å

k=5

0.9042 Å

FlexProt
Hinge Atlas

0.7724 Å

0.6350 Å

0.7880 Å

0.3858 Å

0.3950 Å

1.0665 Å

––Fragments divided by hinges[1..136](1.52Å), [137..436](1.01Å)[1..41](2.03Å), [42..141](0.47Å), [142..436](1.02Å)[1..36](0.29Å), [37..41](2.27Å), [42..141](0.47Å), [142..436](1.02Å)[1..36](0.29Å), [37..41](2.27Å), [42..152](0.47Å)*, [153..329](1.03Å),[330..436](0.40Å)[1..36](0.29Å), [37..41](2.27Å), [42..152](0.47Å)*, [153..220](1.18Å),[221..340](0.49Å), [341..436](0.37Å)— No hinge detected —[1..149], [150..317], [318..436][1..85](0.56Å)*, [86..220](4.75Å)[1..84](0.47Å)*, [85..178](1.28Å)*, [179..220](0.62Å)[1..85](0.56Å)*, [86..105](2.01Å), [106..178](0.52Å)*, [179..220](0.62Å)[1..84](0.47Å)*, [85..97](0.50Å), [98..105](1.98Å), [106..178](0.52Å)*,[179..220](0.62Å)[1..84](0.47Å)*, [85..98](0.77Å), [99..101](0.25Å), [102..106](0.55Å),[107..178](0.51Å)*, [179..220](0.62Å)[5..87]*, [88..180], [181..220][1..85], [86..176], [177..220][1..248](6.23Å), [249..691](1.26Å)[1..91](1.45Å)*, [92..250](0.52Å)*, [251..691](1.24Å)[1..91](1.45Å)*, [92..250](0.52Å)*, [251..332](0.48Å), [333..691](0.98Å)[1..3](0.315Å), [4..91](0.52Å)*, [92..250](0.52Å)*, [251..332](0.48Å),[333..691](0.98Å)[1..3](0.31Å), [4..91](0.52Å)*, [92..250](0.52Å)*, [251..417](1.07Å),[418..422](1.62Å), [423..691](0.54Å)[1..84], [85..244], [245..691][1..90], [91..250], [251..691][1..91](0.39Å)*, [92..238](3.97Å)[1..90](0.32Å)*, [91..191](0.63Å)*, [192..238](0.31Å)[1..90](0.32Å)*, [91..161](0.52Å), [162..191](0.57Å)*, [192..238](0.31Å)[1..90](0.32Å)*, [91..158](0.50Å), [159..182](0.36Å), [183..191](0.35Å)*,[192..238](0.31Å)[1..90](0.32Å)*, [91..112](0.47Å), [113..158](0.35Å), [159..182](0.36Å),[183..191](0.35Å)*, [192..238](0.31Å)[1..83], [84..176], [177..238][1..90], [91..192], [193..238][1..103](0.52Å)*, [104..271](2.50Å)[1..102](0.50Å)*, [103..234](0.41Å)*, [235..271](0.96Å)[1..102](0.50Å)*, [103..233](0.40Å)*, [234..262](0.42Å), [263..271](0.61Å)[1..34](0.29Å), [35..102](0.38Å)*, [103..233](0.40Å)*, [234..262](0.42Å),[263..271](0.61Å)[1..34](0.29Å), [35..102](0.38Å)*, [103..152](0.30Å), [153..234](0.36Å)*,[235..262](0.42Å), [263..271](0.61Å)[1..100]*, [101..271][1..103], [104..235], [236..265][1..58](3.98Å), [59..155](2.50Å)[1..34](0.97Å)*, [35..70](1.87Å), [71..155](1.75Å)[1..36](1.22Å)*, [37..66](1.30Å), [67..107](1.10Å), [108..155](1.22Å)[1..36](1.22Å)*, [37..61](0.88Å)*, [62..69](0.69Å), [70..104](0.78Å)*,[105..155](1.23Å)[1..36](1.22Å)*, [37..61](0.88Å)*, [62..69](0.69Å), [70..104](0.78Å)*,[105..135](0.93Å), [136..155](0.27Å)[1..34]*, [35..66], [67..155][1..35], [36..62], [63..101], [102..155]