Exploring biological interaction networks with tailored weighted quasi-bicliques

Wen-Chieh Chang; Vakati, Sudheer; Krause, Roland; Eulenstein, Oliver
January 2012
BMC Bioinformatics;2012, Vol. 13 Issue Suppl 10, p1
Academic Journal
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 NPhard, 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.


Related Articles

  • Electrochemical Stripping Techniques in Analysis of Nucleic Acids and their Constituents. Fojta, Miroslav; Jelen, František; Havran, Luděk; Paleček, Emil // Current Analytical Chemistry;Jul2008, Vol. 4 Issue 3, p250 

    The ability of nucleic acids (NA) and their components to accumulate at electrode surfaces and electrochemical properties of these species are closely related. This review is devoted to electrochemical stripping techniques applied in NA studies. Cathodic or anodic stripping voltammetry have been...

  • CATCHprofiles: Clustering and Alignment Tool for ChIP Profiles. Nielsen, Fiona G. G.; Markus, Kasper Galschiøt; Friborg, Rune Møllegaard; Favrholdt, Lene Monrad; Stunnenberg, Hendrik G.; Huynen, Martijn // PLoS ONE;Jan2012, Vol. 7 Issue 1, p1 

    Chromatin Immuno Precipitation (ChIP) profiling detects in vivo protein-DNA binding, and has revealed a large combinatorial complexity in the binding of chromatin associated proteins and their post-translational modifications. To fully explore the spatial and combinatorial patterns in...

  • Challenge of Pigs with Classical Swine Fever Viruses after C-Strain Vaccination Reveals Remarkably Rapid Protection and Insights into Early Immunity. Graham, Simon P.; Everett, Helen E.; Haines, Felicity J.; Johns, Helen L.; Sosan, Olubukola A.; Salguero, Francisco J.; Clifford, Derek J.; Steinbach, Falko; Drew, Trevor W.; Crooke, Helen R. // PLoS ONE;Jan2012, Vol. 7 Issue 1, p1 

    Pre-emptive culling is becoming increasingly questioned as a means of controlling animal diseases, including classical swine fever (CSF). This has prompted discussions on the use of emergency vaccination to control future CSF outbreaks in domestic pigs. Despite a long history of safe use in...

  • Understanding the Sequence-Dependence of DNA Groove Dimensions: Implications for DNA Interactions. Oguey, Christophe; Foloppe, Nicolas; Hartmann, Brigitte // PLoS ONE;2010, Vol. 5 Issue 12, p1 

    Background: The B-DNA major and minor groove dimensions are crucial for DNA-protein interactions. It has long been thought that the groove dimensions depend on the DNA sequence, however this relationship has remained elusive. Here, our aim is to elucidate how the DNA sequence intrinsically...

  • Complete Cototal Domination Number of a Graph. Basavanagoud, B.; Hosamani, S. M. // Journal of Scientific Research;2011, Vol. 3 Issue 3, p547 

    Let G = (V, E) be a graph. A set D ⊆ V of a graph G = (V,E) is called a total dominating set if the induced subgraph has no isolated vertices. The total domination number γt (G) of G is the minimum cardinality of a total dominating set of G. A total dominating set D is said to be a...

  • ON MULTISET COLORINGS OF GRAPHS. Okamoto, Futaba; Salehi, Ebrahim; Ping Zhang // Discussiones Mathematicae: Graph Theory;2010, Vol. 30 Issue 1, p137 

    A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χm(G) of G. For every graph G, χmm(G) is bounded above by...

  • Trivalent 2-Arc Transitive Graphs of Type $${G^1_2}$$ are Near Polygonal. Sanming Zhou // Annals of Combinatorics;Sep2010, Vol. 14 Issue 3, p397 

    connected graph S of girth at least four is called a near n-gonal graph with respect to E, where n = 4 is an integer, if E is a set of n-cycles of S such that every path of length two is contained in a unique member of E. It is well known that connected trivalent symmetric graphs can be...

  • Independent sets in (P6,diamond)-free graphs. Mosca, Raffaela // Discrete Mathematics & Theoretical Computer Science (DMTCS);Jun2009, Vol. 11 Issue 1, p125 

    We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

  • An improved bound on the largest induced forests for triangle-free planar graphs. Kowalik, Lukasz; Lu�ar, Borut; �krekovski, Riste // Discrete Mathematics & Theoretical Computer Science (DMTCS);Jan2010, Vol. 12 Issue 1, p87 

    We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics