Finding a Maximum Common Subgraph from Molecular Structural Formulas through the Maximum Clique Approach Combined...

Area of Science:

• Computational Chemistry
• Drug Discovery
• Bioinformatics

Background:

• Neuraminidase inhibitors are vital antiviral medications for treating and preventing influenza A and B.
• Identifying common structural features among inhibitors can aid in the development of new antiviral drugs.
• The maximum common subgraph (MCS) problem is a key challenge in comparing chemical structures.

Purpose of the Study:

• To develop an efficient computational method for determining the maximum common subgraph (MCS) of neuraminidase inhibitors.
• To reduce the computational cost associated with MCS identification in antiviral drug structures.

Main Methods:

• The maximum common subgraph (MCS) was identified by finding the maximum clique in an association graph derived from chemical structures.
• The maximum clique problem was reformulated as an Ising Hamiltonian.
• Optimization techniques were applied to the Ising Hamiltonian formulation.

Main Results:

• A novel approach utilizing combined vertex labels (elemental species and chemical bonds) significantly reduced the number of vertices in the association graph.
• This reduction in graph complexity led to a decrease in computational cost for MCS determination.
• The method was successfully applied to four neuraminidase inhibitors.

Conclusions:

• The proposed method offers an efficient and computationally cost-effective way to find the maximum common subgraph (MCS) of neuraminidase inhibitors.
• This approach can facilitate the comparative analysis of antiviral drug structures and support the design of novel influenza therapeutics.