An exact algorithm to find a maximum weight clique in a weighted undirected graph.

We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.

Protein binding sites for drug design.

Drug development is a lengthy and challenging process that can be accelerated at early stages by new mathematical approaches and modern computers. To address this important issue, we are developing new mathematical solutions for the detection and characterization of protein binding sites that are important for new drug development. In this review, we present algorithms based on graph theory combined with molecular dynamics simulations that we have developed for studying biological target proteins to provide important data for optimizing the early stages of new drug development. A particular focus is the development of new protein binding site prediction algorithms (ProBiS) and new web tools for modeling pharmaceutically interesting molecules-ProBiS Tools (algorithm, database, web server), which have evolved into a full-fledged graphical tool for studying proteins in the proteome. ProBiS differs from other structural algorithms in that it can align proteins with different folds without prior knowledge of the binding sites. It allows detection of similar binding sites and can predict molecular ligands of various types of pharmaceutical interest that could be advanced to drugs to treat a disease, based on the entire Protein Data Bank (PDB) and AlphaFold database, including proteins not yet in the PDB. All ProBiS Tools are freely available to the academic community at http://insilab.org and https://probis.nih.gov.

ProBiS-Fold Approach for Annotation of Human Structures from the AlphaFold Database with No Corresponding Structure in the PDB to Discover New Druggable Binding Sites.

ProBiS (Protein Binding Sites), a local structure-based comparison algorithm, is used in the new ProBiS-Fold web server to annotate human structures from the AlphaFold database without a corresponding structure in the Protein Data Bank (PDB) to discover new druggable binding sites. The ProBiS algorithm is used to compare each query protein structure predicted by the AlphaFold approach with the protein structures from the PDB to identify similarities between known binding sites found in the PDB and yet unknown binding sites in the AlphaFold database. Ligands bound in these identified similar PDB sites are then transferred to each query protein from the AlphaFold database, and binding sites are identified as ligand clusters on an AlphaFold protein. Small molecule binding sites are assigned druggability scores based on the similarity of their ligands to known drugs, allowing them to be ranked according to their perceived and actual potential for drug development. ProBiS-Fold provides interactive and downloadable binding sites for the entire human structural proteome, including more than 3000 new druggable binding sites that have no corresponding structure in the PDB, taking into account AlphaFold's model quality, to enable protein structure-function relationship studies and pharmaceutical drug discovery research. The web server is freely accessible to academic users at http://probis-fold.insilab.org.

ProBiS-Dock: A Hybrid Multitemplate Homology Flexible Docking Algorithm Enabled by Protein Binding Site Comparison.

The protein data bank (PDB) is a rich source of protein ligand structures, but ligands are not explicitly used in current docking algorithms. We have developed ProBiS-Dock, a docking algorithm complementary to the ProBiS-Dock Database (J. Chem. Inf. Model. 2021, 61, 4097-4107) that treats small molecules and proteins as fully flexible entities and allows conformational changes in both after ligand binding. A new scoring function is described that consists of a binding site-specific scoring function (ProBiS-Score) and a general statistical scoring function. ProBiS-Dock enables rapid docking of small molecules to proteins and has been successfully validated in silico against standard benchmarks. It enables rapid search for new active ligands by leveraging existing knowledge in the PDB. The potential of the software for drug development has been confirmed in vitro by the discovery of new inhibitors of human indoleamine 2,3-dioxygenase 1, an enzyme that is an attractive target for cancer therapy and catalyzes the first rate-determining step of l-tryptophan metabolism via the kynurenine pathway. The software is freely available to academic users at http://insilab.org/probisdock.

Automatic Assembly and Calibration of Models of Enzymatic Reactions Based on Ordinary Differential Equations.

Enzymatic reactions have been studied for more than a 100 years. Indeed, isolation of enzymes from biological materials is no longer the main source of enzymes today, as they are now largely produced using recombinant technology, or can even be synthesized from scratch. Studies of the three-dimensional structures of enzymes can provide answers to many questions, but the kinetics of enzymatic reactions is the only method that can lead to better understanding of their function. The complexity of high-throughput analysis of progress curves of data obtained can only be achieved through numerical solutions of a suitable system of ordinary differential equations. We have developed the freely available server ENZO: a web tool for derivation and evaluation of kinetic models of enzyme-catalyzed reactions ( http://enzo.cmm.ki.si/ ). ENZO can be used for simultaneous analysis of a series of progress curves obtained under many different conditions. In this chapter, we exemplify the principles and possibilities of this type of high-throughput analysis.

Potential Novel Thioether-Amide or Guanidine-Linker Class of SARS-CoV-2 Virus RNA-Dependent RNA Polymerase Inhibitors Identified by High-Throughput Virtual Screening Coupled to Free-Energy Calculations.

SARS-CoV-2, or severe acute respiratory syndrome coronavirus 2, represents a new pathogen from the family of Coronaviridae that caused a global pandemic of COVID-19 disease. In the absence of effective antiviral drugs, research of novel therapeutic targets such as SARS-CoV-2 RNA-dependent RNA polymerase (RdRp) becomes essential. This viral protein is without a human counterpart and thus represents a unique prospective drug target. However, in vitro biological evaluation testing on RdRp remains difficult and is not widely available. Therefore, we prepared a database of commercial small-molecule compounds and performed an in silico high-throughput virtual screening on the active site of the SARS-CoV-2 RdRp using ensemble docking. We identified a novel thioether-amide or guanidine-linker class of potential RdRp inhibitors and calculated favorable binding free energies of representative hits by molecular dynamics simulations coupled with Linear Interaction Energy calculations. This innovative procedure maximized the respective phase-space sampling and yielded non-covalent inhibitors representing small optimizable molecules that are synthetically readily accessible, commercially available as well as suitable for further biological evaluation and mode of action studies.

Molecular Dynamics Simulations Reveal Interactions of an IgG1 Antibody With Selected Fc Receptors.

In a survey of novel interactions between an IgG1 antibody and different Fcγ receptors (FcγR), molecular dynamics simulations were performed of interactions of monoclonal antibody involved complexes with FcγRs. Free energy simulations were also performed of isolated wild-type and substituted Fc regions bound to FcγRs with the aim of assessing their relative binding affinities. Two different free energy calculation methods, Molecular Mechanical/Generalized Born Molecular Volume (MM/GBMV) and Bennett Acceptance Ratio (BAR), were used to evaluate the known effector substitution G236A that is known to selectively increase antibody dependent cellular phagocytosis. The obtained results for the MM/GBMV binding affinity between different FcγRs are in good agreement with previous experiments, and those obtained using the BAR method for the complete antibody and the Fc-FcγR simulations show increased affinity across all FcγRs when binding to the substituted antibody. The FcγRIIa, a key determinant of antibody agonistic efficacy, shows a 10-fold increase in binding affinity, which is also consistent with the published experimental results. Novel interactions between the Fab region of the antibody and the FcγRs were discovered with this in silico approach, and provide insights into the antibody-FcγR binding mechanism and show promise for future improvements of therapeutic antibodies for preclinical studies of biological drugs.

ProBiS-Dock Database: A Web Server and Interactive Web Repository of Small Ligand-Protein Binding Sites for Drug Design.

We have developed a new system, ProBiS-Dock, which can be used to determine the different types of protein binding sites for small ligands. The binding sites identified this way are then used to construct a new binding site database, the ProBiS-Dock Database, that allows for the ranking of binding sites according to their utility for drug development. The newly constructed database currently has more than 1.4 million binding sites and offers the possibility to investigate potential drug targets originating from different biological species. The interactive ProBiS-Dock Database, a web server and repository that consists of all small-molecule ligand binding sites in all of the protein structures in the Protein Data Bank, is freely available at http://probis-dock-database.insilab.org. The ProBiS-Dock Database will be regularly updated to keep pace with the growth of the Protein Data Bank, and our anticipation is that it will be useful in drug discovery.

Repurposing of Drugs for SARS-CoV-2 Using Inverse Docking Fingerprints.

Severe acute respiratory syndrome coronavirus 2 or SARS-CoV-2 is a virus that belongs to the Coronaviridae family. This group of viruses commonly causes colds but possesses a tremendous pathogenic potential. In humans, an outbreak of SARS caused by the SARS-CoV virus was first reported in 2003, followed by 2012 when the Middle East respiratory syndrome coronavirus (MERS-CoV) led to an outbreak of Middle East respiratory syndrome (MERS). Moreover, COVID-19 represents a serious socioeconomic and global health problem that has already claimed more than four million lives. To date, there are only a handful of therapeutic options to combat this disease, and only a single direct-acting antiviral, the conditionally approved remdesivir. Since there is an urgent need for active drugs against SARS-CoV-2, the strategy of drug repurposing represents one of the fastest ways to achieve this goal. An in silico drug repurposing study using two methods was conducted. A structure-based virtual screening of the FDA-approved drug database on SARS-CoV-2 main protease was performed, and the 11 highest-scoring compounds with known 3CLpro activity were identified while the methodology was used to report further 11 potential and completely novel 3CLpro inhibitors. Then, inverse molecular docking was performed on the entire viral protein database as well as on the Coronaviridae family protein subset to examine the hit compounds in detail. Instead of target fishing, inverse docking fingerprints were generated for each hit compound as well as for the five most frequently reported and direct-acting repurposed drugs that served as controls. In this way, the target-hitting space was examined and compared and we can support the further biological evaluation of all 11 newly reported hits on SARS-CoV-2 3CLpro as well as recommend further in-depth studies on antihelminthic class member compounds. The authors acknowledge the general usefulness of this approach for a full-fledged inverse docking fingerprint screening in the future.

Ensemble Docking Coupled to Linear Interaction Energy Calculations for Identification of Coronavirus Main Protease (3CLpro) Non-Covalent Small-Molecule Inhibitors.

SARS-CoV-2, or severe acute respiratory syndrome coronavirus 2, represents a new strain of Coronaviridae. In the closing 2019 to early 2020 months, the virus caused a global pandemic of COVID-19 disease. We performed a virtual screening study in order to identify potential inhibitors of the SARS-CoV-2 main viral protease (3CLpro or Mpro). For this purpose, we developed a novel approach using ensemble docking high-throughput virtual screening directly coupled with subsequent Linear Interaction Energy (LIE) calculations to maximize the conformational space sampling and to assess the binding affinity of identified inhibitors. A large database of small commercial compounds was prepared, and top-scoring hits were identified with two compounds singled out, namely 1-[(R)-2-(1,3-benzimidazol-2-yl)-1-pyrrolidinyl]-2-(4-methyl-1,4-diazepan-1-yl)-1-ethanone and [({(S)-1-[(1H-indol-2-yl)methyl]-3-pyrrolidinyl}methyl)amino](5-methyl-2H-pyrazol-3-yl)formaldehyde. Moreover, we obtained a favorable binding free energy of the identified compounds, and using contact analysis we confirmed their stable binding modes in the 3CLpro active site. These compounds will facilitate further 3CLpro inhibitor design.

ProBiS H2O MD Approach for Identification of Conserved Water Sites in Protein Structures for Drug Design.

The ProBiS H2O MD approach for identification of conserved waters and water sites of interest in macromolecular systems, which is becoming a typical step in a structure-based drug design or macromolecular study in general, is described. This work explores an extension of the ProBiS H2O approach introduced by Jukic et al. Indeed, water molecules are key players in the interaction mechanisms of macromolecules and small molecules and play structural roles. Our earlier developed approach, ProBiS H2O, is a simple and transparent workflow for conserved water detection. Here we have considered generalizing the idea by supplementing the experimental data with data derived from molecular dynamics to facilitate work on less known systems. Newly developed ProBiS H2O MD workflow uses trajectory data, extracts and identifies interesting water sites, and visualizes the results. ProBiS H2O MD can thus robustly process molecular dynamic trajectory snapshots, perform local superpositions, collect water location data, and perform density-based clustering to identify discrete sites with high conservation of water molecules. This is a new approach that uses experimental data in silico to identify interesting water sites. Methodology is fast and water-model or molecular dynamics software independent. Trends in the conservation of water molecules can be followed over a variety of trajectories, and our approach has been successfully validated using reported protein systems with experimentally observed conserved water molecules. ProBiS H2O MD is freely available as PyMOL plugin at http://insilab.org.

Sugars and Sweeteners: Structure, Properties and In Silico Modeling.

Several studies report the effects of excessive use of sugars and sweeteners in the diet. These include obesity, cardiac diseases, diabetes, and even lymphomas, leukemias, cancers of the bladder and brain, chronic fatigue syndrome, Parkinson's disease, Alzheimer's disease, multiple sclerosis, autism, and systemic lupus. On the other hand, each sugar and sweetener has a distinct metabolic assimilation process, and its chemical structure plays an important role in this process. Several scientific papers present the biological effects of the sugars and sweeteners in relation to their chemical structure. One important issue dealing with the sugars is the degree of similarity in their structures, focusing mostly on optical isomerism. Finding and developing new sugars and sweeteners with desired properties is an emerging research area, in which in silico approaches play an important role.

Discovery of Novel Potential Human Targets of Resveratrol by Inverse Molecular Docking.

Resveratrol is a polyphenol known for its antioxidant and anti-inflammatory properties, which support its use as a treatment for variety of diseases. There are already known connections of resveratrol to chemoprevention of cancer because of its ability to prevent tumor initiation and inhibit tumor promotion and progression. Resveratrol is also believed to be important in cardiovascular diseases and neurological disorders, such as Alzheimer's disease. Using an inverse molecular docking approach, we sought to find new potential targets of resveratrol. Docking of resveratrol into each ProBiS predicted binding site of >38 000 protein structures from the Protein Data Bank was examined, and a number of novel potential targets into which resveratrol was docked successfully were found. These explain known actions or predict new effects of resveratrol. The results included three human proteins that are already known to bind resveratrol. A majority of proteins discovered however have no already described connections with resveratrol. We report new potential target human proteins and proteins connected with different organisms into which resveratrol can dock. Our results reveal previously unknown potential target human proteins, whose connection with cardiovascular and neurological disorders could lead to new potential treatments for variety of diseases. We believe that our research could help in future experimental studies on revestratol bioactivity in humans.

BoBER: web interface to the base of bioisosterically exchangeable replacements.

We describe a novel freely available web server Base of Bioisosterically Exchangeable Replacements (BoBER), which implements an interface to a database of bioisosteric and scaffold hopping replacements. Bioisosterism and scaffold hopping are key concepts in drug design and optimization, and can be defined as replacements of biologically active compound's fragments with other fragments to improve activity, reduce toxicity, change bioavailability or to diversify the scaffold space. Our web server enables fast and user-friendly searches for bioisosteric and scaffold replacements which were obtained by mining the whole Protein Data Bank. The working of the web server is presented on an existing MurF inhibitor as example. BoBER web server enables medicinal chemists to quickly search for and get new and unique ideas about possible bioisosteric or scaffold hopping replacements that could be used to improve hit or lead drug-like compounds.

Identification of Conserved Water Sites in Protein Structures for Drug Design.

Identification of conserved waters in protein structures is a challenging task with applications in molecular docking and protein stability prediction. As an alternative to computationally demanding simulations of proteins in water, experimental cocrystallized waters in the Protein Data Bank (PDB) in combination with a local structure alignment algorithm can be used for reliable prediction of conserved water sites. We developed the ProBiS H2O approach based on the previously developed ProBiS algorithm, which enables identification of conserved water sites in proteins using experimental protein structures from the PDB or a set of custom protein structures available to the user. With a protein structure, a binding site, or an individual water molecule as a query, ProBiS H2O collects similar proteins from the PDB and performs local or binding site-specific superimpositions of the query structure with similar proteins using the ProBiS algorithm. It collects the experimental water molecules from the similar proteins and transposes them to the query protein. Transposed waters are clustered by their mutual proximity, which enables identification of discrete sites in the query protein with high water conservation. ProBiS H2O is a robust and fast new approach that uses existing experimental structural data to identify conserved water sites on the interfaces of protein complexes, for example protein-small molecule interfaces, and elsewhere on the protein structures. It has been successfully validated in several reported proteins in which conserved water molecules were found to play an important role in ligand binding with applications in drug design.

Global organization of a binding site network gives insight into evolution and structure-function relationships of proteins.

The global organization of protein binding sites is analyzed by constructing a weighted network of binding sites based on their structural similarities and detecting communities of structurally similar binding sites based on the minimum description length principle. The analysis reveals that there are two central binding site communities that play the roles of the network hubs of smaller peripheral communities. The sizes of communities follow a power-law distribution, which indicates that the binding sites included in larger communities may be older and have been evolutionary structural scaffolds of more recent ones. Structurally similar binding sites in the same community bind to diverse ligands promiscuously and they are also embedded in diverse domain structures. Understanding the general principles of binding site interplay will pave the way for improved drug design and protein design.

GenProBiS: web server for mapping of sequence variants to protein binding sites.

Discovery of potentially deleterious sequence variants is important and has wide implications for research and generation of new hypotheses in human and veterinary medicine, and drug discovery. The GenProBiS web server maps sequence variants to protein structures from the Protein Data Bank (PDB), and further to protein-protein, protein-nucleic acid, protein-compound, and protein-metal ion binding sites. The concept of a protein-compound binding site is understood in the broadest sense, which includes glycosylation and other post-translational modification sites. Binding sites were defined by local structural comparisons of whole protein structures using the Protein Binding Sites (ProBiS) algorithm and transposition of ligands from the similar binding sites found to the query protein using the ProBiS-ligands approach with new improvements introduced in GenProBiS. Binding site surfaces were generated as three-dimensional grids encompassing the space occupied by predicted ligands. The server allows intuitive visual exploration of comprehensively mapped variants, such as human somatic mis-sense mutations related to cancer and non-synonymous single nucleotide polymorphisms from 21 species, within the predicted binding sites regions for about 80 000 PDB protein structures using fast WebGL graphics. The GenProBiS web server is open and free to all users at http://genprobis.insilab.org.

ProBiS tools (algorithm, database, and web servers) for predicting and modeling of biologically interesting proteins.

ProBiS (Protein Binding Sites) Tools consist of algorithm, database, and web servers for prediction of binding sites and protein ligands based on the detection of structurally similar binding sites in the Protein Data Bank. In this article, we review the operations that ProBiS Tools perform, provide comments on the evolution of the tools, and give some implementation details. We review some of its applications to biologically interesting proteins. ProBiS Tools are freely available at http://probis.cmm.ki.si and http://probis.nih.gov.

Discovery of new MurA inhibitors using induced-fit simulation and docking.

We report on the successful application of ProBiS-CHARMMing web server in the discovery of new inhibitors of MurA, an enzyme that catalyzes the first committed cytoplasmic step of bacterial peptidoglycan synthesis. The available crystal structures of Escherichia coli MurA in the Protein Data Bank have binding sites whose small volume does not permit the docking of drug-like molecules. To prepare the binding site for docking, the ProBiS-CHARMMing web server was used to simulate the induced-fit effect upon ligand binding to MurA, resulting in a larger, more holo-like binding site. The docking of a filtered ZINC compound library to this enlarged binding site was then performed and resulted in three compounds with promising inhibitory potencies against MurA. Compound 1 displayed significant inhibitory potency with IC50 value of 1µM. All three compounds have novel chemical structures, which could be used for further optimization of small-molecule MurA inhibitors.

Discovery of Mycobacterium tuberculosis InhA Inhibitors by Binding Sites Comparison and Ligands Prediction.

Drug discovery is usually focused on a single protein target; in this process, existing compounds that bind to related proteins are often ignored. We describe ProBiS plugin, extension of our earlier ProBiS-ligands approach, which for a given protein structure allows prediction of its binding sites and, for each binding site, the ligands from similar binding sites in the Protein Data Bank. We developed a new database of precalculated binding site comparisons of about 290000 proteins to allow fast prediction of binding sites in existing proteins. The plugin enables advanced viewing of predicted binding sites, ligands' poses, and their interactions in three-dimensional graphics. Using the InhA query protein, an enoyl reductase enzyme in the Mycobacterium tuberculosis fatty acid biosynthesis pathway, we predicted its possible ligands and assessed their inhibitory activity experimentally. This resulted in three previously unrecognized inhibitors with novel scaffolds, demonstrating the plugin's utility in the early drug discovery process.