Bioinformatics Advance Access originally published online on May 6, 2004
Bioinformatics 2004 20(16):2586-2596; doi:10.1093/bioinformatics/bth290
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics vol. 20 issue 16 © Oxford University Press 2004; all rights reserved.
Incremental generation of summarized clustering hierarchy for protein family analysis
1 Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan, R.O.C. and 2 Institute of Biotechnology and Department of Chemical Engineering, National Taipei University of Technology, Taipei 106, Taiwan, R.O.C.
Received on November 18, 2003; revised on March 28, 2004; accepted on April 25, 2004
Advance Access Publication May 6, 2004
Motivation: Protein sequence clustering has been widely exploited to facilitate in-depth analysis of protein functions and families. For some applications of protein sequence clustering, it is highly desirable that a hierarchical structure, also referred to as dendrogram, which shows how proteins are clustered at various levels, is generated. However, as the sizes of contemporary protein databases continue to grow at rapid rates, it is of great interest to develop some summarization mechanisms so that the users can browse the dendrogram and/or search for the desired information more effectively.
Results: In this paper, the design of a novel incremental clustering algorithm aimed at generating summarized dendrograms for analysis of protein databases is described. The proposed incremental clustering algorithm employs a statistics-based model to summarize the distributions of the similarity scores among the proteins in the database and to control formation of clusters. Experimental results reveal that, due to the summarization mechanism incorporated, the proposed incremental clustering algorithm offers the users highly concise dendrograms for analysis of protein clusters with biological significance. Another distinction of the proposed algorithm is its incremental nature. As the sizes of the contemporary protein databases continue to grow at fast rates, due to the concern of efficiency, it is desirable that cluster analysis of a protein database can be carried out incrementally, when the protein database is updated. Experimental results with the Swiss-Prot protein database reveal that the time complexity for carrying out incremental clustering with k new proteins added into the database containing n proteins is O(n2ßlogn), where ß 
0.865, provided that k << n.
Availability: The Linux executable is available on the following supplementary page.
Supplementary information: http://mars.csie.ntu.edu.tw/~cychen/protein_clustering/psc.htm
Contact: Graduate School of Biotechnology and Bioinformatics, Yuan–Ze University, Chang–Li 320, Taiwan, ROC. Email: cychen{at}mars.csie.ntu.edu.tw