title: Exploring biological interaction networks with tailored weighted quasi-bicliques.
abstract: BACKGROUND
  Biological networks provide fundamental insights into the functional characterization of genes and their products, the characterization of DNA-protein interactions, the identification of regulatory mechanisms, and other biological tasks. Due to the experimental and biological complexity, their computational exploitation faces many algorithmic challenges.
  
  
  RESULTS
  We introduce novel weighted quasi-biclique problems to identify functional modules in biological networks when represented by bipartite graphs. In difference to previous quasi-biclique problems, we include biological interaction levels by using edge-weighted quasi-bicliques. While we prove that our problems are NP-hard, we also describe IP formulations to compute exact solutions for moderately sized networks.
  
  
  CONCLUSIONS
  We verify the effectiveness of our IP solutions using both simulation and empirical data. The simulation shows high quasi-biclique recall rates, and the empirical data corroborate the abilities of our weighted quasi-bicliques in extracting features and recovering missing interactions from biological networks.
authors: Department of Computer Science, Iowa State University, Ames, IA 50011, USA.
authors: Wen-Chieh
authors: WC
authors: Chang
authors: Sudheer
authors: S
authors: Vakati
authors: Roland
authors: R
authors: Krause
authors: Oliver
authors: O
authors: Eulenstein
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D057225:Data Mining; D053263:Gene Regulatory Networks; D053858:Metabolic Networks and Pathways; D008962:Models, Theoretical; D049490:Systems Biology / Q000379:methods*