Open AccessConstraint‐based models for dominating protein interaction networks
Author(s) -
Alofairi Adel A.,
Mabrouk Emad,
Elsemman Ibrahim E.
Publication year - 2021
Publication title -
iet systems biology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.367
H-Index - 50
eISSN - 1751-8857
pISSN - 1751-8849
DOI - 10.1049/syb2.12021
Subject(s) - biological network , computer science , graph , set (abstract data type) , constraint (computer aided design) , dominating set , graph theory , theoretical computer science , mathematics , combinatorics , geometry , programming language , vertex (graph theory)
The minimum dominating set (MDSet) comprises the smallest number of graph nodes, where other graph nodes are connected with at least one MDSet node. The MDSet has been successfully applied to extract proteins that control protein–protein interaction (PPI) networks and to reveal the correlation between structural analysis and biological functions. Although the PPI network contains many MDSets, the identification of multiple MDSets is an NP‐complete problem, and it is difficult to determine the best MDSets, enriched with biological functions. Therefore, the MDSet model needs to be further expanded and validated to find constrained solutions that differ from those generated by the traditional models. Moreover, by identifying the critical set of the network, the set of nodes common to all MDSets can be time‐consuming. Herein, the authors adopted the minimisation of metabolic adjustment (MOMA) algorithm to develop a new framework, called maximisation of interaction adjustment (MOIA). In MOIA, they provide three models; the first one generates two MDSets with a minimum number of shared proteins, the second model generates constrained multiple MDSets ( k ‐MDSets), and the third model generates user‐defined MDSets, containing the maximum number of essential genes and/or other important genes of the PPI network. In practice, these models significantly reduce the cost of finding the critical set and classifying the graph nodes. Herein, the authors termed the critical set as the k ‐critical set, where k is the number of MDSets generated by the proposed model. Then, they defined a new set of proteins called the ( k − 1 ) ‐critical set, where each node belongs to ( k − 1 ) MDSets. This set has been shown to be as important as the k ‐critical set and contains many essential genes, transcription factors, and protein kinases as the k ‐critical set. The ( k − 1 ) ‐critical set can be used to extend the search for drug target proteins. Based on the performance of the MOIA models, the authors believe the proposed methods contribute to answering key questions about the MDSets of PPI networks, and their results and analysis can be extended to other network types.