Paper Info
Title
Mining biological interaction networks using weighted quasi-bicliques
Abstract
Biological network studies can provide fundamental insights into various biological tasks including the functional characterization of genes and their products, the characterization of DNA-protein interactions, and the identification of regulatory mechanisms. However, biological networks are confounded with unreliable interactions and are incomplete, and thus, their computational exploitation is fraught with algorithmic challenges. Here we introduce quasi-biclique problems to analyze 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 provide exact IP solutions that can compute moderately sized networks. 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 the network.
Year
DOI
Venue
2011
10.1007/978-3-642-21260-4_40
ISBRA
Keywords
Field
DocType
various biological task,biological network,biological network study,previous quasi-biclique problem,biological interaction network,high quasi-biclique recall rate,biological interaction level,ip solution,edge-weighted quasi-bicliques,empirical data,quasi-biclique problem,bipartite graph,dna protein interaction,interaction network
Complete bipartite graph,Network motif,Computer science,Biological network,Bipartite graph,Theoretical computer science,Artificial intelligence,Bioinformatics,Machine learning
Conference
Volume
ISSN
Citations 
6674
0302-9743
2
PageRank 
References 
Authors
0.46
8
4
Name
Order
Citations
PageRank
Wen-Chieh Chang11197.15
Sudheer Vakati2243.98
Roland Krause37010.08
Oliver Eulenstein450552.71