Domination based classification algorithms for the controllability analysis of biological interaction networks

Deciding the size of a minimum dominating set is a classic NP-complete problem. It has found increasing utility as the basis for classifying vertices in networks derived from protein–protein, noncoding RNA, metabolic, and other biological interaction data. In this context it can be helpful, for example, to identify those vertices that must be present in any minimum solution. Current classification methods, however, can require solving as many instances as there are vertices, rendering them computationally prohibitive in many applications. In an effort to address this shortcoming, new classification algorithms are derived and tested for efficiency and effectiveness. Results of performance comparisons on real-world biological networks are reported.