Multiple graph regularized protein domain ranking

arXiv:1208.3779v3 [cs.LG] 21 Apr 2013

Jim Jing-Yan Wang1 , Halima Bensmail2 and Xin Gao∗1,3
1 Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology
(KAUST), Thuwal, 23955-6900, Saudi Arabia
2 Qatar Computing Research Institute, Doha 5825, Qatar
3 Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900,
Saudi Arabia

Email: Jim Jing-Yan Wang - jimjywang@gmail.com; Halima Bensmail - hbensmail@qf.org.qa; Xin Gao - xin.gao@kaust.edu.sa;
∗ Corresponding

author

Abstract
Background Protein domain ranking is a fundamental task in structural biology. Most protein domain ranking
methods rely on the pairwise comparison of protein domains while neglecting the global manifold structure
of the protein domain database. Recently, graph regularized ranking that exploits the global structure of
the graph defined by the pairwise similarities has been proposed. However, the existing graph regularized
ranking methods are very sensitive to the choice of the graph model and parameters, and this remains a
difficult problem for most of the protein domain ranking methods.
Results To tackle this problem, we have developed the Multiple Graph regularized Ranking algorithm, MultiGRank. Instead of using a single graph to regularize the ranking scores, MultiG-Rank approximates the
intrinsic manifold of protein domain distribution by combining multiple initial graphs for the regularization.
Graph weights are learned with ranking scores jointly and automatically, by alternately minimizing an objective function in an iterative algorithm. Experimental results on a subset of the ASTRAL SCOP protein
domain database demonstrate that MultiG-Rank achieves a better ranking performance than single graph
regularized ranking methods and pairwise similarity based ranking methods.
Conclusion The problem of graph model and parameter selection in graph regularized protein domain ranking
can be solved effectively by combining multiple graphs. This aspect of generalization introduces a new
frontier in applying multiple graphs to solving protein domain ranking applications.

1

Background
Proteins contain one or more domains each of which could have evolved independently from the rest of the
protein structure and which could have unique functions [1, 2]. Because of molecular evolution, proteins
with similar sequences often share similar folds and structures. Retrieving and ranking protein domains that
are similar to a query protein domain from a protein domain database are critical tasks for the analysis of
protein structure, function, and evolution [3–5]. The similar protein domains that are classified by a ranking
system may help researchers infer the functional properties of a query domain from the functions of the
returned protein domains.
The output of a ranking procedure is usually a list of database protein domains that are ranked in
descending order according to a measure of their similarity to the query domain. The choice of a similarity
measure largely defines the performance of a ranking system as argued previously [6]. A large number of
algorithms for computing similarity as a ranking score have been developed:
Pairwise protein domain comparison algorithms compute the similarity between a pair of protein domains either by protein domain structure alignment or by comparing protein domain features. Protein
structure alignment based methods compare protein domain structures at the level of residues and
sometime even atoms, to detect structural similarities with high sensitivity and accuracy. For example, Carpentier et al. proposed YAKUSA [7] which compares protein structures using one-dimensional
characterizations based on protein backbone internal angles, while Jung and Lee proposed SHEBA [8]
for structural database scanning based on environmental profiles. Protein domain feature based methods extract structural features from protein domains and compute their similarity using a similarity
or distance function. For example, Zhang et al. used the 32-D tableau feature vector in a comparison
procedure called IR tableau [3], while Lee and Lee introduced a measure called WDAC (Weighted
Domain Architecture Comparison) that is used in the protein domain comparison context [9]. Both
these methods use cosine similarity for comparison purposes.
Graph-based similarity learning algorithms use the traditional protein domain comparison methods
mentioned above that focus on detecting pairwise sequence alignments while neglecting all other protein
domains in the database and their distributions. To tackle this problem, a graph-based transductive
similarity learning algorithm has been proposed [6, 10]. Instead of computing pairwise similarities for
protein domains, graph-based methods take advantage of the graph formed by the existing protein
domains. By propagating similarity measures between the query protein domain and the database
2

protein domains via graph transduction (GT), a better metric for ranking database protein domains
can be learned.
The main component of graph-based ranking is the construction of a graph as the estimation of intrinsic
manifold of the database. As argued by Cai et al. [11], there are many ways to define different graphs with
different models and parameters. However, up to now, there are, in general, no explicit rules for choice of
graph models and parameters. In [6], the graph parameters were determined by a grid-search of different
pairs of parameters. In [11], several graph models were considered for graph regularization, and exhaustive
experiments were carried out for the selection of a graph model and its parameters . However, these kinds of
grid-search strategies select parameters from discrete values in the parameter space, and thus lack the ability
to approximate an optimal solution. At the same time, cross-validation [12, 13] can be used for parameter
selection, but it does not always scale up very well for many of the graph parameters, and sometimes it
might over-fit the training and validation set while not generalizing well on the query set.
In [14], Geng et al. proposed an ensemble manifold regularization (EMR) framework that combines the
automatic intrinsic manifold approximation and semi-supervised learning (SSL) [15, 16] of a support vector
machine (SVM) [17, 18]. Based on the EMR idea, we attempted to solve the problem of graph model and
parameter selection by fusing multiple graphs to obtain a ranking score learning framework for protein domain
ranking. We first outlined the graph regularized ranking score learning framework by optimizing ranking
score learning with both relevant and graph constraints , and then generalized it to the multiple graph case.
First a pool of initial guesses of the graph Laplacian with different graph models and parameters is computed,
and then they are combined linearly to approximate the intrinsic manifold. The optimal graph model(s)
with optimal parameters is selected by assigning larger weights to them. Meanwhile, ranking score learning
is also restricted to be smooth along the estimated graph. Because the graph weights and ranking scores
are learned jointly, a unified objective function is obtained. The objective function is optimized alternately
and conditionally with respect to multiple graph weights and ranking scores in an iterative algorithm. We
have named our Multiple Graph regularized Ranking method MultiG-Rank. It is composed of an off-line
graph weights learning algorithm and an on-line ranking algorithm.

Methods
Graph model and parameter selection Given a data set of protein domains represented by their tableau 32-D
feature vectors [3] X = {x1 , x2 , · · · , xN }, where xi ∈ R32 is the tableau feature vector of i-th protein domain,

3

xq is the query protein domain, and the others are database protein domains. We define the ranking score
vector as f = [f1 , f2 , ..., fN ]⊤ ∈ RN in which fi is the ranking score of xi to the query domain. The problem
is to rank the protein domains in X in descending order according to their ranking scores and return several
of the top ranked domains as the ranking results so that the returned protein domains are as relevant to
the query as possible. Here we define two types of protein domains: relevant when they belong to the same
SCOP fold type [19], and irrelevant when they do not. We denote the SCOP-fold labels of protein domains
in X as L = {l1 , l2 , ..., lN }, where li is the label of i-th protein domain and lq is the query label. The optimal
ranking scores of relevant protein domains {xi }, li = lq should be larger than the irrelevant ones {xi }, li 6= lq ,
so that the relevant protein domains will be returned to the user.

Graph regularized protein domain ranking
We applied two constraints on the optimal ranking score vector f to learn the optimal ranking scores:
Relevance constraint Because the query protein domain reflects the search intention of the user, f should
be consistent with protein domains that are relevant to the query . We also define a relevance vector
of the protein domain as y = [y1 , y2 , · · · , yN ]⊤ ∈ {1, 0}N where yi = 1, if xi is relevant to the query
and yi = 0 if it is not. Because the type label lq of a query protein domain xq is usually unknown, we
know only that the query is relevant to itself and have no prior knowledge of whether or not others
are relevant; therefore, we can only set yq = 1 while yi , i 6= q is unknown.
To assign different weights to different protein domains in X , we define a diagonal matrix U as Uii = 1
when yi is known, otherwise Uii = 0. To impose the relevant constraint to the learning of f , we aim
to minimize the following objective function:

min Or (f) =
f

N
X

(fi − yi )2 Uii

i=1

(1)

= (f − y)⊤ U (f − y)
Graph constraint f should also be consistent with the local distribution found in the protein domain
database. The local distribution was embedded into a K nearest neighbor graph G = {V, E, W }. For
each protein domain xi , its K nearest neighbors, excluding itself, are denoted by Ni . The node set V
corresponds to N protein domains in X , while E is the edge set, and (i, j) ∈ E if xj ∈ Ni or xi ∈ Nj .
The weight of an edge (i, j) is denoted as Wij which can be computed using different graph definitions
and parameters as described in the next section. The edge weights are further organized in a weight
4

matrix W = [Wij ] ∈ RN ×N , where Wij is the weight of edge (i, j). We expect that if two protein
domains xi and xj are close (i.e.,Wij is big), then fi and fj should also be close. To impose the graph
constraint to the learning of f , we aim to minimize the following objective function:

min Og (f ) =
f

N
1 X
(fi − fj )2 Wij
2 i,j=1

= f⊤ Df − f⊤ W f

(2)

= f⊤ Lf
where D is a diagonal matrix whose entries are Dii =

PN

i=1

Wij and L = D − W is the graph Laplacian

matrix. This is a basic identity in spectral graph theory and it provides some insight into the remarkable
properties of the graph Laplacian.
When the two constraints are combined, the learning of f is based on the minimization of the following
objective function:
min O(f) = Or (f) + αOg (f)
f

= (f − y)⊤ U (f − y) + αf⊤ Lf

(3)

where α is a trade-off parameter of the smoothness penalty. The solution is obtained by setting the derivative
of O(f) with respect to f to zero as f = (U + αL)−1 U y. In this way, information from both the query
protein domain provided by the user and the relationship of all the protein domains in X are used to rank
the protein domains in X . The query information is embedded in y and U , while the protein domain
relationship information is embedded in L. The final ranking results are obtained by balancing the two
sources of information. In this paper, we call this method Graph regularized Ranking (G-Rank).

Multiple graph learning and ranking: MultiG-Rank
Here we describe the multiple graph learning method to directly learn a self-adaptive graph for ranking
regularization The graph is assumed to be a linear combination of multiple predefined graphs (referred to
as base graphs). The graph weights are learned in a supervised way by considering the SCOP fold types of
the protein domains in the database.

Multiple graph regularization
The main component of graph regularization is the construction of a graph. As described previously, there
are many ways to find the neighbors Ni of xi and to define the weight matrix W on the graph [11]. Several
5

of them are as follows:
• Gaussian kernel weighted graph: Ni of xi is found by comparing the squared Euclidean distance
as,

⊤
⊤
||xi − xj ||2 = x⊤
i xi − 2xi xj + xj xj

(4)

and the weighting is computed using a Gaussian kernel as,

Wij =

(

e−

||xi −xj ||2
2σ2

0,

,

if (i, j) ∈ E
else

(5)

where σ is the bandwidth of the kernel.
• Dot-product weighted graph: Ni of xi is found by comparing the squared Euclidean distance and
the weighting is computed as the dot-product as,

Wij =



x⊤
i xj , if (i, j) ∈ E
0,
else

(6)

• Cosine similarity weighted graph: Ni of xi is found by comparing cosine similarity as,

C(xi , xj ) =

x⊤
i xj
||xi ||||xj ||

(7)

and the weighting is also assigned as cosine similarity as,


C(xi , xj ),
Wij =
0,

if (i, j) ∈ E
else

(8)

• Jaccard index weighted graph: Ni of xi is found by comparing the Jaccard index [20] as,

J(xi , xj ) =
and the weighting is assigned as,

T
|xi xj |
S
|xi xj |


J(xi , xj ), if (i, j) ∈ E
Wij =
0,
else

6

(9)

(10)

• Tanimoto coefficient weighted graph: Ni of xi is found by comparing the Tanimoto coefficient as,

T (xi , xj ) =

x⊤
i xj
2
||xi || + ||xj ||2 − x⊤
i xj

(11)

and the weighting is assigned as,

Wij =


T (xi , xj ), if (i, j) ∈ E
0,
else

(12)

With so many possible choices of graphs, the most suitable graph with its parameters for the protein
domain ranking task is often not known in advance; thus, an exhaustive search on a predefined pool of graphs
is necessary. When the size of the pool becomes large, an exhaustive search will be quite time-consuming
and sometimes not possible. Hence, a method for efficiently learning an appropriate graph to make the
performance of the employed graph-based ranking method robust or even improved is crucial for graph
regularized ranking. To tackle this problem we propose a multiple graph regularized ranking framework,
that provides a series of initial guesses of the graph Laplacian and combines them to approximate the intrinsic
manifold in a conditionally optimal way, inspired by a previously reported method [14].
Given a set of M graph candidates {G1 , · · · , GM }, we denote their corresponding candidate graph Laplacians as T = {L1 , · · · , LM }. By assuming that the optimal graph Laplacian lies in the convex hull of the
pre-given graph Laplacian candidates, we constrain the search space of possible graph Laplacians o linear
combination of Lm in T as,

L=

M
X

(13)

µm L m

m=1

where µm is the weight of m-th graph. To avoid any negative contribution, we further constrain
1, µm ≥ 0.

PM

m=1

µm =

To use the information from data distribution approximated by the new composite graph Laplacian L in
(13) for protein domain ranking, we introduce a new multi-graph regularization term. By substituting (13)
into (2), we get the augmented objective function term in an enlarged parameter space as,

min Omultig (f, µ) =
f,µ

s.t.

M
X

µm (f⊤ Lm f)

m=1
M
X

µm = 1, µm ≥ 0.

m=1

where µ = [µ1 , · · · , µM ]⊤ is the graph weight vector.
7

(14)

Off-line supervised multiple graph learning
In the on-line querying procedure, the relevance of query xq to database protein domains is unknown and
thus the optimal graph weights µ cannot be learned in a supervised way. However, all the SCOP-fold labels
of protein domain in the database are known, making the supervised learning of µ in an off-line way possible.
We treat each database protein domain xq ∈ D, q = 1, · · · , N as a query in the off-line learning and all the
items of its relevant vector yq = [y1q , · · · , yN q ]⊤ as known because all the SCOP-fold labels are known for
all the database protein domains as,

yiq =



1 , if li = lq
0
, else

(15)

Therefore, we set U = I N ×N as a N × N identity matrix. The ranking score vector of the q-th database
protein domain is also defined as fq = [y1q , · · · , yN q ]⊤ . Substituting fq , yq and U to (1) and (14) and
combining them, we have the optimization problem for the q-th database protein domain as,

min O(fq , µ) = (fq − yq )⊤ (fq − yq ) + α
fq ,µ

s.t.

M
X

2
µm (f⊤
q Lm fq ) + β||µ||

m=1
M
X

(16)

µm = 1, µm ≥ 0.

m=1

To avoid the parameter µ over-fitting to one single graph, we also introduce the l2 norm regularization term
||µ||2 to the object function. The difference between fq and yq should be noted: fq ∈ {1, 0}N plays the role
of the given ground truth in the supervised learning procedure, while yq ∈ RN is the variable to be solved.
While fq is the ideal solution of yq , it is not always achieved after the learning. Thus, we introduce the first
term in (16)to make yq as similar to fq as possible during the learning procedure.
Object function: Using all protein domains in the database q = 1, . . . , N as queries to learn µ, we
obtain the final objective function of supervised multiple graph weighting and protein domain ranking as,

min O(F, µ) =
F,µ

N
X
q=1

"

⊤

(fq − yq ) (fq − yq ) + α

m=1



= T r (F − Y )⊤ (F − Y ) + α
s.t.

M
X

M
X

M
X

#

µm (f⊤
q Lm f q )

+ β||µ||2

µm T r(F ⊤ Lm F ) + β||µ||2

(17)

m=1

µm = 1, µm ≥ 0.

m=1

where F = [f1 , · · · , fN ] is the ranking score matrix with the q-th column as the ranking score vector of q-th
protein domain, and Y = [y1 , · · · , yN ] is the relevance matrix with the q-th column as the relevance vector
8

of the q-th protein domain.
Optimization: Because direct optimization to (17) is difficult, instead we adopt an iterative, two-step
strategy to alternately optimize F and µ. At each iteration, either F or µ is optimized while the other is
fixed, and then the roles are switched. Iterations are repeated until a maximum number of iterations is
reached.
• Optimizing F : By fixing µ, the analytic solution for (17) can be easily obtained by setting the derivative
of O(F, µ) with respect to F to zero. That is,
M
X
∂O(F, µ)
= 2(F − Y ) + 2α
µm (Lm F ) = 0
∂F
m=1

F = (I + α

M
X

(18)

µm Lm )−1 Y

m=1

• Optimizing µ: By fixing F and removing items irrelevant to µ from (17), the optimization problem
(17) is reduced to,

min α
µ

M
X

µm T r(F ⊤ Lm F ) + β||µ||2

m=1

=α

M
X

µm e m + β

m=1
⊤

M
X

µ2

m=1
⊤

= αe µ + βµ µ
s.t.

M
X

(19)

µm = 1, µm ≥ 0.

m=1

where em = T r(F ⊤ Lm F ) and e = [e1 , · · · , eM ]⊤ . The optimization of (19) with respect to the graph
weight µ can then be solved as a standard quadratic programming (QP) problem [4].
Off-line algorithm: The off-line µ learning algorithm is summarized as Algorithm 1.

On-line ranking regularized by multiple graphs
Given a newly discovered protein domain submitted by a user as query x0 , its SCOP type label l0 will be
unknown and the domain will not be in the database D = {x1 , · · · , xN }. To compute the ranking scores of
xi ∈ D to query x0 , we extend the size of database to N + 1 by adding x0 into the database and then solve
the ranking score vector for x0 which is defined as f = [f0 , · · · , fN ] ∈ RN +1 using (3). The parameters in
(3) are constructed as follows:
9

Algorithm 1 MultiG-Rank: off-line graph weights learning algorithm.
Require: Candidate graph Laplacians set T ;
Require: SCOP type label set of database protein domains L;
Require: Maximum iteration number T ;
Construct the relevance matrix Y = [yiq ]N ×N where yiq if li = lq , 0 otherwise;
1
Initialize the graph weights as µ0m = M
, m = 1, · · · , M ;
for t = 1, · · · , T do
Update the ranking score matrix F t according to previous µt−1
m by (18);
Update the graph weight µt according to updated F t by (19);
end for
Output graph weight µ = µt .

(N +1)×(N +1)
• Laplacian matrix L: We first compute the m graph weight matrices {Wm }M
m=1 ∈ R
(N +1)×(N +1)
with their corresponding Laplacian matrices {Lm }M
for the extended database
m=1 ∈ R

{x0 , x1 , · · · , xN }. Then with the graph weight µ learned by Algorithm 1, the new Laplacian matrix L
can be computed as in (13).
On-line graph weight computation: When a new query x0 is added to the database, we calculate its
K nearest neighbors in the database D and the corresponding weights W0j and Wj0 , j = 1, · · · , N . If
adding this new query to the database does not affect the graph i n the database space, the neighbors
and weights Wij , i, j = 1, · · · , N for the protein domains in the database are fixed and can be precomputed off-line. Thus, we only need to compute N edge weights for each graph instead of (N + 1) ×
(N + 1).
• Relevance vector y: The relevance vector for x0 is defined as y = [y0 , · · · , yN ]⊤ ∈ {1, 0}N +1 with
only y0 = 1 known and yi , i = 1, · · · , N unknown.
• Matrix U : In this situation, U is a (N + 1) × (N + 1) diagonal matrix with U00 = 1 and Uii = 0,
i = 1, · · · , N .
Then the ranking score vector f can be solved as,

f = (U + αL)−1 U y
The on-line ranking algorithm is summarized as Algorithm 2.

10

(20)

Algorithm 2 MultiG-Rank: on-line ranking algorithm.
Require: protein domain database D = {x1 , · · · , xN };
Require: Query protein domain x0 ;
Require: Graph weight µ;
Extend the database to (N + 1) size by adding x0 and compute M graph Laplacians of the extended
database;
Obtain multiple graph Laplacian L by linear combination of M graph Laplacians with weight µ as in (13);
Construct the relevance vector y ∈ R(N +1) where y0 = 1 and diagonal matrix U ∈ R(N +1)×(N +1) with
Uii = 1 if i = 0 and 0 otherwise;
Solve the ranking vector f for x0 as in (20);
Ranking protein domains in D according to ranking scores f in descending order.

Protein domain database and query set
We used the SCOP 1.75A database [21] to construct the database and query set. In the SCOP 1.75A
database, there are 49,219 protein domain PDB entries and 135,643 domains, belonging to 7 classes and
1,194 SCOP fold types.

Protein domain database
Our protein domain database was selected from ASTRAL SCOP 1.75A set [21], a subset of the SCOP
(Structural Classification of Proteins)1.75A database which was released in March 15, 2012 [21]. ASTRAL
SCOP 1.75A 40%) [21], a genetic domain sequence subset, was used as our protein domain database D. This
database was selected from SCOP 1.75A database so that the selected domains have less than 40% identity
to each other. There are a total of 11,212 protein domains in the ASTRAL SCOP 1.75A 40% database
belonging to 1,196 SCOP fold types. The ASTRAL database is available on-line at http://scop.berkeley.edu.
The number of protein domains in each SCOP fold varies from 1 to 402. The distribution of protein domains
with the different fold types is shown in Fig. 1. Many previous studies evaluated ranking performances using
the older version of the ASTRAL SCOP dataset (ASTRAL SCOP 1.73 95%) that was released in 2008 [3].
Figure 1: Distribution of protein domains with different fold types in the ASTRAL SCOP 1.75A 40%
database.

Query set
We also randomly selected 540 protein domains from the SCOP 1.75A database to construct a query set. For
each query protein domain that we selected we ensured that there was at least one protein domain belonging

11

to the same SCOP fold type in the ASTRAL SCOP 1.75A 40% database, so that for each query, there was
at least one ”positive” sample in the protein domain database. However, it should be noted that the 540
protein domains in the query data set were randomly selected and do not necessarily represent 540 different
folds. Here we call our query set the 540 query dataset because it contains 540 protein domains from the
SCOP 1.75A database.

Evaluation metrics
A ranking procedure is run against the protein domains database using a query domain. A list of all
matching protein domains along with their ranking scores is returned. We adopted the same evaluation
metric framework as was described previously [3], and used the receiver operating characteristic (ROC)
curve, the area under the ROC curve (AUC), and the recall-precision curve to evaluate the ranking accuracy.
Given a query protein domain xq belonging to the SCOP fold lq , a list of protein domains is returned from the
database by the on-line MultiG-Rank algorithm or other ranking methods. For a database protein domain
xr in the returned list, if its fold label lr is the same as that of xq , i.e. lr = lq it is identified as a true positive
(TP), else it is identified as a false positive (FP). For a database protein domain xr′ not in the returned list,
if its fold label lr′ = lq , it will be identified as a true negative (TN), else it is a false negative (FN). The
true positive rate (TPR), false positive rate (FPR), recall, and precision can then be computed based on the
above statistics as follows:
TP
FP
,
FPR =
TP + FN
FP + TN
(21)
TP
TP
, precision =
recall =
TP + FN
TP + FP
By varying the length of the returned list, different T P R, F RP , recall and precision values are obtained.
TPR =

ROC curve Using F P R as the abscissa and T P R as the ordinate, the ROC curve can be plotted. For a
high-performance ranking system, the ROC curve should be as close to the top-left corner as possible.
Recall-precision curve Using recall as the abscissa and precision as the ordinate, the recall-precision curve
can be plotted. For a high-performance ranking system, this curve should be close to the top-right
corner of the plot.
AUC The AUC is computed as a single-figure measurement of the quality of an ROC curve. AUC is
averaged over all the queries to evaluate the performances of different ranking methods.

12

Results
We first compared our MultiG-Rank against several popular graph-based ranking score learning methods
for ranking protein domains. We then evaluated the ranking performance of MultiG-Ranking against other
protein domain ranking methods using different protein domain comparison strategies. Finally, a case study
of a TIM barrel fold is described.

Comparison of MultiG-Rank against other graph-based ranking methods
We compared our MultiG-Rank to two graph-based ranking methods, G-Rank and GT [6], and against the
pairwise protein domain comparison based ranking method proposed in [3] as a baseline method (Fig. 2) .
The evaluations were conducted with the 540 query domains form the 540 query set. The average ranking
performance was computed over these 540 query runs.
Figure 2: Comparison of MultiG-Rank against other protein domain ranking methods. Each curve represents a graph-based ranking score learning algorithm. MultiG-Rank, the Multiple Graph regularized Ranking
algorithm; G-Rank, Graph regularized Ranking; GT, graph transduction; Pairwise Rank, pairwise protein
domain ranking method [3] (a) ROC curves of the different ranking methods; (b) Recall-precision curves of
the different ranking methods.
The figure shows the ROC and the recall-precision curves obtained using the different graph ranking
methods. As can be seen, the MultiG-Rank algorithm significantly outperformed the other graph-based
ranking algorithms; the precision difference got larger as the recall value increased and then tend to converge
as the precision tended towards zero (Fig. 2 (b)). The G-Rank algorithm outperformed GT in most cases;
however, both G-Rank and GT were much better than the pairwise ranking which neglects the global
distribution of the protein domain database.
The AUC results for the different ranking methods on the 540 query set are tabulated in Table 1. As
shown, the proposed MultiG-Rank consistently outperformed the other three methods on the 540 query
set against our protein domain database, achieving a gain in AUC of 0.0155, 0.0210 and 0.0252 compared
with G-Rank, GT and Pairwise Rank, respectively. Thus, we have shown that the ranking precision can be
improved significantly using our algorithm.
We have made three observations from the results listed in Table 1:
1. G-Rank and GT produced similar performances on our protein domain database, indicating that there
is no significant difference in the performance of the graph transduction based or graph regularization
based single graph ranking methods for unsupervised learning of the ranking scores.
13

2. Pairwise ranking produced the worst performance even though the method uses a carefully selected
similarity function as reported in [3]. One reason for the poorer performance is that similarity computed
by pairwise ranking is focused on detecting statistically significant pairwise differences only, while
more subtle sequence similarities are missed. Hence, the variance among different fold types cannot be
accurately estimated when the global distribution is neglected and only the protein domain pairs are
considered. Another possible reason is that pairwise ranking usually produces a better performance
when there is only a small number of protein domains in the database; therefore, because our database
contains a large number of protein domains, the ranking performance of the pairwise ranking method
was poor.
3. MultiG-Rank produced the best ranking performance, implying that both the discriminant and geometrical information in the protein domain database are important for accurate ranking. In MultiGRank, the geometrical information is estimated by multiple graphs and the discriminant information
is included by using the SCOP-fold type labels to learn the graph weights.

Comparison of MultiG-Rank with other protein domain ranking methods
We compare the MultiG-Rank against several other popular protein domain ranking methods: IR Tableau
[3], QP tableau [4], YAKUSA [7], and SHEBA [8].

For the query domains and the protein domain

database we used the 540 query set and the ASTRAL SCOP 1.75A 40% database, respectively. The
YAKUSA software source code was downloaded from http://wwwabi.snv.jussieu.fr/YAKUSA , compiled
and used for ranking. We used the “make Bank” shell script (http://wwwabi.snv.jussieu.fr/YAKUSA)
which calls the phipsi program (Version 0.99 ABI, June 1993) to format the database.

YAKUSA

compares a query domain to a database and returns a list of the protein domains along with ranks
and ranking scores. We used the default parameters of YAKUSA to perform the ranking of the protein domains in our database. The SHEBA software (version 3.11) source code was downloaded from
https://ccrod.cancer.gov/confluence/display/CCRLEE/SHEBA, complied and used it for ranking. The protein domain database was converted to “.env” format and the pairwise alignment was performed between
each query domain and each database domain to obtain the alignment scores. First, we compared the different protein domain-protein domain ranking methods and computed their similarity or dissimilarity. An
ordering technique was devised to detect hits by taking the similarities between data pairs as input. For our
MultiG-Rank, the ranking score was used as a measure of protein domain-protein domain similarly. The

14

ranking results were evaluated based on the ROC and recall-precision curves as shown in Fig. 3. The AUC
values are given in Table 2.
Figure 3: Comparison of the performances of protein domain ranking algorithms. (a) ROC curves for
different field-specific protein domain ranking algorithms. TPR, true positive rate; FPR, false positive rate.
(b) Recall-precision curves for different field-specific protein domain ranking algorithms.
The results in Table 2 show that with the advantage of exploring data characteristics from various graphs,
MultiG-Rank can achieve significant improvements in the ranking outcomes; in particular, AUC is increased
from 0.9478 to 0.9730 in MultiG-Rank which uses the same Tableau feature as IR Tableau. MultiG-Rank
also outperforms QP Tableau, SHEBA, and YAKUSA; and AUC improves from 0.9364, 0.9421 and 0.9537,
respectively, to 0.9730 with MultiG-Rank. Furthermore, because of its better use of effective protein domain
descriptors, IR Tableau outperforms QP Tableau.
To evaluate the effect of using protein domain descriptors for ranking instead of direct protein domain
structure comparisons, we compared IR Tableau with YAKUSA and SHEBA. The main differences between
them are that IR Tableau considers both protein domain feature extraction and comparison procedures,
while YAKUSA and SHEBA compare only pairs of protein domains directly. The quantitative results in
Table 2 show that, even by using the additional information from the protein domain descriptor, IR Tableau
does not outperform YAKUSA . This result strongly suggests that ranking performance improvements are
achieved mainly by graph regularization and not by using the power of a protein domain descriptor.
Plots of TPR versus FPR obtained using MultiG-Rank and various field-specific protein domain ranking
methods as the ranking algorithms are shown in Fig. 3 (a) and the recall-precision curves obtained using
them are shown in Fig. 3 (b). As can be seen from the figure, in most cases, our MultiG-Rank algorithm
significantly outperforms the other protein domain ranking algorithms. The performance differences get
larger as the length of the returned protein domain list increases. The YAKUSA algorithm outperforms
SHEBA, IR Tableau and QP Tableau in most cases. When only a few protein domains are returned to the
query, the sizes of both the true positive samples and the false positive samples are small, showing that, in
this case, all the algorithms yield low FPR and TPR. As the number of returned protein domains increases,
the TPR of all of the algorithms increases. However, MultiG-Rank tends to converge when the FPR is more
than 0.3, whereas the other ranking algorithms seems to converge only when the FPR is more than 0.5.

15

Case Study of the TIM barrel fold
Besides considering the results obtained for the whole database, we also studied an important protein fold,
the TIM beta/alpha-barrel fold (c.1). The TIM barrel is a conserved protein fold that consists of eight
α-helices and eight parallel β-strands that alternate along the peptide backbone [22]. TIM barrels are one
of the most common protein folds. In the ASTRAL SCOP 1.75A %40 database, there are a total of 373
proteins belonging to 33 different superfamilies and 114 families that have TIM beta/alpha-barrel SCOP
fold type domains,. In this case study, the TIM beta/alpha-barrel domains from the query set were used
to rank all the protein domains in the database. The ranking was evaluated both at the fold level of the
SCOP classification and at lower levels of the SCOP classification (ie. superfamily level and family level).
To evaluate the ranking performance, we defined ”true positives” at three levels:
Fold level When the returned database protein domain is from the same fold type as the query protein
domain.
Superfamily level When the returned database protein domain is from the same superfamily as the query
protein domain.
Family level When the returned database protein domain is from the same family as the query protein
domain.
The ROC and the recall-precision plots of the protein domain ranking results of MultiG-Rank for the
query TIM beta/alpha-barrel domain at the three levels are given in Fig. 4. The graphs were learned using
the labels at the family, superfamily and the fold level. The results show that the ranking performance at
the fold level is better than at the other two levels; however, although the performances at the lower levels,
superfamily and family, are not superior to that at the fold level, they are still good. One important factor
is that when the relevance at the lower levels was measured, a much fewer number of protein domains in
the database were relevant to the queries, making it more difficult to retrieve the relevant protein domains
precisely. For example, a query belonging to the family of phosphoenolpyruvate mutase/Isocitrate lyaselike (c.1.12.7) matched 373 database protein domains at the fold level because this family has 373 protein
domains in the ASTRAL SCOP 1.75A %40 database. On the other hand, only 14 and four protein domains
were relevant to the query at the superfamily and family levels respectively.

16

Figure 4:
Ranking results for the case study using the TIM beta/alpha-barrel domain as the query. (a)
ROC curves of the ranking results for the TIM beta/alpha-barrel domain at the fold, superfamily, and family
levels. TPR, true positive rate; FPR, false positive rate. (b) Recall-precision curves of the ranking results
for the TIM beta/alpha-barrel domain at the fold, superfamily, and family levels.

Conclusion
The proposed MultiG-Rank method introduces a new paradigm to fortify the broad scope of existing graphbased ranking techniques. The main advantage of MultiG-Rank lies in its ability to represent the learning
of a unified space of ranking scores for protein domain database in multiple graphs. Such flexibility is
important in tackling complicated protein domain ranking problems because it allows more prior knowledge
to be explored for effectively analyzing a given protein domain database, including the possibility of choosing
a proper set of graphs to better characterize diverse databases, and the ability to adopt a multiple graphbased ranking method to appropriately model relationships among the protein domains. Here, MultiG-Rank
has been evaluated comprehensively on a carefully selected subset of the ASTRAL SCOP 1.75 A protein
domain database. The promising experimental results that were obtained further confirm the usefulness of
our ranking score learning approach.

Competing interests
The authors declare no competing interests.

Author’s contributions
JW invented the algorithm, performed the experiments and drafted the manuscript.

HB drafted the

manuscript. XG supervised the study and made critical changes to the manuscript. All the authors have
approved the final manuscript.

Acknowledgements
The study was supported by grants from National Key Laboratory for Novel Software Technology, China
(Grant No. KFKT2012B17), 2011 Qatar Annual Research Forum Award (Grant No. ARF2011), and
King Abdullah University of Science and Technology (KAUST), Saudi Arabia. We appreciate the valuable
comments from Prof. Yuexiang Shi, Xiangtan University, China.

17

References
1. Zhang Y, Sun Y: HMM-FRAME: accurate protein domain classification for metagenomic
sequences containing frameshift errors. BMC Bioinformatics 2011, 12(198).
2. Ochoa A, Llinas M, Singh M: Using context to improve protein domain identification. BMC
Bioinformatics 2011, 12(90).
3. Zhang L, Bailey J, Konagurthu AS, Ramamohanarao K: A fast indexing approach for protein
structure comparison. BMC Bioinformatics 2010, 11(1).
4. Stivala A, Wirth A, Stuckey PJ: Tableau-based protein substructure search using quadratic
programming. BMC Bioinformatics 2009, 10:153.
5. Stivala AD, Stuckey PJ, Wirth AI: Fast and accurate protein substructure searching with simulated annealing and GPUs. BMC Bioinformatics 2010, 11(446).
6. Bai X, Yang X, Latecki LJ, Liu W, Tu Z: Learning Context-Sensitive Shape Similarity by Graph
Transduction. IEEE Transactions on Pattern Analysis and Machine Intelligence 2010, 32(5):861–874.
7. Carpentier M, Brouillet S, Pothier J: YAKUSA: A fast structural database scanning method.
Proteins-Structure Function and Bioinformatics 2005, 61(1):137–151.
8. Jung J, Lee B: Protein structure alignment using environmental profiles. Protein Engineering
2000, 13(8):535–543.
9. Lee B, Lee D: Protein comparison at the domain architecture level. BMC Bioinformatics 2009,
10.
10. Weston J, Kuang R, Leslie C, Noble W: Protein ranking by semi-supervised network propagation. BMC Bioinformatics 2006, 7(1).
11. Cai D, He X, Han J, Huang TS: Graph Regularized Nonnegative Matrix Factorization for Data
Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 2011, 33(8):1548–
1560.
12. Varma S, Simon R: Bias in error estimation when using cross-validation for model selection.
BMC Bioinformatics 2006, 7(91).

18

13. Nagel K, Jimeno-Yepes A, Rebholz-Schuhmann D: Annotation of protein residues based on a
literature analysis: cross-validation against UniProtKb. BMC Bioinformatics 2009, 10.
14. Geng B, Tao D, Xu C, Yang L, Hua X: Ensemble Manifold Regularization. IEEE Transactions on
Pattern Analysis and Machine Intelligence 2012, PP(99):1.
15. You ZH, Yin Z, Han K, Huang DS, Zhou X: A semi-supervised learning approach to predict synthetic genetic interactions by combining functional and topological properties of functional
gene network. BMC Bioinformatics 2010, 11(343).
16. Min Song, Hwanjo Yu, Wook-Shin Han: Combining active learning and semi-supervised learning
techniques to extract protein interaction sentences. BMC Bioinformatics 2011, :S4 (11 pp.).
17. Kandaswamy KK, Pugalenthi G, Hazrati MK, Kalies KU, Martinetz T: BLProt: prediction of bioluminescent proteins based on support vector machine and relieff feature selection. BMC
Bioinformatics 2011, 12(345).
18. Tung CW, Ziehm M, Kaemper A, Kohlbacher O, Ho SY: POPISK: T-cell reactivity prediction
using support vector machines and string kernels. BMC Bioinformatics 2011, 12(446).
19. Shi JY, Zhang YN: Fast SCOP classification of structural class and fold using secondary
structure mining in distance matrix. In Pattern Recognition in Bioinformatics. Proceedings 4th
IAPR International Conference, PRIB 2009 2009:344–53.
20. Albatineh AN, Niewiadomska-Bugaj M: Correcting Jaccard and other similarity indices for
chance agreement in cluster analysis. Advances in Data Analysis and Classification 2011, 5(3):179–
200.
21. Chandonia J, Hon G, Walker N, Lo Conte L, Koehl P, Levitt M, Brenner S: The ASTRAL Compendium in 2004. Nucleic Acids Research 2004, 32(SI):D189–D192.
22. Kim C, Basner J, Lee B: Detecting internally symmetric protein structures. BMC Bioinformatics
2010, 11(303).

19

Figures
Figure 1 - Distribution of protein domains with different fold types in the ASTRAL SCOP 1.75A 40%
database.

Figure 2 - Comparison of MultiG-Rank against other protein domain ranking methods.
Each curve represents a graph-based ranking score learning algorithm. MultiG-Rank, the Multiple Graph
regularized Ranking algorithm; G-Rank, Graph regularized Ranking; GT, graph transduction; Pairwise
Rank, pairwise protein domain ranking method [3] (a) ROC curves of the different ranking methods; (b)
Recall-precision curves of the different ranking methods.

Figure 3 - Comparison of the performances of protein domain ranking algorithms.
(a) ROC curves for different field-specific protein domain ranking algorithms. TPR, true positive rate; FPR,
false positive rate. (b) Recall-precision curves for different field-specific protein domain ranking algorithms.

Figure 4 - Ranking results for the case study using the TIM beta/alpha-barrel domain as the query.
(a) ROC curves of the ranking results for the TIM beta/alpha-barrel domain at the fold, superfamily, and
family levels. TPR, true positive rate; FPR, false positive rate. (b) Recall-precision curves of the ranking
results for the TIM beta/alpha-barrel domain at the fold, superfamily, and family levels.

20

Tables
Table 1 - AUC results off different graph-based ranking methods.
Table 1: AUC results off different graph-based ranking methods.
Method
AUC
MultiG-Rank
0.9730
G-Rank
0.9575
GT
0.9520
Pairwise-Rank 0.9478

Table 2 - AUC results for different protein domain ranking methods.
Table 2: AUC results for different protein domain ranking methods.
Method
AUC
MultiG-Rank 0.9730
IR Tableau
0.9478
YAKUSA
0.9537
SHEBA
0.9421
QP tableau
0.9364

21

