paperKB
coga / coga-kb
Help
Sign in

Chunk #16 — Methods — Paraclique formation and network analysis

Source
Genetic dissection of acute ethanol responsive gene networks in prefrontal cortex: functional and mechanistic implications.
Embedded
yes

Text

The most natural grouping of vertices in a graph is by cliques, or fully connected subgraphs. While finding the maximum clique is a well-known computationally intractable problem, being NP-complete, the topology of biological graphs lends itself to solution by advanced algorithmic implementations [33], [34]. Since the inevitable noise in large microarray datasets can render clique too restrictive, we used a relaxed version termed a “paraclique”. For graphs constructed using a correlation threshold, we iteratively extracted maximum cliques and used them as cores to build paracliques. A paraclique starts with a maximum clique and gloms onto all vertices with at least some proportion of edges to that clique. This proportion is called the “proportional glom factor.” As a paraclique was formed, the number of edges that must be present for a vertex to be included was scaled to the size of the starting clique. We selected a glom factor of 0.7 for the analyses presented here, which maintains an edge density >90% in nearly all the resulting paracliques. For such defined paracliques, probe-sets had expression responses to ethanol correlated with at