Modelling size-realistic nanomaterials to analyse some of their properties, such as toxicity, solubility, or electronic structure, is a current challenge in computational and theoretical chemistry. ...The representation of the all-atom three-dimensional structure of a nanocompound would be ideal, as it could account explicitly for structural effects. However, the use of the whole structure is tedious due to the high data management and the structural complexity that accompanies the surface of the nanoparticle. Developing appropriate tools that enable a quantitative analysis of the structure, as well as the selection of regions of interest such as the core-shell, is a crucial step toward enabling the efficient analysis and processing of model nanostructures. The aim of this study was twofold. First, we defined the NanoFingerprint, which is a representation of a nanocompound in the form of a vector based on its 3D structure. The local relationship between atoms, i.e., their coordination within successive layers of neighbours, allows the characterisation of the local structure through the atom connectivity, maintaining the information of the three-dimensional structure but increasing the management ability. Second, we present a web server, called ATENA, to generate NanoFingerprints and other tools based on the 3D structure of the nanocompounds. A case study is reported to show the validity of our new fingerprint tool and the usefulness of our server. The scientific community and also private companies have a new tool based on a public web server for exploring the toxicity of nanocompounds.
Extended reduced graphs provide summary representations of chemical structures using pharmacophore-type node descriptions to encode the relevant molecular properties. Commonly used similarity ...measures using reduced graphs convert these graphs into 2D vectors like fingerprints, before chemical comparisons are made. This study investigates the effectiveness of a graph-only driven molecular comparison by using extended reduced graphs along with graph edit distance methods for molecular similarity calculation as a tool for ligand-based virtual screening applications, which estimate the bioactivity of a chemical on the basis of the bioactivity of similar compounds. The results proved to be very stable and the graph editing distance method performed better than other methods previously used on reduced graphs. This is exemplified with six publicly available data sets: DUD-E, MUV, GLL&GDD, CAPST, NRLiSt BDB, and ULS-UDS. The screening and statistical tools available on the ligand-based virtual screening benchmarking platform and the RDKit were also used. In the experiments, our method performed better than other molecular similarity methods which use array representations in most cases. Overall, it is shown that extended reduced graphs along with graph edit distance is a combination of methods that has numerous applications and can identify bioactivity similarities in a structurally diverse group of molecules.
Chemical compounds can be represented as attributed graphs. An attributed graph is a mathematical model of an object composed of two types of representations: nodes and edges. Nodes are individual ...components, and edges are relations between these components. In this case, pharmacophore-type node descriptions are represented by nodes and chemical bounds by edges. If we want to obtain the bioactivity dissimilarity between two chemical compounds, a distance between attributed graphs can be used. The Graph Edit Distance allows computing this distance, and it is defined as the cost of transforming one graph into another. Nevertheless, to define this dissimilarity, the transformation cost must be properly tuned. The aim of this paper is to analyse the structural-based screening methods to verify the quality of the Harper transformation costs proposal and to present an algorithm to learn these transformation costs such that the bioactivity dissimilarity is properly defined in a ligand-based virtual screening application. The goodness of the dissimilarity is represented by the classification accuracy. Six publicly available datasets-CAPST, DUD-E, GLL&GDD, NRLiSt-BDB, MUV and ULS-UDS-have been used to validate our methodology and show that with our learned costs, we obtain the highest ratios in identifying the bioactivity similarity in a structurally diverse group of molecules.
Graph edit distance is a methodology used to solve error-tolerant graph matching. This methodology estimates a distance between two graphs by determining the minimum number of modifications required ...to transform one graph into the other. These modifications, known as edit operations, have an edit cost associated that has to be determined depending on the problem.
This study focuses on the use of optimization techniques in order to learn the edit costs used when comparing graphs by means of the graph edit distance.
Graphs represent reduced structural representations of molecules using pharmacophore-type node descriptions to encode the relevant molecular properties. This reduction technique is known as extended reduced graphs. The screening and statistical tools available on the ligand-based virtual screening benchmarking platform and the RDKit were used.
In the experiments, the graph edit distance using learned costs performed better or equally good than using predefined costs. This is exemplified with six publicly available datasets: DUD-E, MUV, GLL&GDD, CAPST, NRLiSt BDB, and ULS-UDS.
This study shows that the graph edit distance along with learned edit costs is useful to identify bioactivity similarities in a structurally diverse group of molecules. Furthermore, the target-specific edit costs might provide useful structure-activity information for future drug-design efforts.
•A sub-optimal algorithm is presented to compute the Graph Edit Distance.•It obtains exactly the same distance value than the Bipartite algorithm.•The computational cost is lower than the Bipartite ...one.•Validation shows an important decrease on run time.
We present a new algorithm to compute the Graph Edit Distance in a sub-optimal way. We demonstrate that the distance value is exactly the same than the one obtained by the algorithm called Bipartite but with a reduced run time. The only restriction we impose is that the edit costs have to be defined such that the Graph Edit Distance can be really defined as a distance function, that is, the cost of insertion plus deletion of nodes (or arcs) have to be lower or equal than the cost of substitution of nodes (or arcs). Empirical validation shows that higher is the order of the graphs, higher is the obtained Speed up.
The prediction of a ligand potency to inhibit SARS-CoV-2 main protease (M-pro) would be a highly helpful addition to a virtual screening process. The most potent compounds might then be the focus of ...further efforts to experimentally validate their potency and improve them. A computational method to predict drug potency, which is based on three main steps, is defined: (1) defining the drug and protein in only one 3D structure; (2) applying graph autoencoder techniques with the aim of generating a latent vector; and (3) using a classical fitting model to the latent vector to predict the potency of the drug. Experiments in a database of 160 drug-M-pro pairs, from which the pIC50 is known, show the ability of our method to predict their drug potency with high accuracy. Moreover, the time spent to compute the pIC50 of the whole database is only some seconds, using a current personal computer. Thus, it can be concluded that a computational tool that predicts, with high reliability, the pIC50 in a cheap and fast way is achieved. This tool, which can be used to prioritize which virtual screening hits, will be further examined in vitro.
•Always considered graph edit distance (GED) is a metric if edit functions are a metric.•We discern between GED computed through edit path and graph bijection.•Triangle inequality of edit functions ...not necessary if GED defined by graph bijection.•Important: usually recognition ratio is maximized in non-metric edit functions.
In the presentation of the graph edit distance in 1983 and other newer bibliography, authors state that it is necessary to apply the distance restrictions (non-negativity, identity of indiscernible elements, symmetry and triangle inequality) to each of the edit functions (insertion, deletion and substitution of nodes and edges) involved in the process of computing the graph edit distance to make the graph edit distance a true distance. Moreover, graph edit distance algorithms presented in the last three decades have been based on mapping the edit path that transforms a graph into the other one into a bijection of the graphs in which some null nodes have been added. In this paper, we show that the triangle inequality does not need to be imposed in each edit function if the graph edit distance is defined through an edit path; however, it is necessary if it is defined as a graph bijection. This is an important finding since the triangle inequality is the only restriction that relates different edit functions and concerns the process of tuning the edit functions given a specific application. Hence, on one hand, it would encourage research to define new algorithms based on the edit path instead of the graph bijection and, on the other hand, use edit functions without the restriction, for instance, that the sum of the costs of insertion and deletion of a pair of nodes has to be larger or equal than the cost of substituting them, which could increase the recognition ratio of a concrete application.
•Graph edit distance used to compute the distance between graphs.•Only one model to learn the edit costs.•Two machine learning strategies.•Neural network and probability density function.
The paper ...presents a method to learn the substitution, deletion and insertion costs on nodes and edges applied to the graph edit distance. We model the learning strategy as a general model and then we concretise it in two different architectures: the first architecture is based on a neural network and the second architecture is based on a multivariate normal distribution, which have been previously trained. The insertion, deletion and substitution costs on nodes and edges are defined as functions that depend on the output of the machine learning architecture. Other machine learning architectures have been presented in the literature to define the graph edit distance costs. Nevertheless, the main feature of our method is that the insertion, deletion and substitution costs are learned together, training the same machine learning and generating only one model. Thus, these costs are influenced one to another, achieving a higher accuracy in the pattern recognition stage than previous methods.
Bipartite graph matching has been demonstrated to be one of the most efficient algorithms to solve error-tolerant graph matching. This algorithm is based on defining a cost matrix between the whole ...nodes of both graphs and solving the nodes' correspondence through a linear assignment method (for instance, Hungarian or Jonker–Volgenant methods). Recently, two versions of this algorithm have been published called Fast Bipartite and Square Fast Bipartite. They compute the same distance value than Bipartite but with a reduced runtime if some restrictions on the edit costs are considered. In this paper, we do not present a new algorithm but we compare the three versions of Bipartite algorithm and show how the violation of the theoretically imposed restrictions in Fast Bipartite and Square Fast Bipartite do not affect the algorithm's performance. That is, in practice, we show that these restrictions do not affect the optimality of the algorithm and so, the three algorithms obtain similar distances and recognition ratios in classification applications although the restrictions do not hold. Moreover, we conclude that the Square Fast Bipartite with the Jonker–Volgenant solver is the fastest algorithm.
•Graph Edit Distance (GED) is the most used error-tolerant graph matching method.•Bipartite graph matching algorithm (BP) is the most used algorithm to solve GED.•2 new versions of BP published that reduce the runtime but restrictions are imposed.•We study how much extend these restrictions limits their applicability.•Empirical validation shows new versions reduce runtime but keep recognition ratio.
•Commentary on: M. Martineau, et. al. 2 PRL.•Learning error-correcting graph matching with a multiclass neural network.•The distance between graphs defined in the paper is not a distance.•How not ...being a distance influences on the application.
We analyze the learning graph-matching algorithm presented in M. Martineau, R. Raveaux, D. Conte, G.Venturini, Learning error-correcting graph matching with a multiclass neural network, Pattern Recognition Letters (2018). Authors propose a new definition of the graph edit distance and also a learning algorithm that deduces some weights on this new graph edit distance. In this commentary, we first show that this new definition of the graph edit distance cannot be considered a distance and then, we discuss how this fact influences on the application of their learning methodology.
PDF
