Display Settings:

Format

Send to:

Choose Destination
Bioinformatics. 2011 Feb 1;27(3):326-33. doi: 10.1093/bioinformatics/btq655. Epub 2010 Nov 29.

Improving the quality of protein similarity network clustering algorithms using the network edge weight distribution.

Author information

  • 1Department of Pharmaceutical Chemistry, University of California, San Francisco, CA, USA.

Abstract

MOTIVATION:

Clustering protein sequence data into functionally specific families is a difficult but important problem in biological research. One useful approach for tackling this problem involves representing the sequence dataset as a protein similarity network, and afterwards clustering the network using advanced graph analysis techniques. Although a multitude of such network clustering algorithms have been developed over the past few years, comparing algorithms is often difficult because performance is affected by the specifics of network construction. We investigate an important aspect of network construction used in analyzing protein superfamilies and present a heuristic approach for improving the performance of several algorithms.

RESULTS:

We analyzed how the performance of network clustering algorithms relates to thresholding the network prior to clustering. Our results, over four different datasets, show how for each input dataset there exists an optimal threshold range over which an algorithm generates its most accurate clustering output. Our results further show how the optimal threshold range correlates with the shape of the edge weight distribution for the input similarity network. We used this correlation to develop an automated threshold selection heuristic in order to most optimally filter a similarity network prior to clustering. This heuristic allows researchers to process their protein datasets with runtime efficient network clustering algorithms without sacrificing the clustering accuracy of the final results.

AVAILABILITY:

Python code for implementing the automated threshold selection heuristic, together with the datasets used in our analysis, are available at http://www.rbvi.ucsf.edu/Research/cytoscape/threshold_scripts.zip.

PMID:
21118823
[PubMed - indexed for MEDLINE]
PMCID:
PMC3031030
Free PMC Article

Images from this publication.See all images (3)Free text

Fig. 1.
Fig. 2.
Fig. 3.
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for HighWire Icon for PubMed Central
    Loading ...
    Write to the Help Desk