Maximum common substructure (MCS) algorithms rank among the most sensitive and accurate methods for measuring structural similarities among small molecules. This utility is critical for many research areas in drug discovery and chemical genomics. The MCS problem is a graph-based similarity concept that is defined as the largest substructure (sub-graph) shared among two compounds (Wang, Backman, Horan, and Girke, 2013; Cao, Jiang, and Girke, 2008). It fundamentally differs from the structural descriptor-based strategies like fingerprints or structural keys. Another strength of the MCS approach is the identification of the actual MCS that can be mapped back to the source compounds in order to pinpoint the common and unique features in their structures. This output is often more intuitive to interpret and chemically more meaningful than the purely numeric information returned by descriptor-based approaches. Because the MCS problem is NP-complete, an efficient algorithm is essential to minimize the compute time of its extremely complex search process. The package implements an efficient backtracking algorithm that introduces a new flexible MCS (FMCS) matching strategy to identify MCSs among compounds containing atom and/or bond mismatches. In contrast to this, other MCS algorithms find only exact MCSs that are perfectly contained in two molecules. The details about the FMCS algorithm are described in the Supplementary Materials Section of the associated publication (Wang, Backman, Horan, et al., 2013). The package provides several utilities to use the FMCS algorithm for pairwise compound comparisons, structure similarity searching and clustering. To maximize performance, the time consuming computational steps of are implemented in C++. Integration with the package provides visualization functionalities of MCSs and consistent structure and substructure data handling routines (Cao, Charisi, Cheng, Jiang, and Girke, 2008; Backman, Cao, and Girke, 2011). The following gives an overview of the most important functionalities provided by .
The R software for running and can be downloaded from CRAN (http://cran.at.r-project.org/
). The package can be installed from an open R session using the install command.
source("http://bioconductor.org/biocLite.R")
biocLite("fmcsR")
To demo the main functionality of the package, one can load its sample data stored as object. The generic function can be used to visualize the corresponding structures.
library(fmcsR)
data(fmcstest)
plot(fmcstest[1:3], print=FALSE)
The function computes the MCS/FMCS shared among two compounds, which can be highlighted in their structure with the function.
test <- fmcs(fmcstest[1], fmcstest[2], au=2, bu=1)
plotMCS(test,regenCoords=TRUE)
library("fmcsR") # Loads the package
library(help="fmcsR") # Lists functions/classes provided by fmcsR
library(help="ChemmineR") # Lists functions/classes from ChemmineR
vignette("fmcsR") # Opens this PDF manual
vignette("ChemmineR") # Opens ChemmineR PDF manual
The help documents for the different functions and container classes can be accessed with the standard R help syntax.
?fmcs
?"MCS-class"
?"SDFset-class"
The following loads the sample data set provided by the package. It contains the SD file (SDF) of molecules stored in an object.
data(fmcstest)
sdfset <- fmcstest
sdfset
## An instance of "SDFset" with 3 molecules
Custom compound data sets can be imported and exported with the and functions, respectively. The following demonstrates this by exporting the object to a file named sdfset.sdf. The latter is then reimported into R with the function.
write.SDF(sdfset, file="sdfset.sdf")
mysdf <- read.SDFset(file="sdfset.sdf")
The function accepts as input two molecules provided as or objects. Its output is an S4 object of class . The default printing behavior summarizes the MCS result by providing the number of MCSs it found, the total number of atoms in the query compound a, the total number of atoms in the target compound b, the number of atoms in their MCS c and the corresponding Tanimoto Coefficient. The latter is a widely used similarity measure that is defined here as c / (a + b − c). In addition, the Overlap Coefficient is provided, which is defined as c / min(a, b). This coefficient is often useful for detecting similarities among compounds with large size differences.
mcsa <- fmcs(sdfset[[1]], sdfset[[2]])
mcsa
## An instance of "MCS"
## Number of MCSs: 7
## CMP1: 14 atoms
## CMP2: 33 atoms
## MCS: 8 atoms
## Tanimoto Coefficient: 0.20513
## Overlap Coefficient: 0.57143
mcsb <- fmcs(sdfset[[1]], sdfset[[3]])
mcsb
## An instance of "MCS"
## Number of MCSs: 1
## CMP1: 14 atoms
## CMP2: 25 atoms
## MCS: 14 atoms
## Tanimoto Coefficient: 0.56
## Overlap Coefficient: 1
If is run with then it returns the numeric summary information in a named .
fmcs(sdfset[1], sdfset[2], fast=TRUE)
## Query_Size Target_Size MCS_Size Tanimoto_Coefficient Overlap_Coefficient
## 14.0000 33.0000 8.0000 0.2051 0.5714
The class contains three components named , and . The slot stores the numeric summary information, while the structural MCS information for the query and target structures is stored in the and slots, respectively. The latter two slots each contain a with two subcomponents: the original query/target structures as objects as well as one or more numeric index vector(s) specifying the MCS information in form of the row positions in the atom block of the corresponding . A call to will often return several index vectors. In those cases the algorithm has identified alternative MCSs of equal size.
slotNames(mcsa)
## [1] "stats" "mcs1" "mcs2"
Accessor methods are provided to return the different data components of the class.
stats(mcsa) # or mcsa[["stats"]]
## Query_Size Target_Size MCS_Size Tanimoto_Coefficient Overlap_Coefficient
## 14.0000 33.0000 8.0000 0.2051 0.5714
mcsa1 <- mcs1(mcsa) # or mcsa[["mcs1"]]
mcsa2 <- mcs2(mcsa) # or mcsa[["mcs2"]]
mcsa1[1] # returns SDFset component
## $query
## An instance of "SDFset" with 1 molecules
mcsa1[[2]][1:2] # return first two index vectors
## $CMP1_fmcs_1
## [1] 3 8 7 4 9 5 11 1
##
## $CMP1_fmcs_2
## [1] 3 8 7 4 9 5 1 13
The function can be used to return the substructures stored in an instance as object. If new atom numbers will be assigned to the subsetted SDF, while will maintain the atom numbers from its source. For details consult the help documents and .
mcstosdfset <- mcs2sdfset(mcsa, type="new")
plot(mcstosdfset[[1]], print=FALSE)
To construct an object manually, one can provide the required data components in a .
mylist <- list(stats=stats(mcsa), mcs1=mcs1(mcsa), mcs2=mcs2(mcsa))
as(mylist, "MCS")
## An instance of "MCS"
## Number of MCSs: 7
## CMP1: 14 atoms
## CMP2: 33 atoms
## MCS: 8 atoms
## Tanimoto Coefficient: 0.20513
## Overlap Coefficient: 0.57143
If is run with its default paramenters then it returns the MCS of two compounds, because the mismatch parameters are all set to zero. To identify FMCSs, one has to raise the number of upper bound atom mismates and/or bond mismatches to interger values above zero.
plotMCS(fmcs(sdfset[1], sdfset[2], au=0, bu=0))
plotMCS(fmcs(sdfset[1], sdfset[2], au=1, bu=1))
plotMCS(fmcs(sdfset[1], sdfset[2], au=2, bu=2))
plotMCS(fmcs(sdfset[1], sdfset[3], au=0, bu=0))
The function provides FMCS search functionality for compound collections stored in objects.
data(sdfsample) # Loads larger sample data set
sdf <- sdfsample
fmcsBatch(sdf[1], sdf[1:30], au=0, bu=0)
## Query_Size Target_Size MCS_Size Tanimoto_Coefficient Overlap_Coefficient
## CMP1 33 33 33 1.0000 1.0000
## CMP2 33 26 11 0.2292 0.4231
## CMP3 33 26 10 0.2041 0.3846
## CMP4 33 32 9 0.1607 0.2812
## CMP5 33 23 14 0.3333 0.6087
## CMP6 33 19 13 0.3333 0.6842
## CMP7 33 21 9 0.2000 0.4286
## CMP8 33 31 8 0.1429 0.2581
## CMP9 33 21 9 0.2000 0.4286
## CMP10 33 21 8 0.1739 0.3810
## CMP11 33 36 15 0.2778 0.4545
## CMP12 33 26 12 0.2553 0.4615
## CMP13 33 26 11 0.2292 0.4231
## CMP14 33 16 12 0.3243 0.7500
## CMP15 33 34 15 0.2885 0.4545
## CMP16 33 25 8 0.1600 0.3200
## CMP17 33 19 8 0.1818 0.4211
## CMP18 33 24 10 0.2128 0.4167
## CMP19 33 25 14 0.3182 0.5600
## CMP20 33 26 10 0.2041 0.3846
## CMP21 33 25 15 0.3488 0.6000
## CMP22 33 21 11 0.2558 0.5238
## CMP23 33 26 11 0.2292 0.4231
## CMP24 33 17 6 0.1364 0.3529
## CMP25 33 27 9 0.1765 0.3333
## CMP26 33 24 13 0.2955 0.5417
## CMP27 33 26 11 0.2292 0.4231
## CMP28 33 20 10 0.2326 0.5000
## CMP29 33 20 8 0.1778 0.4000
## CMP30 33 18 7 0.1591 0.3889
The function can be used to compute a similarity matrix for clustering with various algorithms available in R. The following example uses the FMCS algorithm to compute a similarity matrix that is used for hierarchical clustering with the function and the result is plotted in form of a dendrogram.
sdf <- sdf[1:7]
d <- sapply(cid(sdf), function(x) fmcsBatch(sdf[x], sdf, au=0, bu=0, matching.mode="aromatic")[,"Overlap_Coefficient"])
d
## CMP1 CMP2 CMP3 CMP4 CMP5 CMP6 CMP7
## CMP1 1.0000 0.2308 0.2308 0.2812 0.5217 0.6842 0.2857
## CMP2 0.2308 1.0000 0.4231 0.5385 0.2174 0.4737 0.2857
## CMP3 0.2308 0.4231 1.0000 0.3077 0.2174 0.4737 0.9048
## CMP4 0.2812 0.5385 0.3077 1.0000 0.3043 0.5263 0.2857
## CMP5 0.5217 0.2174 0.2174 0.3043 1.0000 0.5789 0.2381
## CMP6 0.6842 0.4737 0.4737 0.5263 0.5789 1.0000 0.3158
## CMP7 0.2857 0.2857 0.9048 0.2857 0.2381 0.3158 1.0000
hc <- hclust(as.dist(1-d), method="complete")
plot(as.dendrogram(hc), edgePar=list(col=4, lwd=2), horiz=TRUE)
The FMCS shared among compound pairs of interest can be visualized with, here for the two most similar compounds from the previous tree:
plotMCS(fmcs(sdf[3], sdf[7], au=0, bu=0, matching.mode="aromatic"))
sessionInfo()
## R version 3.1.1 (2014-07-10)
## Platform: x86_64-unknown-linux-gnu (64-bit)
##
## locale:
## [1] LC_CTYPE=en_US.UTF-8 LC_NUMERIC=C LC_TIME=en_US.UTF-8 LC_COLLATE=C
## [5] LC_MONETARY=en_US.UTF-8 LC_MESSAGES=en_US.UTF-8 LC_PAPER=en_US.UTF-8 LC_NAME=C
## [9] LC_ADDRESS=C LC_TELEPHONE=C LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C
##
## attached base packages:
## [1] stats graphics grDevices utils datasets methods base
##
## other attached packages:
## [1] ChemmineOB_1.2.9 knitcitations_1.0-1 fmcsR_1.6.5 ChemmineR_2.16.9 knitr_1.6
##
## loaded via a namespace (and not attached):
## [1] DBI_0.2-7 RCurl_1.95-4.3 RJSONIO_1.3-0 Rcpp_0.11.2 RefManageR_0.8.3 XML_3.98-1.1
## [7] bibtex_0.3-6 digest_0.6.4 evaluate_0.5.5 formatR_0.10 httr_0.4 lubridate_1.3.3
## [13] memoise_0.2.1 parallel_3.1.1 plyr_1.8.1 stringr_0.6.2 tools_3.1.1 zlibbioc_1.10.0
[1] T. W. H. Backman, Y. Cao and T. Girke. “ChemMine tools: an online service for analyzing and clustering small molecules”. In: Nucleic Acids Research 39.suppl (Jun. 2011), pp. W486-W491. DOI: href=http://dx.doi.org/10.1093/nar/gkr320. URL: http://dx.doi.org/10.1093/nar/gkr320.
[2] Y. Cao, A. Charisi, L. Cheng, et al. “ChemmineR: a compound mining framework for R”. In: Bioinformatics 24.15 (Jul. 2008), pp. 1733-1734. DOI: href=http://dx.doi.org/10.1093/bioinformatics/btn307. URL: http://dx.doi.org/10.1093/bioinformatics/btn307.
[3] Y. Cao, T. Jiang and T. Girke. “A maximum common substructure-based algorithm for searching and predicting drug-like compounds”. In: Bioinformatics 24.13 (Jun. 2008), pp. i366-i374. DOI: href=http://dx.doi.org/10.1093/bioinformatics/btn186. URL: http://dx.doi.org/10.1093/bioinformatics/btn186.
[4] Y. Wang, T. W. H. Backman, K. Horan, et al. “fmcsR: mismatch tolerant maximum common substructure searching in R”. In: Bioinformatics 29.21 (Oct. 2013), pp. 2792-2794. DOI: href=http://dx.doi.org/10.1093/bioinformatics/btt475. URL: http://dx.doi.org/10.1093/bioinformatics/btt475.