The advent of whole-genome expression profiling technology has made it possible to identify transcriptional dysregulation that contribute to or result from disease mechanisms and can also serve as biomarkers for disease. However, expression-alone classification can be challenging in complex diseases due to factors such as genetic heterogeneity across patients or noise in mRNA levels. Moreover, it remains unclear how these marker genes interrelate within a larger functional network. We propose a novel approach to integrate gene expression with protein interactions to dissect cancer development and outcome. The new prognostic markers are not individual genes or proteins, but as sets of coherently expressed genes whose products interact within a larger human protein interaction network. In breast cancer, we show that this integrated strategy predict the risk of metastasis potential more accurately than previous approaches based only on gene expression. More than being more reproducible and robust, our network markers also give molecular models for how the cancer susceptibility genes might be associated with cancer metastasis. We next apply this network-based analysis to develop a new system for accurately stratifying patients of chronic lymphocytic leukemia (CLL) at different risk levels of disease progression. The network markers represent an array of disease pathways whose expression converge over time among patients regardless their initial risk levels, implicating novel understanding for cancer evolution and for the development of treatment strategies. Besides incorporating protein interaction network into gene expression analyses, we also identify condition-responsive genes within canonical pathways to infer dysfunctional pathway activation. Contrast to methods based on static pathway knowledge, our dynamic pathway markers lead to better clinical performance for various cancers, including leukemia, prostate cancer, breast cancer and lung cancer. Another way to address the difficulties seen in gene expression studies is to obtain direct measurement of protein levels and states by quantitative mass spectrometry. We develop a method to select protein markers based on the change in expression relative to the standard deviation of repeated measurements across experimental replicates. In CLL disease progression, our protein markers are shown to be involved in the same pathways and more prognostic of newly diagnosed patients. We further discuss strategies for targeted proteomic profiling with the guidance of protein interaction networks