Faulon J.L., Bender A. Handbook of Chemoinformatics Algorithms
Подождите немного. Документ загружается.
338 Handbook of Chemoinformatics Algorithms
ALGORITHM 11.4 PSEUDOCODE FOR SMS
single-molecule-simulator(G, L
et
)
input: - G: simulation graph
-L
et
: list of elementary transformations
output: - Printout of the G vs. time
t = 0
For M
c
steps do
print t,G
L
r
= generate-reactions(G, L
et
)
τ = time of next event using eq. (11.13)
r = selected reaction in L
r
occurring at time t +τ
using eq.(11.14)
B(r) = graph of the reactants of reaction r
E(r) = graph of the products of reaction r
G = G −B(r) +E(r)
t = t +τ
done
generate-reactions(G, L
et
)
input: - G: simulation graph
-L
et
: list of elementary transformations
output: - L
r
: list of reactions
For all et in L
et
do
For all subgraph b of G s.t. b is isomorphic to
B(et)do
e = G −b +E(et)
if species-constraints(e) then
# connected components (full species)
# of subgraphs b and e are required to
# compute reaction rates
L
b
= list of connected components of b
L
e
= list of connected components of e
k = rate-constant(et, L
b
, L
e
)
L
r
= L
r
+(et, b, e, k)
fi
done
done
return L
r
One notes that contrary to previous techniques, Algorithm 11.4 does not require us
to monitor species concentrations. Nonetheless, species and reactions between species
can be retrieved by a postprocess that reads the graphs printed by the algorithm. One
advantage of Algorithm 11.4 is that species concentration can be computed only
when needed; for instance, with a synthesis planning application, concentration may
be computed for only one species (the target product) and a single time step (the final
reaction time).
Reaction Network Generation 339
As already mentioned, the SMS algorithm has been used to study the dynam-
ics of biological networks. Morton-Firth and Bray developed the first version of the
algorithm (StochSim; http://www.ebi.ac.uk/∼lenov/stochsim.html) and used it to pre-
dict the fluctuations in numbers of molecules in a chemotactic signaling pathway of
coliform bacteria. In particular, they examined the temporal changes in the number
of molecules of CheYp, a cytoplasmic protein known to influence the direction of
rotation of the flagellar motor of the bacteria.
Colvin et al. [34] developed asimilar algorithm (DYNSTOC;http://public.tgen.org/
dynstoc) and demonstrated the algorithm with an idealized rule-based model of
two systems. A system in which autophosphorylation of a receptor tyrosine kinase
can generate a multitude of receptor phosphoforms and phosphorylation-dependent
adapter-bound receptor states, and a system in which multivalent ligand–receptor
binding can generate a multitude of ligand-induced receptor aggregates.
As a last application example, Kosuri et al. [35] proposed another implemen-
tation of the SMS algorithm to model cellular transcription and translation. The
software named Tabasco (http://openwetware.org/wiki/TABASCO) directly repre-
sents the position and activity of individual molecules on DNA and can be used
to study the effect of detailed molecular processes on systemwide gene expression.
Tabasco has been demonstrated by simulating the entirety of gene expression during
bacteriophage T7 infection.
11.7 CONCLUDING REMARKS
Initially developed for synthesis planning and retrosynthesis, reaction network
generators have been used in combustion and fuel processing. For these initial appli-
cations, freeware and commercial products exist (for instance, LASHAA, http://lhasa.
harvard.edu/, from Harvard University and, WODCA, http://www.molecular-
networks.com/software/wodca/index.html, from Molecular Networks). With recent
developments in systems biology, one is witnessing novel uses of network generation
in biology, in particular for inferring and studying the dynamics of signaling, and
metabolic and transcriptional networks. With the even more recent activities in syn-
thetic biology, one may foresee new applications for network generation in particular
with enzymatically controlled retrosynthesis, where the synthesis is performed by
microorganisms.
REFERENCES
1. Corey, E. J., General methods for the construction of complex molecules. Pure Appl.
Chem. 1967, 14, 19–37.
2. Ugi, I. B., J., Bley, K., Dengler, A., Dietz A., Fontain, E., Gruber, B., Herges, R. K.
M., Reitsam, K., and Stein, N., Computer-assisted solution of chemical problems—the
historical development and the present state of the art of a new discipline of chemistry.
Angew. Chem., Int. Ed. Engl. 1993, 32, 201–227.
3. Corey, E. J., Cramer III, R. D., and Howe, J., Computer-assisted synthetic analysis
for complex molecules. Methods and procedures for machine generation of synthetic
intermediates. J. Am. Chem. Soc. 1971, 94, 440–459.
340 Handbook of Chemoinformatics Algorithms
4. Clymans, P. J. and Froment, G. F., Computer-generation of reaction paths and rates equa-
tions in the thermal cracking of normal and branched paraffins. Comput. Chem. Eng. 1984,
83, 137–142.
5. Broadbelt, L. J., Stark, S. M., and Klein, M. T., Computer generated pyrolysis modeling:
On-the-fly generation of species, reactions, and rates. Ind. Eng. Chem. Res. 1994, 33,
790–799.
6. Faulon, J. L. and Sault, A. G., Stochastic generator of chemical structure. 3. Reaction
network generation. J. Chem. Inf. Comput. Sci. 2001, 41(4), 894–908.
7. Frenklach, M., Modeling of large reaction systems. In: Complex Chemical Reaction Sys-
tems, Mathematical Modelling and Simulation, J. Warnatz and W. Jäger (eds). Springer:
Berlin, 1987; Vol. 47, pp. 2–16.
8. Susnow, R. G., Dean, A. M., Green, W. H., Peczak, P., and Broadbelt, L. J., Rate-based
construction of kinetic models for complex systems. J. Phys. Chem. A 1997, 101, 3731–
3740.
9. Ugi, I., Fontain, E., and Bauer, J., Transparent formal methods for reducing the combi-
natorial abundance of conceivable solutions to a chemical problem. Computer-assisted
elucidation of complex mechanism. Anal. Chim. Acta 1990, 235, 155–161.
10. Faeder, J. R., Blinov, M. L., Goldstein, B., and Hlavacek, W. S., Combinatorial complexity
and dynamical restriction of network flows in signal transduction. Syst. Biol. (Stevenage)
2005, 2(1), 5–15.
11. Lok, L. and Brent, R.,Automatic generation of cellular reaction networks with Moleculizer
1.0. Nat. Biotechnol. 2005, 23(1), 131–136.
12. Danos, V., Feret, J., Fontana, W., and Krivine, J., Scalable simulation of cellular signaling
networks. Lect. Notes Comput. Sci. 2007, 4807, 139–157.
13. Kotera, M., Okuno,Y., Hattori, M., Goto, S., and Kanehisa, M., Computational assignment
of the EC numbers for genomic-scale analysis of enzymatic reactions. J. Am. Chem. Soc.
2004, 126(50), 16487–16498.
14. Rose, J. R. and Gasteiger, J., HORACE: An automatic system for the hierarchical
classification of chemical reactions. J. Chem. Inf. Comput. Sci. 1994, 34, 74–90.
15. Dugundji, J. and Ugi, I., Theory of the be- and r-matrices. Top. Curr. Chem. 1973, 39,
19–29.
16. Dugundji, J., Gillespie, P., Marquarding, D., and Ugi, I., Metric space and graphs repre-
senting the logical structure of chemistry. In: Chemical Applications of Graph Theory,A.
T. Balaban (ed.). Academic Press: London, 1976.
17. Faulon, J.-L., Stochastic generator of chemical structure: 1. Application to the structure
elucidation of large molecules. J. Chem. Inf. Comput. Sci. 1994, 34, 1204–1218.
18. Ridder, L. and Wagener, M., SyGMa: Combining expert knowledge and empirical scoring
in the prediction of metabolites. Chem. Med. Chem. 2008, 3(5), 821–832.
19. Benson, S. W., Thermochemical Kinetics. Wiley-Interscience: New York, 1976.
20. Sumathi, R., Carstensen, H.-H., and Green, W. H., Jr., Reaction rate prediction via group
additivity, Part 2: H-abstraction from alkenes, alkynes, alcohols, aldehydes, and acids by
H atoms. J. Phys. Chem. A 2001, 105, 8969–8984.
21. Sumathi, R., Carstensen, H.-H., and Green, W. H., Jr., Reaction rate prediction via group
additivity, Part 1: H abstraction from alkanes by H and CH
3
. J. Phys. Chem. A 2001, 105,
6910–6925.
22. Gillespie, D. T.,A general method for numerically simulating the stochastic time evolution
of coupled chemical reactions. J. Comput. Phys. 1976, 22, 403–434.
23. Gillespie, D. T., Stochastic simulation of chemical kinetics. Annu. Rev. Phys. Chem. 2007,
58, 35–55.
Reaction Network Generation 341
24. Fontain, E. and Reitsam, K., The generation of reaction network with RAIN. 1. The
reaction generator. J. Chem. Inf. Comput. Sci. 1991, 31, 96–101.
25. Nigam, A. and Klein, M. T., A mechanism-oriented lumping strategy for heavy hydro-
carbon pyrolysis: Imposition of quantitative structure–reactivity relationship for pure
components. IEC Res. 1993, 32, 1297–1303.
26. Hatzimanikatis, V., Li, C., Ionita, J. A., Henry, C. S., Jankowski, M. D., and Broadbelt,
L. J., Exploring the diversity of complex metabolic networks. Bioinformatics 2005, 21(8),
1603–1609.
27. Liao, K. H., Dobrev, I. D., Dennison, J. E., Jr., Andersen, M. E., Reisfeld, B., Reardon, K.
F., Campain, A., et al., Application of biologically based computer modeling to simple or
complex mixtures. Environ. Health Perspect. 2002, 110(Suppl 6), 957–963.
28. Lenaerts, T. and Bersini, H., A synthon approach to artificial chemistry. Artif. Life 2009,
15(1), 89–103.
29. Gonzalez-Lergier, J., Broadbelt, L. J., and Hatzimanikatis, V., Theoretical considerations
and computational analysis of the complexity in polyketide synthesis pathways. J. Am.
Chem. Soc. 2005, 127(27), 9930–9938.
30. Hou, B. K., Wackett, L. P., and Ellis, L. B., Microbial pathway prediction: A functional
group approach. J. Chem. Inf. Comput. Sci. 2003, 43(3), 1051–1057.
31. Faeder, J. R., Blinov, M. L., Goldstein, B., and Hlavacek, W. S., Rule-based modeling of
biochemical networks. Complexity 2005, 10, 22–41.
32. Morton-Firth, C. J. and Bray, D., Predicting temporal fluctuations in an intracellular
signalling pathway. J. Theor. Biol. 1998, 192(1), 117–128.
33. Blinov, M. L., Faeder, J. R., Yang, J., Goldstein, B., and Hlavacek, W. S., ‘On-the-fly’ or
‘generate-first’ modeling? Nat. Biotechnol. 2005, 23(11), 1344–1345.
34. Colvin, J., Monine, M. I., Faeder, J. R., Hlavacek, W. S., Von Hoff, D. D., and Posner,
R. G., Simulation of large-scale rule-based models. Bioinformatics 2009, 25(7), 910–917.
35. Kosuri, S., Kelly, J. R., and Endy, D., TABASCO: A single molecule, base-pair resolved
gene expression simulator. BMC Bioinform. 2007, 8, 480.
12
Open Source
Chemoinformatics
Software and Database
Technologies
Rajarshi Guha
CONTENTS
12.1 Introduction ...................................................................343
12.2 Why Open Source? ...........................................................344
12.3 The Chemoinformatics Software Stack ......................................345
12.4 Toolkits ........................................................................346
12.4.1 Chemistry Development Kit ........................................347
12.4.2 OpenBabel ...........................................................349
12.4.3 RDKit ................................................................350
12.5 Database Technologies .......................................................352
12.5.1 Cartridges............................................................352
12.5.2 Indexing Chemical Information ....................................354
12.6 Workflow Environments ......................................................358
12.7 Conclusions ...................................................................358
References ............................................................................359
12.1 INTRODUCTION
Algorithm development is integral to the study of chemoinformatics. It is an implicit
fact that many of the tools will incorporate fundamental chemoinformatics algorithms
(such as canonicalization and aromaticity perception).Although any software dealing
with chemoinformatics will need to implement a number of these algorithms, this
chapter will focus on two specific classes of chemoinformatics software. Firstly, we
discuss toolkit libraries which provide various(low-and high-level)chemoinformatics
methods but which are not designed as standalone applications. Secondly, we discuss
relational databases and the solutions available for incorporating chemoinformatics
within the database environment. We also briefly touch upon workflow tools as a
means of aggregating chemoinformatics functionality. Finally, we note that although
there are many vendors for each type of software considered in this chapter, we
exclusively consider Open Source offerings.
343
344 Handbook of Chemoinformatics Algorithms
12.2 WHY OPEN SOURCE?
Although the idea of free and shared software has been in existence since the 1960s,
such software has not been generally available in chemoinformatics. In contrast, the
field of bioinformatics has produced a number of core algorithms (such as BLAST)
as freely available software. Part of the reason for this is the preponderance of chemo-
informatics research in industry, but equally important is the fact that the majority
of chemical information has been proprietary, in contrast to biological data (such as
gene sequences and protein structures), which has traditionally been freely exchanged.
Recently, there has been increasing interest in Open Source chemoinformatics soft-
ware, both in academia and industry [1]. It is also interesting to note that this has
coincided, to some extent, with increasing amounts of public chemical information
(such as structures and assay results). Our focus here is not the business case for
Open Source in software (although issues such as cost and accountability are certainly
important for both business and nonbusiness users); rather, we would like to stress
the transparency of Open Source software in this context. This is especially important
when we realize that the bulk of chemoinformatics software depends on a collection
of core algorithms. The correctness and validity of such software are directly depen-
dent on that of the underlying algorithms. Open Source implementations of the core
algorithms thus allow the user to verify that the algorithm is implemented correctly,
which is usually not true for closed source implementations. Certainly, with the use
of unit tests, one can provide a suite of checks and this is applicable to both closed
source and Open Source software. However, in the case of the latter, one is still at
the mercy of the vendor who may or may not provide the results of a test suite. And
even then, it is not possible to guarantee that an algorithm has been implemented as
described. In one sense, Open Source software follows the principles of good sci-
entific conduct: The “experiment” (i.e., the implementation) is freely accessible for
everybody to examine, repeat, and verify. Furthermore, if advances are made in algo-
rithms, one need not develop an implementation from scratch. Instead, one can start
from a preexisting Open Source implementation. Another important aspect of Open
Source software is the ability to fix errors. Given that software invariably contains
bugs, it is useful not only to identify them, but also to fix them. The ability to access
the source code can allow identification and correction of bugs in a rapid manner. It
should be noted that for chemoinformatics software, this is not always the case, given
the niche nature of the field and the fact that such fixes do require a certain level of
expertise in programming as well as in chemoinformatics. However, the principle still
holds. Probably more important than any of the factors described here is the ability
to freely reuse software (within the limits of the license) and develop novel applica-
tions. No doubt a number of closed source toolkits and applications do provide free
licenses for a number of scenarios (e.g., no cost academic licenses); however, one
cannot usually redistribute the underlying software with the newly developed tool.
As a result, new applications require that other users have access to the underlying
toolkit that can be a hindrance to the spread of the higher-level application. The use
of Open Source software in such situations avoids this problem.
Although the advent of Open Source software in the chemoinformatics field is rel-
atively recent, there is a growing community that focuses specifically on Open Source
Open Source Chemoinformatics Software and Database Technologies 345
and Open Access issues relating to software as well as data. The latter is important
since many chemoinformatics algorithms depend on data (such as van der Waals radii)
and, consequently, the validity and verifiability of the data are important. One of the
more prominent groups in the area is the Blue Obelisk movement [2], which is an
amalgamation of Open Source projects. The group maintains an Open Access, Open
Source data repository at http://bodr.sourceforge.net/.A recent development under the
umbrella of the Blue Obelisk movement is the OpenSMILES project. The SMILES
language was designed in the 1980s, and although there are a number of publications
on this standard [3,4], the specification contains a number of ambiguities. Given that
the original Daylight implementation was proprietary, other vendors (both commer-
cial and noncommercial) have added extensions or provided their own interpretations.
The goal of the OpenSMILES project is to explicitly define the SMILES language in
a public manner. The end result is expected to be a formal grammar for the language
along with reference implementations. Furthermore, the specification will be com-
pletely free. Given the core nature of the SMILES language in chemoinformatics,
open discussion and resolution of ambiguities are vital. The OpenSMILES project is
an excellent example of the transparency afforded by Open Source approaches.
12.3 THE CHEMOINFORMATICS SOFTWARE STACK
The preceding section raises the notion of developing chemoinformatics applications
on top of toolkits. From this point of view, we can look at chemoinformatics software
development in terms of the chemoinformatics “stack,” as shown in Figure 12.1. The
main feature of the stack is the increase in user-oriented functionality as we move
from the bottom to the top.
At the lowest level are the toolkits and databases, which are primarily the focus
of programmers and software developers. It is at this level that most fundamental
Programming
toolkit
Database
system
Cheminformatics
cartridge
Standalone
applications
Web services
Workflow tools
FIGURE 12.1 A schematic representation of an Open Source chemoinformatics software
stack.
346 Handbook of Chemoinformatics Algorithms
chemoinformatics algorithms will be implemented. Building on top of the toolkit and
database, chemoinformatics cartridges allow one to manipulate chemical information
within the database.With this functionality one is in a position to then develop focused
applications, which may be stand-alone or deployed in a variety of manners (such
as web pages or web services) for end users. Finally, at the top we have workflow
tools, which are able to aggregate high- and low-level applications and present them
in an easy-to-use manner. It should be noted that Figure 12.1 does not imply that
databases and cartridges are employed by every chemoinformatics application. Nor
does it imply a rigid hierarchy. However, it does highlight the general role of individual
chemoinformatics components. It should be noted that certain components such as
web services will employ software such as web servers, application containers, and
so on. These components can be commercial or Open Source, the latter accounting
for some of the most popular examples (such as Apache and Tomcat).
12.4 TOOLKITS
Given that the focus of the book is chemoinformatics algorithms, it is important to
realize that the field is not purely theoretical. In other words, one must be able to
employ the algorithms to process real-world data. Although one can build monolithic
chemoinformatics applications, good software engineering practice suggests that low-
level and frequently used functionality be reused. This issue is addressed by the use of
chemoinformatics toolkits that package chemoinformatics functionality into reusable
libraries. A number of toolkit libraries are available for various languages and we
focus on three Open Source libraries that are under active development, namely, the
CDK, OpenBabel, and RDKit. Table 12.1 provides a broad comparison of the three
toolkits in terms of supported features.
Before describing the features of the various toolkits, we provide a brief overview
of the projects themselves.All three have an active development community, although
RDKit is a relatively new entrant and thus has a lower level of participation compared
to the CDK and OpenBabel. Figure 12.2 compares the development activity in terms
of commits to the trunk between July 2007 and July 2008. It is important to note that
the graph of activity includes both maintenance and new development. In that sense,
a project with low activity may simply be in a stable state, with only bug fixes being
committed.
All three are hosted on Sourceforge, which provides mailing lists and version
control. All projects make extensive use of mailing lists for discussions related to
both developmental issues and usage questions. In addition to mailing lists, Wikis
are also employed to host descriptions, tutorials, and so on. Both OpenBabel and
RDKit provide a variety of online documentation in the form of help pages, API
documentation, and examples. In contrast, although there is a variety of information
available for the CDK, it is not collected in one place.
We next consider the chemoinformatics functionality provided by the three toolkits.
It should be noted that these descriptions are not exhaustive and we advise that the
reader explore the web sites of each project to get a more exhaustive and up-to-date
list of features.
Open Source Chemoinformatics Software and Database Technologies 347
TABLE 12.1
A Broad Comparison of Chemoinformatics Features Provided by the Three
Toolkits Discussed
Feature CDK OpenBabel RDKit
License LGPL GPL New BSD
Language Java C++ C++/Python
SLOC
a
188,554 194,358 173,219
Fingerprints
Hashed
√√√ √√√ √√√
Substructure
√√√ √√√ √√√
File format support
√√ √√√ √
Aromaticity models
√√ √
Stereochemistry
√ √√ √√√
Canonicalization
√√√ √√√ √√√
Descriptors
√√√ √ √√√
2D coordinate generation
√√√
x
√√√
3D coordinate generation
√ √√√ √√√
2D depictions
√√√
x
√√√
Conformer generation x
√√
Rigid alignment
√√√ √√√ √√√
SMARTS searching
√√√ √√√ √√√
Pharmacophore searching
√√
x
√√√
a
Source Lines of Code as measured by the tool sloccount (http://www.dwheeler.com/sloccount/). The
count includes all source files, in any language, for the project. In addition, only the trunk for each
project was considered.
12.4.1 CHEMISTRY DEVELOPMENT KIT
The chemistry development kit (CDK) [5,6] (http://cdk.sourceforge.net) is a chemoin-
formatics toolkit library written in Java and licensed under the LGPL. Development
on the library was initiated in 2000 and since then it has been actively developed.
Currently, the project has approximately 20 active developers who address a variety
of projects ranging from implementing new functionality, bug fixes to documenta-
tion and code quality metrics. The library sees widespread usage as evidenced by 60
citations to the original publications. Although the library is written in Java, it can
be accessed from a variety of other languages including Python (via Jython), Ruby,
and R [7]. In addition, a variety of CDK functionalities are available as components
within the KNIME workflow environment.
The CDK provides both low- and high-level functionality. Firstly, the library pro-
vides a set of low-level classes for representing molecular concepts such as atoms,
bonds, molecules, and so on. These classes provide a variety of methods to get and
set various properties of these objects. Related to core representational classes, the
library also provides various low-level operations that are commonly performed in
chemoinformatics. This includes atom typing, ring perception, aromaticity percep-
tion, and substructure searching (either by SMILES or by SMARTS). The second level