Skip Navigation



Bioinformatics Advance Access published online on May 6, 2004
Bioinformatics, doi:10.1093/bioinformatics/bth290
Bioinformatics © Oxford University Press 2004; all rights reserved
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow All Versions of this Article:
20/16/2586    most recent
bth290v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Chen, C.-Y.
Right arrow Articles by Juan, H.-F.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Chen, C.-Y.
Right arrow Articles by Juan, H.-F.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Received November 18, 2003
Revised March 28, 2004
Accepted April 25, 2004

Article

Incremental generation of summarized clustering hierarchy for protein family analysis

Chien-Yu Chen 1*, Yen-Jen Oyang 1, Hsueh-Fen Juan 2

1 Department of Computer Science and Information Engineering National Taiwan University, Taipei, 106, Taiwan
2 Institute of Biotechnology and Department of Chemical Engineering National Taipei University of Technology, Taipei, 106, Taiwan

* To whom correspondence should be addressed. E-mail: cychen{at}mars.csie.ntu.edu.tw.


  Abstract

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 a rapid rate, 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{beta}logn), where {beta}=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.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.