Combining fragment docking with graph theory to improve ligand docking for homology model structures.

Computational protein-ligand docking is well-known to be prone to inaccuracies in input receptor structures, and it is challenging to obtain good docking results with computationally predicted receptor structures (e.g. through homology modeling). Here we introduce a fragment-based docking method and test if it reduces requirements on the accuracy of an input receptor structures relative to non-fragment docking approaches. In this method, small rigid fragments are docked first using AutoDock Vina to generate a large number of favorably docked poses spanning the receptor binding pocket. Then a graph theory maximum clique algorithm is applied to find combined sets of docked poses of different fragment types onto which the complete ligand can be properly aligned. On the basis of these alignments, possible binding poses of complete ligand are determined. This docking method is first tested for bound docking on a series of Cytochrome P450 (CYP450) enzyme-substrate complexes, in which experimentally determined receptor structures are used. For all complexes tested, ligand poses of less than 1 Å root mean square deviations (RMSD) from the actual binding positions can be recovered. Then the method is tested for unbound docking with modeled receptor structures for a number of protein-ligand complexes from different families including the very recent severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) protease. For all complexes, poses with RMSD less than 3 Å from actual binding positions can be recovered. Our results suggest that for docking with approximately modeled receptor structures, fragment-based methods can be more effective than common complete ligand docking approaches.

Molecular Sticker Model Stimulation on Silicon for a Maximum Clique Problem.

Molecular computers (also called DNA computers), as an alternative to traditional electronic computers, are smaller in size but more energy efficient, and have massive parallel processing capacity. However, DNA computers may not outperform electronic computers owing to their higher error rates and some limitations of the biological laboratory. The stickers model, as a typical DNA-based computer, is computationally complete and universal, and can be viewed as a bit-vertically operating machine. This makes it attractive for silicon implementation. Inspired by the information processing method on the stickers computer, we propose a novel parallel computing model called DEM (DNA Electronic Computing Model) on System-on-a-Programmable-Chip (SOPC) architecture. Except for the significant difference in the computing medium--transistor chips rather than bio-molecules--the DEM works similarly to DNA computers in immense parallel information processing. Additionally, a plasma display panel (PDP) is used to show the change of solutions, and helps us directly see the distribution of assignments. The feasibility of the DEM is tested by applying it to compute a maximum clique problem (MCP) with eight vertices. Owing to the limited computing sources on SOPC architecture, the DEM could solve moderate-size problems in polynomial time.

Graph-based relevancy-redundancy gene selection method for cancer diagnosis.

Nowadays, microarray data processing is one of the most important applications in molecular biology for cancer diagnosis. A major task in microarray data processing is gene selection, which aims to find a subset of genes with the least inner similarity and most relevant to the target class. Removing unnecessary, redundant, or noisy data reduces the data dimensionality. This research advocates a graph theoretic-based gene selection method for cancer diagnosis. Both unsupervised and supervised modes use well-known and successful social network approaches such as the maximum weighted clique criterion and edge centrality to rank genes. The suggested technique has two goals: (i) to maximize the relevancy of the chosen genes with the target class and (ii) to reduce their inner redundancy. A maximum weighted clique is chosen in a repetitive way in each iteration of this procedure. The appropriate genes are then chosen from among the existing features in this maximum clique using edge centrality and gene relevance. In the experiment, several datasets consisting of Colon, Leukemia, SRBCT, Prostate Tumor, and Lung Cancer, with different properties, are used to demonstrate the efficacy of the developed model. Our performance is compared to that of renowned filter-based gene selection approaches for cancer diagnosis whose results demonstrate a clear superiority.

A differentiable approach to the maximum independent set problem using dataless neural networks.

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. In this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.

Quantifying the similarity of 2D images using edge pixels: an application to the forensic comparison of footwear impressions.

We propose a novel method to quantify the similarity between an impression (Q) from an unknown source and a test impression (K) from a known source. Using the property of geometrical congruence in the impressions, the degree of correspondence is quantified using ideas from graph theory and maximum clique (MC). The algorithm uses the x and y coordinates of the edges in the images as the data. We focus on local areas in Q and the corresponding regions in K and extract features for comparison. Using pairs of images with known origin, we train a random forest to classify pairs into mates and non-mates. We collected impressions from 60 pairs of shoes of the same brand and model, worn over six months. Using a different set of very similar shoes, we evaluated the performance of the algorithm in terms of the accuracy with which it correctly classified images into source classes. Using classification error rates and ROC curves, we compare the proposed method to other algorithms in the literature and show that for these data, our method shows good classification performance relative to other methods. The algorithm can be implemented with the R package shoeprintr.

Graph Theory Approach to Detect Examinees Involved in Test Collusion.

Test collusion (TC) is sharing of test materials or answers to test questions before or during the test (important special case of TC is item preknowledge). Because of potentially large advantages for examinees involved, TC poses a serious threat to the validity of score interpretations. The proposed approach applies graph theory methodology to response similarity analyses for identifying groups of examinees involved in TC without using any knowledge about parts of test that were affected by TC. The approach supports different response similarity indices (specific to a particular type of TC) and different types of groups (connected components, cliques, or near-cliques). A comparison with an up-to-date method using real and simulated data is presented. Possible extensions and practical recommendations are given.

An algorithm to compare two-dimensional footwear outsole images using maximum cliques and speeded-up robust feature.

Footwear examiners are tasked with comparing an outsole impression (Q) left at a crime scene with an impression (K) from a database or from the suspect's shoe. We propose a method for comparing two shoe outsole impressions that relies on robust features (speeded-up robust feature; SURF) on each impression and aligns them using a maximum clique (MC). After alignment, an algorithm we denote MC-COMP is used to extract additional features that are then combined into a univariate similarity score using a random forest (RF). We use a database of shoe outsole impressions that includes images from two models of athletic shoes that were purchased new and then worn by study participants for about 6 months. The shoes share class characteristics such as outsole pattern and size, and thus the comparison is challenging. We find that the RF implemented on SURF outperforms other methods recently proposed in the literature in terms of classification precision. In more realistic scenarios where crime scene impressions may be degraded and smudged, the algorithm we propose-denoted MC-COMP-SURF-shows the best classification performance by detecting unique features better than other methods. The algorithm can be implemented with the R-package shoeprintr.

In Silico Laboratory: Tools for Similarity-Based Drug Discovery.

Computational methods that predict and evaluate binding of ligands to receptors implicated in different pathologies have become crucial in modern drug design and discovery. Here, we describe protocols for using the recently developed package of computational tools for similarity-based drug discovery. The ProBiS stand-alone program and web server allow superimposition of protein structures against large protein databases and predict ligands based on detected binding site similarities. GenProBiS allows mapping of human somatic missense mutations related to cancer and non-synonymous single nucleotide polymorphisms and subsequent visual exploration of specific interactions in connection to these mutations. We describe protocols for using LiSiCA, a fast ligand-based virtual screening software that enables easy screening of large databases containing billions of small molecules. Finally, we show the use of BoBER, a web interface that enables user-friendly access to a large database of bioisosteric and scaffold hopping replacements.