Geometric Suﬃx Tree: A New Index Structure
for Protein 3-D Structures
Tetsuo Shibuya
Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan
tshibuya@hgc.jp

Abstract. Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate query
data structures for such 3-D structures are highly desired for research on
proteins. This paper proposes a new data structure for indexing protein
3-D structures. For strings, there are many eﬃcient indexing structures
such as suﬃx trees, but it has been considered very diﬃcult to design such
sophisticated data structures against 3-D structures like proteins. Our index structure is based on the suﬃx trees and is called the geometric suﬃx
tree. By using the geometric suﬃx tree for a set of protein structures, we
can search for all of their substructures whose RMSDs (root mean squaredeviations) or URMSDs (unit-vector root mean square deviations) to agiven query 3-D structure are not larger than a given bound. Though
there are O(N 2 ) substructures, our data structure requires only O(N )space where N is the sum of lengths of the set of proteins. We proposean O(N 2 ) construction algorithm for it, while a naive algorithm would
require O(N 3 ) time to construct it. Moreover we propose an eﬃcient
search algorithm. We also show computational experiments to demonstrate the practicality of our data structure. The experiments show thatthe construction time of the geometric suﬃx tree is practically almost
linear to the size of the database, when applied to a protein structure
database.

1

Introduction

Analyzing 3-D structures of proteins is very important in molecular biology andmore and more protein structures are solved today with the aid of state-of-theart technologies such as nuclear magnetic resonance (NMR) techniques, as seenin the increasing number of PDB [4] entries: 35,813 on March 28, 2006. It is said
that structurally similar proteins tend to have similar functions even if theiramino acid sequences are not similar to each other. Thus it is very important toﬁnd proteins with similar structures (even in part) from the growing database
to analyze protein functions.
Structure similarity search methods for protein structure databases can beclassiﬁed into two types. One is by comparing each database entry with thequery. There are many comparison algorithms for protein structures [10], andthe results could be very accurate, but it will require enormous amount of time
M. Lewenstein and G. Valiente (Eds.): CPM 2006, LNCS 4009, pp. 84–93, 2006.
c Springer-Verlag Berlin Heidelberg 2006


Geometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures85

to apply against very large databases. The other approach is by indexing withsome important features of structures [1, 3, 6, 5, 8, 12]. In ordinary, these methods can search queries more eﬃciently, but with less accuracy than the pairwise comparison-based methods. The accuracy of comparison of two protein
structures is often measured by RMSD (root mean square deviation) [2, 9, 17]or sometimes by URSMD (unit-vector root mean square deviation) [7, 15]; seesection 2.1 for more details. But it has been considered too diﬃcult to designindexing structures that strictly consider the RMSD or the URMSD.
In this paper, we propose a new data structure called the geometric suﬃx
tree that succeeds in ﬁnding all the substructures whose RMSD or URMSD toa query is not larger than some given bound. As the name implies, our data
structure is very similar to the famous suﬃx tree for character strings: Theedges in the ordinary suﬃx tree represent substrings of texts, while the edges in
the geometric suﬃx tree represent 3-D substructures of protein 3-D structures.
The geometric suﬃx tree can be stored in O(N ) space where N is the sum of
the lengths of the proteins in the database. We propose an O(N 2 ) construction
algorithm for it, though it takes O(N 3 ) time if we construct the data structure
naively. Furthermore, the experiments will show that the construction time of
the geometric suﬃx tree is almost linear to the size of the database in practice,when applied to a protein structure database. Moreover, we propose an eﬃcient
search algorithm for substructure queries. This data structure is also useful forﬁnding structural motifs, clustering substructures, and so on.
Organization of this paper is as follows. In section 2, we explain related work
as preliminaries. In section 3, we describe deﬁnitions of two data structures:the geometric trie and the geometric suﬃx tree, where the geometric trie is thebasis for the geometric suﬃx tree. In sections 4 and 5, we explain algorithms forconstructing the data structure and algorithms for searching queries. In section 6,
we demonstrate experimental results. In section 7, we conclude our results.

2

Related Work

2.1

RMSD and URMSD

A protein is a chain of amino acids. Each amino acid has one unique carbon atom
named Cα , and we often use the coordinates of the Cα atom as the representative
position of the amino acid. The set of Cα atom positions of all the amino acids ina protein is called the backbone of the protein, and is often used to ease protein
structure analysis in previous work. The backbone is topologically linear, but it
forms a geometrically very complex structure in the 3-D space. In this paper, weconsider the backbone as the target to index.
The most popular and basic measure to determine geometric similarity between two sets of points like the positions of backbone atoms is the RMSD
(root mean square deviation) [2, 9, 17], if we know which atom in one structure
corresponds to which atom in the other. The measure describes the similarityof two structures when one of the point sets is rotated and translated reasonably. Let the two sets of points to be compared be P = {p1 , p2 , . . . , pn } and86

T. Shibuya

Q = {q 1 , q 2 , . . . , q n }, where pi and q j are coordinates in the 3-D space, and we
considerpi corresponds to q i for each i. The RMSD is the minimum value ofn{( i=1 pi − (R · q i + v)2 )/n}1/2 over possible rotation matrices R and translation vectors v, where  ·  denotes the 
norm. Let R̂(P, Q) and v̂(P, Q) be Rnand v that minimizes the value. We call i=1 pi − (R̂(P, Q) · q i + v̂(P, Q))2
the MSSD (minimum sum squared distance) of P and Q.
It is known that v̂(P, Q) = ni=1 (pi − R̂(P, Q) · q i )/n, i.e., the distance isminimized when the centroids of the two point sets are translated to the same
point. Hence, if both of the point sets are translated so that their centroids
are located at the origin of the coordinates, the RMSD/MSSD
n problem is reduced to a problem of ﬁnding R that minimizes f (R) = i=1 pi − R · q i 2 .
We can ﬁnd R̂(P, Q) in linear time
singular value decomposition
n by using
t
(SVD)
[2,
17]
as
follows.
Let
H
=
p
·
q
.
Then
f (R) can be described as
i
i=1 i
n
t
t
(p
p
+
q
q
)−trace(R·H),
andtrace(RH)ismaximized
when R = V U T ,
i i
i i
i=1
where U ΛV is the SVD of H. Hence R̂(P, Q) can be obtained in constant timefrom H (see [13] for SVD algorithms). 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 cases in this paper. In this way, we can compute the
RMSD/MSSD values in O(n) time.
The URMSD (unit-vector root mean square deviation) [7, 15] is a variation of
the RMSD. The RMSD is sometimes inﬂuenced badly by very distant pairs of
points, andthe URMSD is designed to avoid such inﬂuence. It is the minimum
n−1value of {( i=1 pi − R · q i 2 )/(n − 1)}1/2 over possible rotation matrices R,
where pi = (pi+1 − pi )/pi+1 − pi  and q i = (q i+1 − q i )/qi+1 − q i . Let
n−1Ř(P, Q) be R that minimizes the value. We call i=1 pi − Ř(P, Q) · q i 2 theUMSSD (unit-vector minimum sum squared distance). The URMSD/UMSSD
can be computed
n with the same strategy in O(n) time, i.e., by computing the
SVD of H  = i=1 pi · (q i )t .
2.2

Suﬃx Trees

The suﬃx tree [11, 14, 16, 19, 20] of a string S ∈ Σ n is the compacted trie of/ Σ. This data
all the suﬃxes of S + = S$ where $ is a character such that $ ∈structure can be stored in O(n) space and moreover is known to be buildablein O(n) time. Each leaf represents a suﬃx of the string S + , and each node
represents some substring. This data structure is very useful for various problems
in sequence pattern matching. Using it, we can query a substring of length m inO(m) time, we can ﬁnd frequently appearing substrings in a given sequence inlinear time, we can ﬁnd a common substring of many sequences in linear time,and so on [14].
Not much work has been done for applying this data structure to biomolecular
structures. The PSIST [12] is the only index data structure for protein structures
based on the suﬃx trees as far as we know. It converts local features of the aminoacid chain (i.e., some feature vectors computed from only several adjacent atoms)
into some alphabets and constructs suﬃx trees over the converted alphabet sequences, without considering global similarity measures like the RMSD or theGeometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures

87

URMSD at all. For RNA (secondary) structures, the s-suﬃx tree [18], a generalization of the suﬃx tree, can be used for mining some interesting RNA structuresfrom sequence databases, but it cannot be applied to protein 3-D structures.

3

Geometric Suﬃx Tree Data Structure

In this section, we describe the deﬁnition of the geometric suﬃx tree. Before
deﬁning the geometric suﬃx tree, we deﬁne a data structure called the geometrictrie for a set of protein structures.
Consider a set of n protein structures represented by the sequence of their Cαatom coordinates. Let Wi be the i-th structure, where the 3-D coordinates of the(i)j-th Cα atom is denoted as w j , and let i be the length of Wi (i.e., number of
(i)

(i)

(i)

Cα atoms). Let Wi [j..k] denote {wj , wj+1 , . . . , wk }, which means a structure
formed by the (k − j + 1) atoms from the j-th atom to the k-th atom in Wi . We
call it a substructure of Wi . Moreover, we call Wi [1..j] a preﬁx substructure of
Wi . Conversely, Wi [j..i ] is called a suﬃx substructure. From now on, we deﬁne
two versions of the geometric trie: one based on the RMSD/MSSD (which we callthe RMSD Geometric trie (RGT)) and the other based on the URMSD/UMSSD(which we call the URMSD geometric trie (UGT)). The geometric trie for the setof protein structures is deﬁned as a rooted tree data structure that has following
features:
1. All the internal nodes (nodes other than the leaves) except for the root havemore than one child, while the root has only one child. (It corresponds tothe fact that a structure with only one atom is always the same structure.)
The trie has n leaves, each of which corresponds to one protein structure,and no two leaves correspond to the same structure. Let leaf (i) denote theleaf that corresponds to Wi .
2. All the internal edges (i.e., edges that end at internal nodes) and someexternal edges (i.e., edges that end at leaves) correspond to a substructure ofsome protein. If the corresponding substructure of edge e is P (e) = Wi [j..k],
we represent it with only three values: i, j, and length(e) = k − j + 1. Let
length(e) = 0 if e is an external edge without a corresponding substructure.
We call the value length(e) the edge length of e. Let the depth(v) be thesum of all the edge lengths on the path from the root to v, which we call thedepth of v.
3. Add to the three values that represent its corresponding substructure, eachedge with a corresponding substructure has information of a rotation matrix
R(e) and a translation vector v(e). R(e) and v(e) must satisfy the conditionin the items 4 and 5.
4. Let S(e) be a 3-D structure obtained by rotating P (e) with R(e) and translating it with v(e) after that. We call S(e) the ‘edge structure’ of e. Notethat S(e) (not P (e)) corresponds to the substring represented by an edge inan ordinary suﬃx tree for alphabet strings. The ‘node structure’ S(x) for anode x is deﬁned as a structure that can be obtained by concatenating ‘edge

88

T. Shibuya

structures’ of the edges on the path from the root to the node x. For any
leaf v = leaf (i) and its node structure S(v), the MSSD (in case of RGTs, orthe UMSSD in case of UGTs) between any preﬁx substructure of S(v) andthe preﬁx substructure of Wi of the same length must not be larger thansome given ﬁxed bound b. (Note that b is unrelated to the RMSD/URMSD
bound d used in the next section for searching structures.)5. For an edge e = (v, w) with some corresponding substructure P (e), the‘branching structure’ str(e) is deﬁned as a structure that is obtained byadding the coordinates of the ﬁrst atom of S(e) (i.e., S(e)[1]) after thecoordinates sequence S(v). For any internal node v with more than one
outgoing edge with corresponding substructures, the MSSD (for RGTs, orthe UMSSD for UGTs) between str(e1 ) and str(e2 ) must be larger than b,
where e1 and e2 are arbitrary two of the edges.

p2
p4
p6
p8
p9

p1

p3

q4

p5
p7

q2

MSSD b

p11
p10

q1
q3
q6

q5

q8
q7

q10

P[1..7],R1, v1q9
q11

P[8..11],
R1, v1

Q[8..11],
R2, v2

Fig. 1. A geometric trie for two protein 3-D structures

As there are only O(n) nodes/edges in the trie and we need only O(1) memory for each edge/node, the total memory space to store the geometric trie isonly O(n). Note that the data structure is not unique for a ﬁxed set of protein
structures. Figure 1 shows an example of the geometric trie constructed for two
structures P and Q. In the ﬁgure, we consider the MSSD of P [1..7] and Q[1..7] is
not larger than b, while the MSSD between P [1..8] and Q[1..8] is larger than b.
Now we can deﬁne the geometric suﬃx tree: The geometric suﬃx tree for a setof proteins is the geometric trie for all the suﬃx substructures of all the proteinsin the set. It is easy to see that we need O(N ) space to store the geometric suﬃxtree, where N is the sum of the lengths of the proteins.

4

Constructing Geometric Suﬃx Trees

In this section, we describe how to construct the geometric tries and the geometric suﬃx trees. Given a set of n protein structures Wi and some given MSSD
(for RGTs or UMSSD for UGTs) bound b, we can construct the geometric trie
by adding structures one by one as follows:Geometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures

89

Algorithm 1. At ﬁrst, construct a tree with only the root node. For each protein
structure Wi , set the root node to v and do the following.
1. From among a set of v’s outgoing edges with some corresponding substructures, ﬁnd an edge e such that the MSSD (for RGTs, or the UMSSD for
UGTs) between Wi [1..depth(v) + 1] and str(e) is smaller than b. If there
is more than one such edge, choose an arbitrary one (or preferably the one
with the smallest MSSD (or UMSSD)). If no such edge exists, go to step 2.
Otherwise go to step 3.
2. Add a new outgoing edge e = (v, w) to v, and let the new leaf w correspondto Wi . Let P (e ) be Wi [depth(v) + 1..i ]. If v is the root, let R(e ) be theidentity matrix and let v(e ) be a zero vector. Otherwise, in case of RGTs, letR(e ) be R̂(S(v), Wi [1..depth(v)]), and let v(e ) be v̂(S(v), Wi [1..depth(v)]).
In case of UGTs, let R(e ) be Ř(S(v), Wi [1..depth(v)]), and let v(e ) be(S(v)[depth(v)] − R(e ) · Wi [depth(v)]). Notice that, in both cases, R(e ) andv(e ) represents alignment between S(v) and Wi [1..depth(v)]. Then stop.
3. Let w be the node where the edge e ends. Find the longest preﬁx substructures of S(w) and Wi whose MSSD (for RGTs, or UMSSD for UGTs) is
not larger than b, and let the length be . If  < depth(w) go to step 4. If
 = depth(w) and  < i , set w to v and go to step 1. Otherwise, add a new
outgoing edge (w, u) with no corresponding substructure, and let the newleaf u correspond to the structure Wi . Then stop.
4. Insert a new node u between v and w. Let e1 = (v, u) and let e2 = (u, w). Let
P (e1 ) be the preﬁx substructure of P (e) of length (−depth(v)), and P (e2 ) be
the suﬃx substructure of P (e) of length (depth(w) − ). Let R(e1 ) and R(e2 )be the same matrix as R(e), and v(e1 ) and v(e2 ) be the same vector as v(e).
Add a new outgoing edge e = (u, x) to u, and let the new leaf x correspondto the structure Wi . If  = i , let e have no corresponding substructure.
Otherwise, let the corresponding substructure P (e ) be Wi [ + 1..i]. In caseof RGTs, let R(e ) be R̂(S(u), Wi [1..]) and let v(e ) be v̂(S(u), Wi [1..]).
In case of UGTs, let R(e ) be Ř(S(u), Wi [1..]) and let v(e ) be (S(u)[] −R(e ) · Wi []). Then stop.
With the same algorithm, we can construct the geometric suﬃx tree: Justconsider that Wi is the i-th suﬃx substructure.
Recall that it takes O() time to compute the MSSD or the UMSSD (and therotation matrix and the translation vector related to it) between two structuresof size . Thus, if we execute the algorithm naively, we would need O((i + n) · i )branches on the pathtime to add Wi to the tree, because there are at most nnfrom the root node to some leaf. Accordingly, we need O( i {(i + n) · i }) time
for constructing the geometric trie. It means that the above algorithm requiresO(N 3 ) time to construct the geometric suﬃx tree, where N is the sum of all thestructure lengths. From now on we present how to reduce it to O(N 2 ).
We reduce the computation time by proposing an incremental MSSD/UMSSD
computation technique. Recall that the MSSD of two protein structures
P [1..j] and Q[1..j] can be obtained by computing the SVD of H =90

T. Shibuyajt
i=1 (pi − cP ) · (q i − cQ ) where cP

and cQ are the centroids of P and Q. Hjj
can be computed in constant time if we are given fP (j) = i pi , fQ (j) = i q i ,and g(j) = ji pi · q ti , as H = g(j) − {fP (j) · (fQ (j))t }/j. Add to these values,
jj
we need hP (j) = i=1 pti pi and hQ (j) = i=1 q ti q i to compute the MSSD or
RMSD values in constant time. Notice that all of these can be computed incrementally in constant time from fP (j − 1), fQ (j − 1), g(j − 1), hP (j − 1), andhQ (j−1). It means that we can add the structure Wi to the tree in O(i +n) time,and accordingly we can construct the RGT in O(N + n2 ) time. In conclusion,
we can construct the RMSD-based geometric suﬃx tree in O(N 2 ) time.
Similarly, we can compute the UMSSD of two protein structures P [1..j]
j

 t

and Q[1..j] in constant time if we are given g  (j) =i=1 pi · (q i ) , hP (j) =

j
j
 t 

 t 
i=1 (pi ) pi , and hQ (j) =i=1 (q i ) q i . We can easily see that these can also
be computed from g (j − 1), hP (j − 1) and hQ (j − 1) in constant time. Therefore we conclude that the UGTs and the URMSD-based geometric suﬃx trees
can be constructed in the same time bound as the RGTs and the RMSD-based
geometric suﬃx trees: We can construct the UGTs in O(N + n2 ) time, and the
URMSD-based geometric suﬃx trees in O(N 2 ) time.

5

Geometric Suﬃx Tree Applications

There are two important features on the RMSD/MSSD (or URMSD/UMSSD)
measures. One is that the MSSD (or UMSSD) of two structures P and Q (ofthe same length) is always larger than or equal to that of P  and Q , where P and Q are any same-length preﬁx substructures of P and Q. The other is that
there is a triangle inequality c ≤ a + b where a is the RMSD (URMSD) between
P and Q, b is that between Q and R, and c is that between R and P , for any
set of three structures P , Q, and R of same lengths.
Using these features, all maximal substructures whose RMSD (or URMSD)
to a query Q[1..m] is within some bound d can be computed eﬃciently as follows. Let ‘representative structure’ mean any preﬁx substructure of the ‘node
structure’ of any node in the geometric suﬃx tree. First, we ﬁnd all the maximal
representative substructures whose RMSD (or URMSD) to the query Q is within
b/m+d by just doing a depth-ﬁrst or breadth-ﬁrst search from the root, whereb is the MSSD (or UMSSD) bound used for constructing the geometric suﬃx
tree. Let E be the set of edges to which the collected representative substructures correspond. After that, ﬁnd all the leaves that are descendants of the edges
in E. As the suﬃxes that correspond to the collected leaves are candidates of
the answer substructures (and there are no candidates elsewhere), check their
RMSDs (or URMSDs) one by one.
Ordinary suﬃx trees have tremendous number of applications in string patternmatching [14]. Like them, applications of the geometric suﬃx trees are not limited to the database search. A long representative structure whose correspondingedge has many descendants is a repeated structure in a protein structure, which
could have some meaning. By constructing the geometric suﬃx tree for several
functionally-related protein structures, we could ﬁnd structural motifs. We couldGeometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures

91

further use this fundamental data structure for designing more complicated combinatorial pattern matching algorithms on protein structures, such as structuralalignment algorithms, clustering/classiﬁcation algorithms and functional prediction algorithms.

6

Experimental Results

In this section, we demonstrate the performance of the geometric suﬃx trees
through experiments on a Sun Fire 15K super computer with 288 GB memory
and 96 UltraSPARC III Cu CPUs running at 1.2GHz. Note that we used only
one CPU for each experiment. As a data for experiments, we used a set of 228
myoglobin or myoglobin-related PDB data ﬁles containing 275 protein structures.
The total number of amino acids in the protein set is 41,719.
Table 1 shows the computation time for constructing the RMSD-based geometric suﬃx trees against databases of diﬀerent sizes, setting 400Å2 to the MSSD
bound. In the experiment (1), we used all the 275 proteins to index. In the experiments (2)-(5), we used diﬀerent subsets of them. The ‘#sequence(#a.a.)’column shows the numbers of sequences and amino acids contained in the protein sets. The ‘Time’ column shows the computation time, while the ‘GST Size’
column shows the numbers of nodes in the constructed geometric suﬃx trees.
According to the table, the computation time is almost linear to the size of thedatabases, though the theoretical time bound is O(N 2 ). It is reasonable as there
should be some reasonable upper bound on protein lengths.
Next, we examined the query speed on the RMSD-based geometric suﬃx
trees with diﬀerent MSSD bounds. Table 2 shows the results, where ‘b = . . .’denotes the MSSD bound in Å2 . We used two protein substructures of the samelength as queries: In experiment (a), we used as a query a substructure from
Table 1. Time for constructing the geometric suﬃx trees (b = 400Å2 )Database#sequence (#a.a.) Time (sec) GST Size
(1) Entire database
275(41,719)
53.15
57,241
198(30,061)
36.37
41778
(2) Subset A
111(16,983)
17.68
25,942(3) Subset B
54(8,267)
7.91
13,050(4) Subset C
20(3,069)2.894,855(5) Subset D

Table 2. Query time (sec) on the geometric suﬃx trees with various MSSD bounds
Queriesb = 1 b = 100 b = 400 b = 900 b = 1600 b = 2500 #found
d
=
1.0
Å
1.63 0.56
0.39
0.43
0.60
0.87
19
(a)
5.66
6.55
6.63
6.63
217
d = 5.0Å 11.70 5.08
0.48
0.33
0.19
0.21
0
(b) d = 1.0Å 1.63 0.73
d = 5.0Å 16.13 7.83
7.93
8.00
7.58
7.20
0

92

T. Shibuya

the 20th amino acid to the 69th amino acid of a myoglobin’s structure obtained
from the PDB entry named 103M. In experiment (b), we used a protein thatis unrelated to myoglobins: A substructure from the 20th amino acid to the69th amino acid of a rhodopsin’s structure obtained from the PDB entry named
1F88. In both experiments, we examined query time by setting two diﬀerent
RMSD bounds: d = 1.0Å and d = 5.0Å. In the table, the ‘#found’ column
shows the numbers of found substructures similar to the query. According to theexperiments, the query is very fast when the RMSD bound for the query is small
in both experiments. Note that we can observe similar phenomenon on ordinary
suﬃx trees: It is known that the inexact matching on suﬃx trees is (not) eﬃcientwhen there is (not) a small edit distance limit.

7

Concluding Remarks

We proposed a new data structure called the geometric suﬃx tree for indexing
the protein 3-D structures. The data structure can be stored in O(N ) space where
N is the database size, and we presented an O(N 2 ) construction algorithm for it.
Moreover, we showed through experiments that we can build the data structure
in quasi-linear time in practice. We also showed that we can search for queries
very eﬃciently with the geometric suﬃx tree.
It is an open problem whether we can improve the theoretical time boundfor building the geometric suﬃx tree. We are now working on utilizing this data
structure for further combinatorial matching problems and machine learning
problems on protein structures. We suppose this work is just the beginning.

Acknowledgements
The author would like to thank Prof. Tatsuya Akutsu for fruitful discussions
on protein comparison algorithms. All the computational experiments in thisresearch were done on the Super Computer System, Human Genome Center,
Institute of Medical Science, University of Tokyo.

References
1. T. Akutsu, K. Onizuka, and M. Ishikawa. New hashing techniques and their application to a protein database system. Proc. Hawaii Int. Conf. System Sciences(HICSS-28), Vol. 5, pp. 197-206, 1995.
2. K. S. Arun, T. S. Huang, and S. D. Blostein. Least-squares ﬁtting of two 3-D pointsets. IEEE Trans Pattern Anal. Machine Intell., Vol. 9, pp. 698-700, 1987.
3. Z. Aung, W. Fu and K. Tan. An eﬃcient index-based protein structure databasesearching method. Proc. Intl. Conf. on Database Systems for Advanced Applications, pp. 311-318, 2003.
4. H. M. Berman, J. Westbrook, Z. Feng, et al. The protein data bank. Nucl. Acids
Res., Vol. 28, pp. 235-242, 2000.

Geometric Suﬃx Tree: A New Index Structure for Protein 3-D Structures

93

5. O. Çamoğlu, T. Kahveci and A. Singh. Towards index-based similarity search forprotein structure databases. IEEE Computer Society Bioinformatics Conference,
pp. 148-158, 2003.
6. T. Can and Y. Wang. CTSS: a robust and eﬃcient method for protein structurealignment based on local geometrical and biological features. IEEE Computer Society Bioinformatics Conference, pp. 169-179, 2003.
7. L. P. Chew, D. Huttenlocher, K. Kedem and J. Kleinberg. Fast detection of common
geometric substructure in proteins. J. Comput. Biol., Vol. 6, No. 3, pp. 313-325,
1999.
8. I. Choi, J. Kwon and S. Kim. Local feature frequency proﬁle: A method to measure
structural similarity in proteins. Proc. Natl. Acad. Sci., Vol. 101, No. 11, pp. 37973802, 2004.
9. D. W. Eggert, A. Lorusso and R. B. Fisher. Estimating 3-D rigid body transformations: a comparison of four major algorithms. Machine Vision and Applications,Vol. 9, pp. 272-290, 1997.
10. I. Eidhammer, I. Jonassen, and W. R. Taylor. Structure Comparison and Structure
Patterns. J. Computational Biology, Vol. 7, No. 5, pp. 685-716, 2000.
11. M. Farach. Optimal suﬃx tree construction with large alphabets. Proc. 38th IEEE
Symp. Foundations of Computer Science, pp. 137-143, 1997.
12. F. Gao and M. J. Zaki. PSIST: Indexing Protein Structures using Suﬃx Trees.
Proc. IEEE Computational Systems Bioinformatics Conference (CSB), pp. 212222, 2005.
13. G. H. Golub and C. F. Van Loan. Matrix Computation. 3rd eds., John Hopkins
University Press, 1996.
14. D. Gusﬁeld. Algorithms on strings, trees, and sequences: computer science andcomputational biology, Cambridge University Press, 1997.
15. K. Kedem, P. Chew and R. Elber. Unit-vector RMS (URMS) as a tool to analyze
molecular dynamics trajectories. Proteins: Struct. Funct. Genet., Vol. 38, pp. 1-12,
1999.
16. E. M. McCreight. A space-economical suﬃx tree construction algorithm. J. ACM.,
Vol. 23, pp. 262-272, 1976.
17. J. T. Schwartz and M. Sharir. Identiﬁcation of partially obscured objects in two
and three dimensions by matching noisy characteristic curves. Intl. J. of Robotics
Res., Vol. 6, pp. 29-44, 1987.
18. T. Shibuya. Generalization of a suﬃx tree for RNA structural pattern matching.
Algorithmica, Vol. 39, No. 1, pp. 1-19, 2004.
19. E. Ukkonen. On-line construction of suﬃx-trees. Algorithmica, Vol. 14, pp. 249-260,
1995.
20. P. Weiner. Linear pattern matching algorithms. Proc. 14th Symposium on Switching and Automata Theory, pp. 1-11, 1973.