J. Biomedical Science and Engineering, 2009, 2, 621-625 JBiSE
doi: 10.4236/jbise.2009.28090 Published Online December 2009 (http://www.SciRP.org/journal/jbise/).
Published Online December 2009 in SciRes. http://www.scirp.org/journal/jbise
FastCluster: a graph theory based algorithm for removing
redundant sequences
Peng-Fei Liu2, Yu-Dong Cai1*, Zi-Liang Qian3,4, Sheng-Yu Ni5, Liu-Huan Dong5, Chang-Hong Lu6,7,
Jin-Long Shu6 , Zhen-Bing Zeng2,5, Wen-Cong Lu8*
1Institute of Systems Biology, Shanghai University, Shanghai, China;
2Software Engineering Institute of East China Normal University, East China Normal University, Shanghai, China;
3
Bioinformatics Center, Key Lab of Systems Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences,
Shanghai, China;
4
Graduate School of the Chinese Academy of Sciences, Beijing, China;
5
CAS-MPG Partner Institute for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences,
Shanghai, China;
6
Department of Mathematics, East China Normal University, Shanghai, China;
7
Institute of Theoretical Computing, East China Normal University, Shanghai, China;
8
Department of Chemistry, Shanghai University, Shanghai, China.
[e-mail]; [e-mail]; [e-mail]; *[e-mail]
Received 1 August 2009; revised 30 August 2009, accepted 3 September 2009.
ABSTRACT
In many cases, biological sequence databases contain
redundant sequences that make it difficult to achieve
reliable statistical analysis. Removing the redundant
sequences to find all the real protein families and
their representatives from a large sequences dataset
is quite important in bioinformatics. The problem of
removing redundant protein sequences can be mod-
eled as finding the maximum independent set from a
graph, which is a NP problem in Mathematics. This
paper presents a novel program named FastCluster
on the basis of mathematical graph theory. The algo-
rithm makes an improvement to Hobohm and
Sander’s algorithm to generate non-redundant pro-
tein sequence sets. FastCluster uses BLAST to de-
termine the similarity between two sequences in or-
der to get better sequence similarity. The algorithm’s
performance is compared with Hobohm and
Sander’s algorithm and it shows that Fast- Cluster
can produce a reasonable non-redundant pro- tein set
and have a similarity cut-off from 0.0 to 1.0. The
proposed algorithm shows its superiority in generat-
ing a larger maximal non-redundant (independent)
protein set which is closer to the real result (the
maximum independent set of a graph) that means all
the protein families are clustered. This makes Fast-
Cluster a valuable tool for removing redundant pro-
tein sequences.
Keywords: Blast; Graph Theory; Redundant Sequences;
CD-HIT
1. INTRODUCTION
Recently, with the explosion of biological sequence data,
many biological sequence databases have redundant se-
quences which can cause problems for data analysis.
These redundant sequences cannot provide valuable in-
formation for analysis but detracts from the statistical
significance of interesting hits. Moreover, processing
these redundant sequences often requires more time and
computational resources. Removing redundant sequen-
ces is undoubtedly very helpful for performing statistical
analysis and accelerating extensive database searching
[1]. And it is also a way to obtain the real protein fami-
lies and their representatives from a large sequences
dataset. Therefore, it is necessary to develop an appro-
priate algorithm to remove redundant sequences from a
biological sequence database.
Hobohm and Sander’s algorithm is a widely used al-
gorithm in many redundant sequence removing pro-
grams. Hobohm and Sander’s algorithm was firstly in-
troduced by U.Hobohm et al. of EMBL laboratory in
1992. In 1998, Lissa Holm and Chris Sander developed
a program based on this algorithm to generate a non-
redundant protein database NRDB90 [2]. After that,
other researchers developed some programs for remov-
ing redundant sequences on the basis of Hobohm and
Sander ’s algorithm, such as CD-HIT and PISCES.
CD-HIT [3,4] is a well-known program for processing
large sequence databases efficiently. It is fast and flexi-
ble and can generate a representative set based on an
incremental greedy algorithm introduced by Hobohm

622 P. F. Liu et al. / J. Biomedical Science and Engineering 2 (2009) 621-625
SciRes Copyright © 2009 JBiSE
and Sander [5,6]. It uses short word filtering to deter-
mine the similarity between two sequences rather than
performing an actual sequence alignment. However, the
results generated by short word filtering are not accurate
to some degree. The lowest threshold of CD-HIT is
around 40% and it is not suitable for removing redun-
dancy on lower threshold. PISCES [7] is a public server
for culling sets of protein sequences from the Protein
Data Bank. It determines sequence similarity by PSI-
BLAST [8] alignments which are more accurate, and it
also uses a structural quality criterion to cull sequences
from a sequence database.
Hobohm and Sander ’s algorithm has the advantage of
being simple and fast. But the result set generated by this
algorithm is not large enough since some non-redundant
sequences may also be removed.
FastCluster, introduced in this paper, uses BLAST [9]
to determine sequence similarity, which is a general se-
quence alignment tool and can provide better sequence
similarity than word filtering. FastCluster makes im-
provements to Hobohm and Sander’s algorithm and can
get a larger non-redundant protein dataset, which means
more protein families can be clustered.
2. METHODS
2.1. Hobohm and Sander’s Algorithm
Hobohm and Sander’s algorithm sorts all sequences by
length in descending order to generate an ordered sequen-
ce set S. Then similar sequences will be put together into
the same cluster. The longest sequence is added into the
first cluster (initially empty), which is also the represen-
tative of the cluster, and then all the other sequences are
compared with the representative. If the similarity be-
tween a sequence and the representative is above a thre-
shold then it will be included into the same cluster as the
representative’s, otherwise a new cluster will be created
with it as the representative. Every remaining sequence
will be processed in the same way, either as the repre-
sentative of a new cluster if the similarity between it and
any representative is below the threshold, or included
into some existing cluster if it is similar to the cluster ’s
representative.
2.2. Graph Theory Based Algorithm
In order to make some improvements to Hobohm and
Sander ’s algorithm, a new algorithm using maximum
independent set of graph theory to generate a representa-
tive set is developed. Firstly all the sequences are clus-
tered simply and the first sequence of each cluster is the
temporary representative sequence of the cluster. Then
the maximum independent set of each cluster (excluding
the representative sequence) is figured out. Finally the
maximum independent set of each cluster is processed
and the final maximal independent set can be generated.
Based on the algorithm above, FastCluster was written
in C++ and tested on Linux platform. The input to the
program is a protein sequence set in FASTA format.
Three output files can be generated by FastCluster. One
is a FASTA file containing a list of representative pro-
teins free from redundancy. Another output file lists the
clusters and their members and the third output file con-
tains clusters and the size of each cluster’s maximal in-
dependent set. FastCluster can be downloaded from
http://pcal.biosino.org/FastCluster.html.
2.3. Blast-Based Similarity Score (BSS)
FastCluster uses BLAST to make pair wise sequence
alignments. The similarity score between two sequences
is determined by the identical percentage of their hits
(homologous sequence segments). When a sequence
alignment has more than one hit, the percentage of the
sum of all hits’ identical is calculated to represent the
overall similarity score between the two sequences.
A Python script was used to parse BLAST output and
construct a BLAST-BASED SIMILARITY SCORE (BSS)
matrix. An expectation value parameter 1e-3 is set to
filter BLAST output in which the expectation value of
each hit is smaller than 1e-3. When calculating BSS,
three cases have to be considered: 1) there are no hits
found; 2) there is one hit found; 3) there are more than
one hit found. Formula 1 below shows how to calculate
the BSS.





∑∑
=
)(/
)(/
)(0
11 foundhitsNLI
foundhitOneLI
foundhitNo
BSS
nn
Formula 1: The formula to calculate BSS. ‘I’ is short
for the length of a hit’s identities, and ‘L’ stands for the
length of a hit’s length. In case of no hits found, the BSS
is regarded as 0. When there is one hit in the BLAST
output, the identical percentage is taken as the BSS. On
the occasion of more than one hit found, the percentage
of the sum of all hits’ identities is taken as the BSS.
Figure 1 shows an example of how to calculate the
BSS from BLAST output.
2.4. Graph Definition
A graph is a mathematical object which is composed of
vertices and edges. It is usually used to represent rela-
tions between objects. Graphs can be categorized into
four types: undirected graphs (or simple graphs), di-
rected graphs, multigraphs and weighted graphs. Fast-
Cluster uses an undirected graph to represent relations
between protein sequences.
2.5. Clique and Independent Set of a Graph
An undirected graph is denoted by ),( EVG
=
, in which
V is the set of vertices and
E
are the set of edges and
every edge is composed of two adjacent vertices in V.

P. F. Liu et al. / J. Biomedical Science and Engineering 2 (2009) 621-625 623
SciRes Copyright © 2009 JBiSE
Figure 1. An example of parsing BLAST output. Three cases are considered: (1) Case
1, the BSS is 0; (2) Case 2, the BSS is 94/102=0.922; (3) Case 3, the BSS is (35+20)/
(163+57) =0.25.
In FastCluster, an undirected graph is defined as follows:
any vertex represents a protein sequence; and if two
protein sequences have a BSS above the given threshold,
there is an edge between them.
A clique Cof a graph G is a subset of V, and every
vertex in C is adjacent to all the other vertices in C,
while an independent set of a graph is a set of vertices,
none of which are adjacent. A clique is said to be maxi-
mal if it is not the subset of any larger clique, and maxi-
mum if there are no larger cliques in the graph [10]. The
complement of a graph G is the graph
'
G with the
same vertex set but whose edge set consists of the edges
not present in G. [http://mathworld.wolfram.com/Graph
Complement.html]. By taking the complement of a
graph, the maximum independent set problem is trans-
formed into the maximum clique problem.
The concept of clique and independent set is illus-
trated in Figure 2.
2.6. Algorithm Procedure
The algorithm used in FastCluster is described in the
following steps.
1) Run local BLAST for sequence set S to make
pair wise alignments.
2) Parse BLAST output and construct a BSS matrix
for all the sequences.
3) Sort all sequences in descending order by length
and construct the first cluster with the longest se-
quence as its representative.
4) Align each remaining sequence in S with the ex-
isting representatives. If the BSS (from BSS matrix
in step 2) between a sequence with any representa-
tive is above a given threshold, then it is included
into that cluster, otherwise a new cluster starts with
it as representative.
5) Repeat Step 4 until S is empty. Thus, a list of
clusters for set S is generated and every cluster
has a temporary representative sequence (the first
sequence of that cluster).
6) Compute the maximum independent set for each
cluster.
7) Construct an empty set
R
. If the maximum inde-

624 P. F. Liu et al. / J. Biomedical Science and Engineering 2 (2009) 621-625
SciRes Copyright © 2009 JBiSE
pendent set of the last cluster has more than or equal
to 2 sequences, then every sequence in the maxi-
mum independent set is put into
R
, otherwise the
representative of the cluster is put into
R
.
8) Process each remaining maximum independent set
from the last one to the first. If a set has more than
or equal to 2 sequences which have no edge with
any sequence in
R
, then put these sequences in the
maximum independent set into
R
, otherwise put the
cluster ’s representative into
R
.
9) Output the final representative non-redundant set
R
to a file in Fasta format.
2.7. Algorithm Comparison
An algorithm comparison is shown in Figure 3. As
shown below, S is an ordered sequence set and
R
is the result sequence dataset.
(
)
i
rS is composed
ofsequences which are similar to representative se-
quence i r. In Figure 3,
(
)
(
)
i
rSC is the maximum
independent set of
(
)
i
rS , in which no sequence is
similar to any other one, and f is a procedure to
process the maximum independent set of every cluster.
Both of the algorithms share the same procedure to
generate a list of clusters
(
)
1
rS ,
(
)
2
rS …
(
)
n
rS . That is
to say, both of them sort all sequences by length in de-
creasing order firstly to generate an ordered sequence set
S and then partition them into different clusters. The
difference lies in the way they generate result set
R
.
Hobohm and Sander’s algorithm (Figure 3(a)) simply
picks up the representative sequence of each cluster and
put them together to compose result set
R
, while Fast-
Cluster behaves in a different way.
It searches the maximum independent set for each
cluster and get
n
maximum independent set
(
)
(
)
1
rSC ,
(
)
(
)
2
rSC …
(
)
(
)
n
rSC. Then they are processed in a pro-
cedure f to generate the final result set R. fis such a
procedure that if the number of sequences in
(
)
(
)
i
rSC
is less than 2, then i r is added to R, otherwise every
sequence in
(
)
(
)
i
rSC is put to R on condition that the
sequence has no edge with any sequence of current
R
which grows bigger in an incremental way.
Some
(
)
(
)
i
rSC usually have more than 2 sequences, so
after we replace i r with
(
)
(
)
i
rSC , it is clear that
R
in
FastCluster is larger than
R
in the algorithm of Ho-
bohm and Sander. An example below is used to prove
that.
2.8. An Example for Algorithm Comparison
As shown in Figure 4, vertices 1,2,3,4,5 and 6 repre-
sents 6 different protein sequences respectively. If two
protein sequences have a BSS above the given threshold,
there is an edge between them. Vertices 1,2,3,4,5 and 6
Figure 2. (a) is Graph G; (b) is its complementary graph
'G. Vertices set
{
}
543 ,, is the maximum clique of G and
the maximum independent set of graph 'G. Vertices set
{
}
41, or
{
}
51, or
{
}
32, or
{
}
52, is the maximum clique of
'G and is also the maximum independent set of graph G.
(a)
(b)
Figure 3. (a) Algorithm of Hobohm and sander; (b) Graph theory based algorithm by FastCluster.

P. F. Liu et al. / J. Biomedical Science and Engineering 2 (2009) 621-625 625
SciRes Copyright © 2009 JBiSE
Figure 4. A graph example.
Table 1. Number of non-redundant sequences obtained using
FastCluster and HSCluster.
Database Threshold
(%)
Number
(FastCluster)
Number
(HSCluster)
10 3167 2824
20 3185 2845
30 5256 4753
40 12940 10058
50 18177 17275
60 25854 25020
70 33400 32758
80 41049 40555
65718 En-
zyme pro-
teins
90 49986 49669
are assumed to be ordered in descending order by length.
This example can be used to prove that FastCluster can
produce more results than Hobohm and Sander’s algo-
rithm.
Hobohm and Sander’s algorithm and FastCluster
share the same way to generate three clusters, and they
are {} 1 , { } 2 and { } 6543 ,,, (Figure 4). But the way
they generate the result set is different. According to
Hobohm and Sander’s algorithm, the representative ver-
tex from each cluster is picked up to compose the result
vertices
{ }
3,2,1 . While FastCluster computes the maxi-
mum independent set for each cluster and they are
{}
1,
{ } 2 and { } 6,4 , and then it collects { } 6,4, { } 2 and
{}
1
together to compose the final result vertices { } 6,4,2,1.
Obviously,
{ }
6,4,2,1 is larger than
{ }
321 ,, . From this
example, it is proved that FastCluster can produce more
results than Hobohm and Sander ’s algorithm.
3. RESULTS AND DISCUSSION
FastCluster introduces a graph theory algorithm to re-
move redundant protein sequences and runs in a flexible
and user-friendly way. It can also be changed to process
other types of biological sequences easily.
A protein sequence set (65718 enzymes, from
http://expasy.org/sprot/) was selected to test the per-
formance of FastCluster. Another program HSCluster
which implements the algorithm of Hobohm and San-
der is also developed. The results generated by these
two algorithms are shown in Table 1. It is clear that
FastCluster can produce more results than HSCluster.
4. CONCLUSIONS
This paper makes an investigation on removing redun-
dant biological sequences, which is modeled as a mathe-
matical problem of finding a maximal independent set
from a graph. Based on this model, FastCluster has made
an improvement to Hobohm and Sander ’s algorithm in
finding a larger independent set of a graph and thus gen-
erate more result sequences, which mean that more pro-
tein families can be clustered in a protein dataset. In a
word, FastCluster provides an alternatively improved
way to remove redundancy from a biological database and
is also a computational tool to find more protein families
and their representatives.
5. ACKNOWLEDGEMENTS
This research was supported by the grants from Shanghai Commission
for Science and Technology (KSCX2-YW-R-112), and Shanghai
Leading Academic Discipline Project (J50101).
REFERENCES
[1] G. Grillo, M. Attimonelli, S. Liuni, G. Pesole. (1996)
CLEANUP: a fast computer program for removing re-
dundancies from nucleotide sequence databases.
CABIOS, 12, 1–8.
[2] L. Holm and C. Sander. (1998) Removing near-
neighbour redundancy from llarge protein sequence col-
lections. Bioinformatics, 14, 423–429.
[3] W. Li and A. Godzik. (2006) Cd-Hit: a fast program for
clustering and comparing large sets of protein or nucleo-
tide sequences. Bioinformatics, 22, 1658–1659.
[4] W. Li, J L. aroszewski, A. Godzik. (2001) Clustering of
highly homologous sequences to reduce the size of large
protein databases. Bioinformatics, 17, 282–283.
[5] U. Hobohm, M. Scharf, R. Schneider, C. Sander. (1992)
selection of representative protein data sets. Protein Sci,
1, 409–417.
[6] U. Hobohm and C. Sander. (1994) Enlarged representa-
tive set of protein structures. Protein Sci, 3, 522–524.
[7] G. Wang and R. L. Jr. Dunbrack. (2003) PISCES: a pro-
tein sequence culling server. Bioinformatics, 12, 1589–
1591.
[8] S. F. Altschul, T. L. Madden, A. A. Schäffer, J. Zhang, Z.
Zhang, W. Miller, D. J. Lipman. (1997) Gapped BLAST
and PSI-BLAST: a new generation of protein database
search programs. Nucleic Acids Research, 25, 3389–
3402.
[9] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, D. J.
Lipman. (1990) Basic local alignment search tool. J. Mol.
Biol., 215, 403–410.
[10] S. Niskanen and P. R. J. Östergård. (2003) Cliquer user’s
guide, Version 1.0, Communications Laboratory, Hel-
sinki University of Technology, Espoo, Tech. Rep. T48.
http://users.tkk.fi/~pat/cliquer.html.