Hello everyone!
I am currently dealing with some transcriptomic data and building protein-protein interaction (PPI) networks. After filtering my data by fold-change and p-value, I got quite a lot disconnected nodes in my PPI network. So I would like to expand my current network through a whole-genome network (as a template) in order to connect the maximum number of single nodes. The main assumption is that not all proteins being at play in a biologic response will show a change in their transcript level, and that up-regulated proteins may interact with partners (yet present, and unmodified during the biological response). My goal, thus, is to connect the maximum amount of query nodes with the minimum amount of newly added nodes.
The STRING database has an option of "adding more nodes to the current network", but it usually enriches current clusters rather than connecting single nodes (or at least it seems to me). However I don't know what strategy does STRING follow to choose nodes to be added. So, what would be the best network expansion strategy to connect single nodes?
Thanks in advanced!
You may start deducing a proteome wide graph connecting all genes of your study using, say STRING, germania, or whatnot.
Then, you can identify in the graph the genes of interest by fold-change/p-value considerations. You could search for a minimum spanning tree throughout the graph covering all these genes.
This is called the Steiner tree problem, which is NP-hard.
networkx provides an approximation algorithm to solve it.
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.steinertree.steiner_tree.html
Dear Dr. Mazza, thanks for your insight! It is always useful to name a problem in order to find a solution. I have been implementing the steiner tree problem approach upon my data with the R function steinertree (from SteinerNET package), and succesfully connected all my nodes. However, lots of nodes have been added in between, as some of my single nodes seem to be far from each other. The other approach I considered is to run the heat diffusion algorithm (from Cytoscape), in order to diffuse my query nodes through the whole interactome network, and then apply a heat diffusion coefficient threshold to subnetwork. In this way I may connect my single nodes to their neighbors, and obtain an expanded network with several modules (perhaps not connected in between). Any thoughts on this approach?
Yes, it is another way to tackle the problem. However, I am not sure that the number of added nodes is generally lower than those added with the former solution since it strictly depends on the network topology. In my opinion, if you can tolerate the number of extra nodes to keep the global nodal closeness low, then this is one way to go. Network propagation algorithms find wide applicability on DEG analysis and network biology anyway.
On the contrary, I'd use a Steiner tree to guarantee reachability and (globally) shortest paths between my nodes. I don't know how you implemented the solution mentioned above, but I'd have assigned low weights on edges connecting my nodes of interests and high weights to penalize all other edges. In this way, you will force the algorithm to prefer connections between your differentially expressed nodes, thereby resorting to the others secondarily.
From your first message, it is unclear what your (biological) purposes are, but one of these two settings should definitely help.
Article Network propagation in the cytoscape cyberinfrastructure
- Badges
- Science topic
- Similar topics
- Biological Science
- Bioecology
- Systems Ecology
- Landscape Ecology
- Connectivity