Bipartite graph search optimization for type II diabetes mellitus Jamu formulation using branch and bound algorithm

Abstract

Jamu is an Indonesian traditional herbal medicine that has been practiced for generations. Jamu is made from various medicinal plants. Each plant has several compounds directly related to the target protein that are directly associated with a disease. A pharmacological graph can form relationships between plants, compounds, and target proteins. Research related to the prediction of Jamu formulas for some diseases has been carried out, but there are problems in finding combinations or compositions of Jamu formulas because of the increase in search space size. Some studies adopted the drug-target interaction (DTI) implemented using machine learning or deep learning to predict the DTI for discovering the Jamu formula. However, this approach raises important issues, such as imbalanced and high-dimensional dataset, overfitting, and the need for more procedures to trace compounds to their plants. This study proposes an alternative approach by implementing bipartite graph search optimization using the branch and bound algorithm to discover the combination or composition of Jamu formulas by optimizing the search on a plant-protein bipartite graph. The branch and bound technique is implemented using the search strategy of breadth first search (BrFS), Depth First Search, and Best First Search. To show the performance of the proposed method, we compared our method with a complete search algorithm, searching all nodes in the tree without pruning. In this study, we specialize in applying the proposed method to search for the Jamu formula for type II diabetes mellitus (T2DM). The result shows that the bipartite graph search with the branch and bound algorithm reduces computation time up to 40 times faster than the complete search strategy to search for a composition of plants. The binary branching strategy is the best choice, whereas the BrFS strategy is the best option in this research. In addition, the the proposed method can suggest the composition of one to four plants for the T2DM Jamu formula. For a combination of four plants, we obtain Angelica Sinensis, Citrus aurantium, Glycyrrhiza uralensis, and Mangifera indica. This approach is expected to be an alternative way to discover the Jamu formula more accurately.

Keywords: branch and bound; diabetes mellitus; drug–target interaction; graph traversing; jamu.

FIGURE 1

Illustration of three networks of plants, compounds, and proteins, respectively represented by T, C, and P. We define three networks from different databases to get the relationship between plants and protein. Network A connects plants from KNApSAcK, compounds from KNApSAcK and PubChem, and proteins from PubChem BioAssay. Network B connects compounds in network A, compounds in network B taken from ChemmineTools, and the target protein is the same as that in Network A. Network C connects proteins from Usman et al. (2020), proteins from Uniprot, and compounds from PubChem BioAssay.

FIGURE 2

Searching strategy (Morrison et al., 2016)

FIGURE 3

Branching strategy (Morrison et al., 2016)

FIGURE 4

Data with weight and profit.

FIGURE 5

Lower bounds pruning rule.

FIGURE 6

Use of the queue data structure in tree tracing.

FIGURE 7

Use of the stack data structure on the tree.

FIGURE 8

Priority queue with (binary) heap tree.

FIGURE 9

Wide branching strategy.

FIGURE 10

Comparison of search space area in log(n) units.