title: Robust and efficient identification of biomarkers by classifying features on graphs.
abstract: BACKGROUND
  A central problem in biomarker discovery from large-scale gene expression or single nucleotide polymorphism (SNP) data is the computational challenge of taking into account the dependence among all the features. Methods that ignore the dependence usually identify non-reproducible biomarkers across independent datasets. We introduce a new graph-based semi-supervised feature classification algorithm to identify discriminative disease markers by learning on bipartite graphs. Our algorithm directly classifies the feature nodes in a bipartite graph as positive, negative or neutral with network propagation to capture the dependence among both samples and features (clinical and genetic variables) by exploring bi-cluster structures in a graph. Two features of our algorithm are: (1) our algorithm can find a global optimal labeling to capture the dependence among all the features and thus, generates highly reproducible results across independent microarray or other high-thoughput datasets, (2) our algorithm is capable of handling hundreds of thousands of features and thus, is particularly useful for biomarker identification from high-throughput gene expression and SNP data. In addition, although designed for classifying features, our algorithm can also simultaneously classify test samples for disease prognosis/diagnosis.
  
  
  RESULTS
  We applied the network propagation algorithm to study three large-scale breast cancer datasets. Our algorithm achieved competitive classification performance compared with SVMs and other baseline methods, and identified several markers with clinical or biological relevance with the disease. More importantly, our algorithm also identified highly reproducible marker genes and enriched functions from the independent datasets.
  
  
  BACKGROUND
  Supplementary results and source code are available at http://compbio.cs.umn.edu/Feature_Class.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science and Engineering, University of Minnesota, Twin Cities, Bioinformatics Core, Mayo Clinic College of Medicine, Rochester, MN, USA.
authors.forename: TaeHyun
authors.initials: T
authors.lastname: Hwang
authors.forename: Hugues
authors.initials: H
authors.lastname: Sicotte
authors.forename: Ze
authors.initials: Z
authors.lastname: Tian
authors.forename: Baolin
authors.initials: B
authors.lastname: Wu
authors.forename: Jean-Pierre
authors.initials: JP
authors.lastname: Kocher
authors.forename: Dennis A
authors.initials: DA
authors.lastname: Wigle
authors.forename: Vipin
authors.initials: V
authors.lastname: Kumar
authors.forename: Rui
authors.initials: R
authors.lastname: Kuang
mesh_terms: D000465:Algorithms; D014408:Biomarkers, Tumor / Q000737:chemistry / Q000235:genetics*; D001943:Breast Neoplasms / Q000235:genetics; D019295:Computational Biology / Q000379:methods; D030562:Databases, Protein; D005260:Female; D020869:Gene Expression Profiling / Q000379:methods*; D006801:Humans; D009363:Neoplasm Proteins / Q000235:genetics
chemical_list: D014408:Biomarkers, Tumor; D009363:Neoplasm Proteins