
(EC-BLAST), which overcomes these limitations, refines the present approaches 4 and extends the public Kyoto Encyclopedia of Genes and Genomes (KEGG) database 15 to provide a fully annotated reaction database.

EC-BLAST, comprising a set of algorithms, automatically performs rapid comparisons between enzyme reactions ( Fig. 1) using the EC number, enzyme name or substrate name as an input parameter. Three types of reaction similarity searches are supported by EC-BLAST ( Fig. 2a) : (i) bond-change similarity search, based on comparison of the bond changes (bonds formed or cleaved, order changes and stereo changes); (ii) reaction-center similarity search, based on comparison of the reactive centers of the reactions; and (iii) structural similarity search of the reactions, based on comparison of the chemical structure of the smallmolecule moieties in the reactions.

For comparisons, reactions must first be 'cleaned up' so that they are balanced (for full algorithm details, see Online Methods and Supplementary Note 1). The representation of stereoisomers is standardized, and the whole reaction is canonicalized (normalized) wherever possible so that each identical molecule is represented identically across the whole data set of reactions. The use of R-group annotation to encode generic molecules and reactions is included where possible. Four distinct algorithms for accurate atom-atom mapping (AAM) 4 (specifically, one-to-one mapping of the atoms in the reactants to the same atoms in the products) are employed via the maximal common subgraph (MCS) 16 approach. The solution chosen is the one that obeys the principle of minimum chemical distance 17 on the basis of the number of bond changes, the total bond-energy change and the number of subgraph fragments determined for a reaction. These algorithms use a 'divide and conquer' strategy for overall mapping of the atoms, and at each step a game theory strategy is used to choose the best match, with specified resolver rules in case of deadlocks. With this approach, bond changes and reaction centers can be assigned automatically from the reaction with a variation of the Dugundji-Ugi (DU) matrix model 18 . Stereochemical changes are calculated using a combination of available tools 19 . To facilitate enzyme comparisons, we designed EC-BLAST to characterize reactions by multiple fingerprints: a bond-change fingerprint, with stereo changes coded in parallel; a set of reaction-center fingerprints, representing the local atomic environment for each reaction center in the reaction; and a reaction-structure fingerprint, which is a composite molecular fingerprint of all the molecules in the reaction. These fingerprints are stored in EC-BLAST's underlying database for each reaction to allow rapid searching.

Our major challenge in developing EC-BLAST was assigning the correct AAM. To test the AAM protocol, we compared the ec-bLast: a tool to automatically search and compare enzyme reactions We present ec-bLast (http://www.ebi.ac.uk/thornton-srv/ software/rbl/), an algorithm and Web tool for quantitative similarity searches between enzyme reactions at three levels: bond change, reaction center and reaction structure similarity. it uses bond changes and reaction patterns for all known biochemical reactions derived from atom-atom mapping across each reaction. ec-bLast has the potential to improve enzyme classification, identify previously uncharacterized or new biochemical transformations, improve the assignment of enzyme function to sequences, and assist in enzyme engineering.

A major challenge in biological research is to understand, capture and describe the biological functions of proteins. Of all known protein functions, enzyme chemical reactions are perhaps the best described, having been manually curated by members of the Enzyme Commission (EC) 1, 2 . Although the EC nomenclature is widely employed as an invaluable reference description of enzyme function, it cannot readily be used for an automated quantitative comparison of reactions [3] [4] [5] [6] [7] [8] [9] . Such comparisons are essential for assigning EC numbers automatically and for gaining an overview of the world of biochemical reactions. Just as methods for comparing protein and DNA sequences have improved our basic understanding of evolution, a method allowing quantitative comparison of enzyme reactions should provide a firm foundation from which to explore the evolution of enzyme function and to facilitate the design of new enzymes.

Efforts have been made to classify enzymes and their reactions automatically 3, [8] [9] [10] [11] [12] [13] [14] and to find similar enzymes on the basis of their overall reaction chemistry [3] [4] [5] [6] [7] [8] [9] , but the success of these approaches has been limited. These attempts have critically depended upon the consistency and reliability of the underlying reaction data and the power of the algorithms used to process a diverse range of reactions 4 . We describe an algorithm and Web-based tool, EC-bond library alignment and search tool brief communications outputs from EC-BLAST with ~6,000 balanced and curated KEGG reactions (18,903 reactantpair (RPAIR) 8 mappings), which had been generated by KEGG from a combination of manual and computational work. Our top solution reproduced ~99% (18,629 of 18,903) of the KEGG RPAIR mappings automatically, with ~1% (274 of 18,903) mapping mismatches (Supplementary Note 1). However, in many of these mismatches, the KEGG mapping is thought to be derived by manual intervention using further experimental information about the reaction mechanism, which is not present in the overall reaction equation used here.

The similarity between two enzyme reactions is calculated by the similarity of their reaction fingerprints via a Jaccard function (T w ), which ranges between 0 (no similarity) and 1 (identical fingerprints) (Supplementary Note 1). For each similarity metric (i.e., bond change, reaction center and structure similarity), an all-by-all comparison was performed across ~6,000 mapped representative enzyme reactions in the EC-BLAST database derived from KEGG. The statistical significance of the reported similarity scores between reactions was computed from the observed distributions using the z score and P value (Online Methods).

To investigate the performance of these three metrics, we performed an all-by-all comparison ( Fig. 2 and Supplementary Data 1) of the 6,000 KEGG balanced reactions (covering ~3,490 International Union of Biochemistry and Molecular Biology (IUBMB) EC numbers) using EC-BLAST. The resulting distributions of the three scores ( Fig. 2b) shows that all metrics display a median score of ~0.2, with similar shapes for the bond and reaction-center score distributions. The Jaccard scores for the structure similarity metric show a different, broader distribution with many more high-scoring matches, reflecting the common involvement of large substrates such as ATP.

One approach to test the efficiency of these scoring metrics for comparisons is to explore whether they can be used to identify similar reactions automatically. Each reaction was compared to all other reactions, and the hits were then rank ordered according to the score. This comparison was done at various Jaccard score cutoffs (between 0 and 1), and we used the values obtained from the above analysis to calculate the accuracy plots ( Fig. 2c ) and receiver operating characteristic (ROC) curves ( Fig. 2d) for the three similarity metrics using the standard approach available in R (ROCR 20 ). The ROC curves show a strong predictive power for all metrics, but the comparison of reaction centers is the most effective method for identifying reactions with the same EC sub-subclass, yielding a prediction accuracy of more than 90% for a cutoff of 0.65. The area under the curve (AUC), which gives a measure of overall efficacy of the method for the three metrics (bond change, reaction center and structure similarity), was 0.84, 0.87 and 0.78, respectively. This approach should be helpful in assigning EC numbers for novel reactions and for identifying outliers and errors.

To compare the six enzyme primary classes, we clustered ~6,000 enzymatic reactions according to the percent frequency of bond changes within each class (Fig. 3a) . The resulting dendrogram (Fig. 3b) shows one major division into two groups, splitting the ligases (EC 6), transferases (EC 2) and hydrolases (EC 3) from the isomerases (EC 5), oxidoreductases (EC 1) and lyases (EC 4). This split is due to the high frequency of distinct bond changes such as O-P and H-N in the first group and the change of bond order in carbon-oxygen bonds, C-O ↔ C=O, in the second group. The divisions within these two groups are due to class-specific frequency of bond changes, for instance C-S in transferases, C-O (aromatic) in isomerases and O=O in oxidoreductases. Some reaction classes have greater chemical diversity (for example, the oxidoreductases), whereas some bond changes occur frequently in all classes (for example, the ubiquitous cleavage of the H-O bond).

In order to get an overview of the universe of the chemical reactions ( Supplementary Table 1 ), we derived the network of the 5,073 representative reactions using a combination of bond and reaction-center scores. The network ( Fig. 3c) shows that clusters are usually small and separate and that there is no segregation between enzyme primary classes. Figure 3d shows the largest clusters, all with at least ten members. There are 785 individual clusters with more than one member when a P value cutoff of >0.01 is used. Of these, 715 are pure clusters, whose members all have the same primary EC number ( Supplementary Figs. 1 and 2 and Supplementary Data 2 and 3). Some clusters are outliers in the plot; such reactions usually include unusual bond changes and metabolites.

A few clusters (~7.6%) contain a mixture of reactions from different primary classes ( Fig. 3c) , highlighting cases of shared chemistry between these enzymes despite their disparate classification (Supplementary Results).

To investigate the relationship between the evolution of sequence and reactions, we examined a relatively small and structurally characterized set of enzymes, the phosphatidylinositol phosphodiesterase (PPI) superfamily. We cataloged ~8,823 sequences that contain the PPI domain (CATH protein structure classification database ID: 83.161.120.155) as reported by CATH-Gene3D 21,22 version 3.5. The resulting enzymes perform 18 different enzyme functions, 12 of which were included in the EC-BLAST database ( Supplementary Tables 2 and 3) .

When we used the reaction-center metric, 6 of these 12 reactions were found in the top 50 EC-BLAST results list. Four of these were in the top seven, being very similar reactions in the same EC sub-subclass. The fifth, which is a lyase rather than an oxidoreductase, came in at rank 12. When we used the substructure metric, a further three reactions were identified npg that had not been identified by the reaction-center metric. These therefore represent examples in which the reaction center has changed but the substructures have been conserved. Not all enzyme functions performed by this domain family can be found by a single search, but when the results are iteratively used as search terms, a further three PPI superfamily enzyme functions can be found. This type of two-tier search could be mimicking the steps followed in the evolution of the enzyme superfamily via an intermediary function and/or highlight promiscuous (multifunctional) enzymes, but we have no evidence for this yet. EC-BLAST provides a robust, simple method to compare enzyme reactions quantitatively on the basis of bond changes, reaction centers and substructure similarities ( Supplementary Fig. 3 ).

Our study highlights the complexity of enzymatic catalysis and the need for well-structured and accurate databases of enzyme reactions. The EC nomenclature is the gold standard, which remains incredibly useful as the common currency for identifying reactions. However, many reactions are complex and have attributes of more than a single primary class (for example, EC 5.4, the isomerase subclass of intramolecular transferases). Having a tool such as EC-BLAST to navigate between reactions and to highlight unbalanced and inconsistent annotations makes the classification scheme even more intuitive.

The ability to compare the chemical similarities of enzyme reactions can help suggest new possible functions for an enzyme family. We believe that EC-BLAST may help address challenges such as understanding the process by which enzyme sequences adopt new functions, understanding enzyme functional promiscuity, understanding the species distribution of enzyme (a) Typical output from a reaction query search as a ranked list of reactions. The searches are based on the reaction similarity metrics for (i) bond changes, (ii) reaction centers and (iii) structure similarity. Arrow color illustrates similarity between reactions; green to red represents highly similar to most dissimilar, respectively. (b) Distribution of Jaccard similarity scores (T w ) for the three different metrics, shown as density plots for T w > 0. The yellow violin shapes indicate the kernel density estimation of the data at different scores; the thick black lines indicate the middle two quadrants in the distribution of each score; and the white circles give the median for each metric. (c) Accuracy plot for the prediction of IUBMB EC sub-subclass, derived for the three metrics for a given cutoff. Bond changes 1,000 Automated reaction classification in EC-BLAST. The approach used to characterize reactions is summarized in Supplementary  Figure 3 , and it comprises the following steps.

1. For reaction characterization, the molecular input data must be first cleaned and standardized. We used standard structure data 24 representations of both the molecules and the reactions. 2. If the reaction is balanced, AAM is performed using four algorithms (see "Atom-atom mapping across the reaction" below) in parallel, and the outputs are canonicalized (Supplementary Note 1) and annotated using a relative numbering scheme for standardization. 3. The best mapping is chosen from the output, as defined by the 'chemical cost function' , the evaluation of enthalpy and entropy factors across the reaction. 4. In the final stage, bond changes and stereo changes are calculated, which is followed by fingerprint generation.

Each of these steps is described below and in more mathematical detail in Supplementary Note 1.

The AAM can be performed only on 'clean' reactions, as many reactions do not balance. Often, manual curation is required to standardize such reactions. In our case, unbalanced reactions were balanced using an automated reaction-balance code; however, success rates were sometimes low for complex reactions. Stereochemistry was curated in those reactions where it was found to be ambiguous or undefined. This is particularly important for comparative analysis of enzymes within the isomerase class because many of the overall reactions within this EC class involve a change only of stereochemistry. The annotation is a very intensive process because changing one molecule in the data set may lead to a cascade of changes if a molecule is involved in multiple reactions.

The curated reactions are subjected to the AAM process, which involves multiple graph comparison steps. The small-molecule subgraph detector (SMSD) 16 software developed in our group was used for the graph comparison step. This allows for a robust comparison between the molecules on either side of the reaction, ranking solutions on the basis of chemical filters: for example, solutions that contain matched rings are ranked above others. The SMSD not only calculates isomorphism but also ranks these solutions using chemical filters defined by us. The SMSD has various graph comparison algorithms, implemented and optimized for various chemical graphs, which helps to generate chemically valid graph comparison solutions. Most of the chemical graph comparisons can be done in minutes using LSF nodes, but there are a few reactions that may take several hours (for example, multiple molecules with complex ring systems).

The next challenge faced for accurate AAM is the selection of winning solution(s) in the similarity matrix. Sometimes more than one row or column can compete as winners. In this scenario a deadlock of selection is triggered, and a deadlock resolver is used to obtain a solution. The basis of the deadlock resolver is to obtain a subgraph solution, which will minimize the number of fragments, in turn minimizing the bond broken/formed energy if bonds are cleaved/formed. In cases where even this criterion fails, the first competing solution in the matrix is chosen. This is deterministic in terms of output because the input reaction and the matrix are canonicalized before the actual AAM algorithm is triggered.

Once the AAM is completed, the extraction of bond changes is performed using the DU model. The bonds broken and formed are very well depicted in this reaction matrix (R), and an extended R also incorporates stereo changes on atoms. Geometric isomer (E/Z) information is then added as a later stage in the fingerprint generation. Extraction of stereo changes is challenging, and we have been unable to find a 'single-software solution' that is capable of doing this process. Instead, we used InChI 25 to extract the stereo centers on the 2D molecules. Then ChemAxon was used to find the CIP configuration on these stereo centers. Manual curation of these stereo centers was necessary to ensure annotation in the data set because InChI did not recognize all stereochemistry information. Further options might include generating 3D conformers to define valid stereo atoms or centers, but this is not implemented in the present framework.

Four algorithms are used to generate AAM, and this may give rise to alternative mappings. These algorithms are also guided by chemical knowledge while performing the AAM: for example, prioritizing phosphate and water mapping. The best mapping is chosen on the basis of the cost function, which minimizes bond changes, bond broken/formed energy (minimizing the chemical chaos in this model). When it is impossible to identify the best solution from the cost function, then an alternative mapping is stored. Fingerprint generation is computed on only one of the solutions.

Cleaning and standardizing the input reaction. Explicit hydrogen atoms are added to the input RXN reaction file, and a check is made for balance between the nonhydrogen atom types of the reactant and products. Only balanced reactions, according to the nonhydrogen atom count, are mapped, whereas the unbalanced reactions are skipped. The stereochemistry assignment has been npg manually fixed/updated on a number of molecules. The reactants and products in a reaction are sorted according to atom count, bond count, atomic weight, isotope and hydrogen count.

One of the major challenges in the data curation process is the presence of R groups. The total number of reactions with at least one enzyme assigned to them in the EC-BLAST database is 6,257. The number of reactions with R groups is 863 (~14%); and amongst them in 33 (~1%) reactions, R is a part of the reaction center. R in reactions was treated as a single-atom entity, although more sophisticated methods can be used to assign functional groups to these. Presently this is beyond the scope of the project. The negative impact of R groups might be seen in the search results if the R becomes part of reaction center.

Molecular graph matching across the reaction. The SMSD 16 is used for finding the constraint-based MCS between two molecules, and the obtained results can further be filtered on the basis of chemical rules such as the cost of bond-breaking energy, stereo matches, and the total number of bonds affected if the matched subgraph was deleted from the query molecules. This makes the reported isomorphism solution 16 chemically viable.

Atom-atom mapping across the reaction. The four algorithms for performing the AAM are as follows.

Mixture-MCS model. In the mixture-MCS model, the largest MCSs between reactants and products are first mapped according to the similarity scores. The cells of the similarity matrix with the highest similarity scores are processed, and the matched part is removed from the reaction. The matrix is refilled with the similarity score of the remaining molecules, and the selection-and-elimination process is repeated until no more atoms can be mapped.

Min-sub model. In the min-sub model, the smallest substructures between the reactants and products are first mapped according to the similarity scores. The cells with the lowest substructure similarity scores are processed, and the matched part is removed from the reaction. The matrix is refilled with the similarity score of the remaining molecules, and the selectionand-elimination process is repeated until no more atoms can be mapped. The user-defined structural matches are preferred over the general rule.

Max-sub model. In the max-sub model, the largest substructures between the reactants and products are first mapped on the basis of the similarity scores. The cells with the highest substructure similarity scores are processed, and the matched part is removed from the reaction. The matrix is refilled with the similarity scores of the remaining molecules, and the selectionand-elimination process is repeated until no more atoms can be mapped. The user-defined structural matches are preferred over the general rule.

Assimilation model. The assimilation model is triggered if a substrate or a product has a ring system. The restricted MCS prefers the ring mapping to nonring matches, thus excluding rings being matched with aliphatic chains (detects internal rearrangement reactions). The cells with the highest similarity scores are processed, and the matched part is removed from the reaction. The matrix is refilled with the similarity scores of the remaining molecules, and the selection-and-elimination process is repeated until no more atoms can be mapped. This is very similar to the mixture algorithm, except that ring-system mapping is preferred here.

These models are necessary to obtain a chemically valid AAM, which generates a minimal number of bond changes and requires minimal energy in doing so. The method presented here utilizes a mixture of graph theory and mathematical optimization of algorithmic results generated given a set of chemical rules. Our robust algorithm for performing AAM between reactant and product molecules of a reaction is an extension of the previous work 26, 27 . AAM is a complex process, and there can be more than one way to map atoms in a reaction. We have developed chemical filters to report the best possible mapping with assigned bond changes. The scope of some other non-graph-based methods is often not broad enough to cover diverse classes of reaction patterns, or they usually work on a predefined class of reaction patterns and/or reaction rules. Calculating stereo changes. Stereochemistry assignment involves the relative arrangement of atoms in the molecules 4 . Chirality is one such case of stereochemistry in which molecules are mirror images and hence nonsuperimposable (R/S) 29 . As per the Cahn-Ingold-Prelog (CIP) priority rules 29, 30 , each chiral center is labeled as R or S (on the basis of the atomic number priority). The other form of stereochemistry defined in the IUBMB EC is cis/trans isomerism, which describes the relative orientation of functional groups attached to separate atoms that are connected via double bond (E/Z) or are contained within a ring. Stereo centers are detected using an in-house stereo detection tool (J. May from the CDK) in combination with ChemAxon's stereo code. The chirality information is gained from 3D models (ChemAxon) and our 2D-based stereo detection tool, which supports CIP rules.

Choosing the best mapping. Depending on each of the EC-BLAST mapping algorithms schema, at each step of the AAM process, matched subgraphs are removed from the substrates and products of a reaction, thus changing the reaction center and the outcome of the bond changes. The best solution should produce the minimum number of structural changes in the reactions and thereby reduce the fragments generated while cutting the graph. It should also minimize the bond changes in the reaction and therefore reduce the reaction distance and the cost of energy for npg forming or breaking a bond. These are the core assumptions in understanding the bond changes for an overall reaction. In the case of multiple competing solutions, one of the solutions is chosen arbitrarily.

Generating reaction fingerprints. The chemical information from the mapped reaction is converted into fingerprints 4, 31 . We use an automated method to generate reaction fingerprints on the fly (Supplementary Note 1) .

1. The bond-change fingerprint (BCfp) is generated from the DU model-derived R matrix (Supplementary Note 1) . The stereo changes are coded in parallel, and the reported stereo changes are also transformed into fingerprints. 2. The reaction-center fingerprint (RCfp) represents the local atom environment (Supplementary Note 1) of the reaction centers as marked in the R matrix or stereo-change matrix. They are calculated using molecular signatures or circular fingerprints by capturing the neighboring environment or the affected bonds and atoms. 3. The reaction-structure fingerprint (RSfp) is the composite fingerprint of all the moieties present in the reactants and products of a reaction.

The combination of bond-change and reaction-center fingerprint similarity is the average of their combined scores.

Reaction similarity. The similarity between two reactions can be calculated via the fingerprints. The size of the computed fingerprints is dynamic as it depends on the number of reaction patterns in each reaction. This makes the storage of the information memory efficient, as the system has to keep track of only the changes rather than the whole reaction while computing the similarity searches.

While similarity between two reaction fingerprints is compared, each fingerprint can be transformed into a fixed-length hashed fingerprint, and the similarity between them can be computed by the weighted Jaccard coefficient (T w ) (Supplementary Note 1) . The similarity scores range between 0 (minimum similarity) and 1 (maximum similarity).

Measuring statistical significance of the hits. The significance of the hits returned from the database can be inferred from the P values derived from the z scores of the similarity.

The mean (µ) and s.d. (σ) of the similarity scores are used to define the z score, z = (T w -µ)/σ. For the purpose of calculating the P value, only hits with T w > 0 are considered. The P value is derived from the z score using an extreme value distribution P = 1 -exp(−e −zπ/√(6) − Γ ′ (1) ), where the Euler-Mascheroni constant Γ ′ (1) ≈ 0.577215665.

A hit above a chosen cutoff is defined as a true positive if its EC sub-subclass (for example, 3.5.2) matches that of the query reaction. A hit is defined as a false positive if its similarity score is more than the chosen cutoff and its EC sub-subclass does not match the query reaction. If the score is below the designated cutoff and the EC sub-subclass of this reaction does not match that of the query reaction, this is defined as a true negative. If the score is below the designated cutoff and the EC sub-subclass of this reaction matches that of the query reaction, this is defined as a false negative 20 . An in-house R script was used to perform statistical analysis (Supplementary Note 2) .

Reaction-enzyme database. We generated a reaction database with ~6,950 mapped balanced reactions from the KEGG database (June 2011 public release). We have manually curated many molecules (~100) for which the stereochemistry was missing or wrong. The database has approximately 6,200 reactions with one of more enzymes assigned to each. Each reaction in the database has annotated bond changes and stereo centers assigned to it.

EC-BLAST allows AAM to be performed on a balanced reaction RXN file. The mapping with best chemical outcome as determined by the software is returned to the user.

Analysis tools used. ChemAxon (http://www.chemaxon. com/) was used for reaction drawing and testing 3D conformers for stereo changes. ChemAxon was used for adding explicit hydrogen(s) to the reaction molecules and generating a 2D layout (where required). The CDK 19 was used as the base library to handle and process the molecules and reactions. Open Babel 32 was used to generate 3D conformers when required. The statistical software R was used performing statistical analysis such as for clustering and generating ROC data 20 .

{'paper_id': '9337564', 'title': 'EC-BLAST: a tool to automatically search and compare enzyme reactions', 's2_url': 'https://api.semanticscholar.org/CorpusID:9337564', 'source': 'S2ORC'}