How to find Minimum dominating set in a biological network

Question

[Bioinformatist Newbie]

How we can find a Minimum Dominating Set (MDS) in a directed network in R?

Answer 1

[Kamil]

You might consider describing a specific scientific question. Perhaps searching for a minimum dominating set is one possible approach, but there might be alternative ways to address your question of interest.

This package may be interesting: https://cran.r-project.org/web/packages/cccd/

This paper might be of interest to you: http://dx.doi.org/10.1038/srep01736

Since finding the MDS is NP-hard, we approximate the exact solution by using a sequential greedy algorithm. Starting with an empty set, at each step the algorithm adds that node to which yields the largest increase in the number of dominated nodes in the network. When there are multiple candidate nodes yielding the maximal increase in domination, the algorithm chooses one randomly (uniformly among candidates). These steps continue until all nodes are dominated and then the algorithm terminates with storing the approximated MDS. The greedy algorithm yields a (1 + log N) approximation28 to the size of MDS, and has a time complexity of O(E). See the Supplementary Information for implementation details.