Multi-node graphs

The model

In a “multi-node graph,” individual nodes may take on one more more states, and edges connecting nodes are dynamically activated or deactivated as a function of the state of the two incident nodes (Figure below.)   We can think of each pair of nodes (u,v) being associated with a binary edge matrix E_uv such that there is an active edge connecting the pair if E_uv[state(u), state(v)] = 1.   An assignment A={A₁, A_2, A_{3, ...,} A_n} induces a standard graph G_A.   Thus, to find a k-clique in a multi-node graph, we must identify a set of state assignments that induces a particular graph, GA, and then find the k-clique itself within the induced graph.





Applications

My research has been largely involved with the application of the multi-node graph formalism to applications in biotechnology and biological systems.  

Multiplex PCR

The PCR (Polymerase Chain Reaction) method of DNA amplification has had a profound impact on biotechnology and biological research.   Multiplex PCR is an extension of the standard PCR protocol in which multiple loci are amplified simultaneously in order to save time, improve throughput, and reduce the total cost of reagents.  Applications for PCR and Multiplex PCR abound including quantitative gene expression, haplotyping, whole-genome closure, detection of genetically modified organisms,  forensic analysis, including human identification and paternity testing diagnosis of infectious diseases, and for anti-bioterror applications aimed at detecting biological agents such as Anthrax.   Multiplex PCR presents certain challenges involving the requirement that selected primers for each loci be pair-wise compatible.   The problem of designing a set of k-plex assays can be modelled using multi-node graphs where nodes correspond to loci to be amplified, node states represent candidate primer pairs, and an edge is active if all of the primers are pairwise compatible, meaning that they could potentially be amplified within the same reaction tube.    Designing a set of k-plex reactions is thus equivalent to finding a set of disjoint k-cliques in a multi-node graph. 



Biological Context Networks (a special case of multi-node graphs)

Biological processes within the cell involve vastly complex networks of interaction among millions of biochemical entities.  Elucidation of the underlying architecture of such networks can provide incite into the way in which cellular processes respond to perturbations, chemical signals, or other environmental factors and is thus a major focus of current-day biomedical and pharmaceutical research.    A special case of multi-node graphs occurs if edges are disallowed for two nodes not currently sharing the same state or context.   (Two nodes in the same context may or may not have an edge between them.)   We call this special case of a multi-node graph a ‘context network’ and have demonstrated that they can be applied to the modelling of biological networks.  Biological context networks capture the fact that biochemical interactions are in reality mediated by specific contexts such as cellular location, tissue type, disease state, or structural modifications in the proteins themselves.   Such considerations allow one to identify an interesting class of proteins whose interacting partners tend to vary from one context to another.   Our research has shown that such “promiscuous proteins” are more likely to be essential to the viability of the cell, and may provide a computational basis for the selection of more specific drug targets.