Display Settings:


Send to:

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 2011 Mar;18(3):263-81. doi: 10.1089/cmb.2010.0269.

Subnetwork state functions define dysregulated subnetworks in cancer.

Author information

  • 1Department of Electrical Engineering and Computer Science, Case Western Reserve University, Cleveland, Ohio, USA.


Emerging research demonstrates the potential of protein-protein interaction (PPI) networks in uncovering the mechanistic bases of cancers, through identification of interacting proteins that are coordinately dysregulated in tumorigenic and metastatic samples. When used as features for classification, such coordinately dysregulated subnetworks improve diagnosis and prognosis of cancer considerably over single-gene markers. However, existing methods formulate coordination between multiple genes through additive representation of their expression profiles and utilize fast heuristics to identify dysregulated subnetworks, which may not be well suited to the potentially combinatorial nature of coordinate dysregulation. Here, we propose a combinatorial formulation of coordinate dysregulation and decompose the resulting objective function to cast the problem as one of identifying subnetwork state functions that are indicative of phenotype. Based on this formulation, we show that coordinate dysregulation of larger subnetworks can be bounded using simple statistics on smaller subnetworks. We then use these bounds to devise an efficient algorithm, Crane, that can search the subnetwork space more effectively than existing algorithms. Comprehensive cross-classification experiments show that subnetworks identified by Crane outperform those identified by additive algorithms in predicting metastasis of colorectal cancer (CRC).

[PubMed - indexed for MEDLINE]
Free PMC Article

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

FIG. 1.
FIG. 2.
FIG. 3.
FIG. 4.
FIG. 5.
FIG. 6.
PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc. Icon for PubMed Central
    Loading ...
    Write to the Help Desk