Faulon J.L., Bender A. Handbook of Chemoinformatics Algorithms
Подождите немного. Документ загружается.
358 Handbook of Chemoinformatics Algorithms
function is based on Guttman quadratic split algorithm [41], using the Tanimoto
distance.
Another common scenario in chemoinformatics applications is the use of similarity
searches with binary fingerprints. In this case, similarity between two molecules
is defined by their Tanimoto index, which can be efficiently computed using bit
operations. Currently, there is no Open Source implementation of an index that will
support similarity searching on binary string (necessitating linear scans), although the
work being performed on GiST indexes for molecules described above is applicable
to this problem.
12.6 WORKFLOW ENVIRONMENTS
Workflow (or pipelining) tools have grown in popularity as a means of allowing
nonexperts to perform tasks composed of sequential units, without having to write
actual programs (although such tools can be enhanced with user-written scripts). Note
that, by definition, a workflow tool is not tied to any specific domain. By providing
domain-specific tasks (components), one can provide support for any specific domain
such as bioinformatics or chemoinformatics.
A variety of commercial and Open Source workflow tools for chemoinformatics
are available, and Warr [47] provides a broad overview. Two of the most popular Open
Source tools are Taverna [48] and KNIME (http://www.knime.org), both written in
Java and supporting chemoinformatics via third-party plugins. In the former case,
the CDK is used to provide chemoinformatics support. In the latter case, chemoin-
formatics support is provided by plugins from Tripos, Schrodinger, as well as the
CDK. Note that the plugin functionality can range from simple operations such as
fingerprint generation, format conversion, and 2D depictions to much more complex
tasks such as pharmacophore searching or docking. Given the rise in chemoinformat-
ics web services, it is useful for workflow tools to be able to handle them. Taverna
provides support for SOAP-based web services, although KNIME currently does not
support them.
In one sense, workflow tools can be considered the highest level of an Open Source
chemoinformatics stack—making using of toolkits and databases and providing an
easy-to-use interface on top of these items. Note that workflow environments do
not necessarily represent a fixed-goal application. Indeed their flexibility allows one
to mix and match various chemoinformatics tools. At the same time, workflows to
perform specific tasks can be “packaged” and thus presented as a stand-alone tool.
12.7 CONCLUSIONS
Given the practical nature of chemoinformatics, it is essential that implementations
of fundamental algorithms are easily accessible. Although one can always imple-
ment specific algorithms as stand-alone programs, it is useful to be able to build on
top of previous work. In this sense, chemoinformatics toolkits provide a convenient
platform on which to build a variety of applications. By their nature, such toolkits
will provide core data models for chemical concepts and implement a number of
core chemoinformatics algorithms such as ring perception and canonicalization. As a
Open Source Chemoinformatics Software and Database Technologies 359
result, most toolkits exhibit similar core functionalities, although differences in their
completeness (such as the handling of chirality) do occur. Toolkits may also provide
higher-level functionality that, while not representing a full standalone program, is
sufficiently common in various applications. Examples include fingerprint genera-
tion, similarity calculations, and so on. The three toolkits discussed here provide a
variety of high-level functionality, which, as in the case of RDKit, may extend beyond
traditional chemoinformatics.
The choice of toolkit is very dependent on language, features available, support,
documentation, and of course personal preference. Indeed, a recent Open Source
project called Cinfony (http://code.google.com/p/cinfony/) provides a uniform API
to the three toolkits discussed here, allowing one to mix and match functionality from
any of them. With the increased availability of publicly accessible data and cheap
computing power, the ability to carry out chemoinformatics research and develop
applications in a redistributable fashion is becoming increasingly feasible. In such a
scenario, the license associated with a toolkit can play a major role in choosing which
one to use. In this context, Open Source toolkits provide a number of advantages
as described in Section 12.1.1. Of course, Open Source toolkits are not always as
polished as their commercial counterparts.
Given that some commercial vendors do provide no-cost licenses for certain
groups, they can be an attractive alternative when developing applications. The
downside is that distribution of such applications is dependent on access to the toolkit.
In this context, it is clear that the viability of an Open Source chemoinformatics
stack (Figure 12.1) is very much dependent on the use of Open Source toolkits. Given
the free availability of high-performance database systems and web servers, a signifi-
cant part of the computational infrastructure for large chemoinformatics applications
exists in an Open Source fashion and toolkits represent the core domain-specific
functionality. With the rise of Grid and Cloud computing, the ability to freely dis-
tribute the stack across hundreds or thousands of machines can be severely limited by
commercial licenses. In such a scenario, Open Source software provides an attractive
approach to making use of emerging computing technologies in chemoinformatics
applications.
In conclusion, while Open Source chemoinformatics software may suffer from
some disadvantages compared to commercial offerings, they provide a number of
significant advantages in terms of transparency (leading to verifiability), reuse, and
cost. A number of Open Source toolkits are available and this chapter has focused on
three projects that are most active. In addition to toolkits, we have provided a brief
discussion on database and pipelining technologies as they relate to chemoinformatics
applications.
REFERENCES
1. Delano, W., The case for cpen source software in drug discovery. Drug Discov. Today
2005, 10, 213–217.
2. Guha, R., Howard, M. T., Hutchison, G. R., Murray-Rust, P., Rzepa, H., Steinbeck,
C., Wegner, J., and Willighagen, E. L., The blue obelisk–interoperability in chemical
informatics. J. Chem. Inf. Model. 2006, 46, 991–998.
360 Handbook of Chemoinformatics Algorithms
3. Weininger, D., SMILES, a chemical language and information system. 1. Introduction to
methodology and encoding rules. J. Chem. Inf. Comput. Sci. 1988, 28, 31–36.
4. Weininger, D., Weininger, A., and Weininger, J., SMILES. 2. Algorithm for generation of
unique SMILES notation. J. Chem. Inf. Comput. Sci. 1989, 29, 97–101.
5. Steinbeck, C., Han, Y. Q., Kuhn, S., Horlacher, O., Luttmann, E., and Willighagen, E.,
The Chemistry Development Kit (CDK): An open-source java library for chemo- and
bioinformatics. J. Chem. Inf. Comput. Sci. 2003, 43, 493–500.
6. Steinbeck, C., Hoppe, C., Kuhn, S., Floris, M., Guha, R., and Willighagen, E., Recent
developments of the Chemistry Development Kit (CDK)—an open-source java library for
chemo- and bioinformatics. Curr. Pharm. Des. 2006, 12, 2110–2120.
7. Guha, R., Chemical informatics functionality in R. J. Stat. Soft. 2007, 18 [online].
8. Wang, R. and Lai, L., A new atom-additive method for calculating partition coefficients.
J. Chem. Inf. Comput. Sci. 1997, 37, 615–621.
9. Ghose, A. and Crippen, G., Atomic physicochemical parameters for three-dimensional-
structure-directed quantitative structure–activity relationships. 2. Modeling dispersive and
hydrophobic interactions. J. Chem. Inf. Comput. Sci. 1987, 27, 21–35.
10. Hall, L. and Kier, L., Electrotopological state indices for atom types: A novel combination
of electronic, topological, and valence state information. J. Chem. Inf. Comput. Sci. 1995,
35, 1039–1045.
11. Hall, L., and Kier, L., The molecular connectivity χ indices and κ shape indices
in structure–property modeling.. In: Reviews of Computational Chemistry, Vol. 2, K.
Lipkowitz and D. Boyd (eds), VCH Publishers: New York, 1991.
12. Wiener, H., Structural determination of paraffin boiling points. J. Am. Chem. Soc. 1947,
69, 2636–2638.
13. Gutman, I., Ruscic, B., Trinajstic, N., and Wilcox, Jr., C., Graph theory and molecular
orbitals. XII. Acyclic polyenes. J. Chem. Phys. 1975, 62, 3399–3405.
14. Petitjean, M., Applications of the radius diameter diagram to the classification of topo-
logical and geometrical shapes of chemical compounds. J. Chem. Inf. Comput. Sci. 1992,
32, 331–337.
15. Katritzky, A., Mu, L., Lobanov, V., and Karelson, M., Correlation of boiling points with
molecular structure. 1. A training set of 298 diverse organics and a test set of 9 simple
inorganics. J. Phys. Chem. 1996, 100, 10400–10407.
16. Gasteiger, J. and Marsili, M., Iterative partial equalization of orbital electronegativity—a
rapid access to atomic charges. Tetrahedron 1980, 36, 3219–3228.
17. Pearlman, R. S. and Smith, K. M., Metric validation and the receptor-relevant subspace
concept. J. Chem. Inf. Comput. Sci. 1999, 39, 28–35.
18. Todeschini, R. and Gramatica, P., 3D modelling and prediction by WHIM descriptors. Part
5. Theory, development and chemical meaning of WHIM descriptors. Quant. Struct. Act.
Relat. 1997, 16, 113–119.
19. Ertl, P., Rohde, B., and Selzer, P., Fast calculation of molecular polar surface area as a
sum of fragment based contributions and its application to the prediction of drug transport
properties. J. Med. Chem. 2000, 43, 3714–3717.
20. Stanton, D. and Jurs, P., Development and use of charged partial surface area structural
descriptors in computer assisted quantitative structure property relationship studies. Anal.
Chem. 1990, 62, 2323–2329.
21. Copeland, T., PMD Applied, Centennial Books: Alexandria, VA, 2005.
22. Sun Microsystems, “DocCheck,” http://java.sun.com/j2se/javadoc/doccheck/, last accessed
July 2008.
23. O’Boyle, N., Morely, C., and Hutchison, G., Pybel: A python wrapper for the openBabel
chemoinformatics toolkit. Chem. Central J. 2008, 2, 5.
Open Source Chemoinformatics Software and Database Technologies 361
24. Lewell, X., Judd, D., Watson, S., and Hann, M., RECAP—retrosynthetic combinatorial
analysis procedure: A powerful new technique for identifying privileged molecular frag-
ments with useful applications in combinatorial chemistry. J. Chem. Inf. Comput. Sci.
1998, 38, 511–522.
25. Balaban, A., Highly discriminating distance based topological index. Chem. Phys. Lett.
1982, 89, 399–404.
26. Carhart, R., Smith, D., and Venkataraghavan, R., Atom pairs as molecular features in
structure–activity studies: Definition and applications. J. Chem. Inf. Comput. Sci. 1985,
25, 64–73.
27. Nilakantan, R., Bauman, N., Dixon, J., and Venkataraghavan, R., Topological torsion:
A new molecular descriptor for SAR applications. Comparison with other descriptors.
J. Chem. Inf. Model. 1987, 27, 82–85.
28. Kier, L., A shape index from molecular graphs. Quant. Struct.–Act. Relat. Pharmacol.,
Chem. Biol. 1985, 4, 109–116.
29. Labute, P., A widely applicable set of descriptors, http://www.chemcomp.com/journal/
vsadesc. htm, last accessed August 2008.
30. Williams, A., A perspective of publicly accessible/open-access chemistry databases. Drug
Discov. Today 2008, 13, 495–501.
31. Haider, N., “checkmol/matchmol,” http://merian.pch.univie.ac.at/∼nhaider/cheminf/
cmmm. html, last accessed August 2008.
32. Cormen, T., Leiserson, C., and Rivest, R., Introduction to Algorithms, MIT Press:
Cambridge, MA, 1998.
33. Ullmann, J., An algorithm for subgraph isomorphism. J. ACM 1976, 23, 31–42.
34. Sayle, R., Improved SMILES substructure Searching, http://www.daylight.com/meetings/
emug00/Sayle/substruct.html, 2000.
35. Ballester, P. and Graham Richards, W., Ultrafast shape recognition to search compound
databases for similar molecular shapes. J. Comp. Chem. 2007, 28, 1711–1723.
36. Good, A., Ewing, T., Gschwend, D., and Kuntz, I., New molecular shape descriptors—
applications in database screening. J. Comput.-Aided Mol. Des. 1995, 9, 1–12.
37. Guha, R., Dutta, D., Jurs, P., and Chen, T., R–NN curves: An intuitive approach to outlier
detection using a distance based method. J. Chem. Inf. Model. 2006, 46, 1713–1722.
38. Xu, H. and Agrafiotis, D., Nearest neighbor search in general metric spaces using a tree
data structure with a simple heuristic. J. Chem. Inf. Comput. Sci. 2003, 43, 1933–1941.
39. Bentley, J., Multidimensional binary search trees used for associative searching. Commun.
ACM 1975, 18, 509–517.
40. Gionis, A., Indyk, P., and Motwani, R., Similarity search in high dimensions via hashing.
In: VLDB ’99: Proceedings of the 25th International Conference on Very Large Data
Bases, Morgan Kaufmann Publishers Inc.: San Francisco, CA, 1999.
41. Guttman, A., R-trees: A dynamic index structure for spatial searching. In: SIGMOD
Conference, ACM Press: New York, 1984.
42. Bohm, C., Berchtold, S., and Keim, D., Searching in high-dimensional spaces: Index
structures for improving the performance of multimedia databases. ACM Comput. Surv.
2001, 33, 322–373.
43. Wang,W.,Yang, J., and Muntz, R., Information organization and databases: Foundations of
data organization. In: Kluwer International Series in Engineering and Computer Science
Series, Kluwer Academic Publishers: Norwell, MA, 2000; Chapter PK-tree: A Spatial
Index Structure for High Dimensional Point Data, pp. 281–293.
44. Ciaccia, P., Patella, M., and Zezula, M., M-tree: An efficient access method for similarity
search in metric spaces. In: VLDB ’97: Proceedings of the 23rd International Conference
on Very Large Data Bases, Morgan Kaufmann Publishers, Inc.: San Francisco, CA, 1997.
362 Handbook of Chemoinformatics Algorithms
45. Hellerstein, J., Naughton, J., and Pfeffer,A., Generalized search trees for database systems.
In: VLDB ’95: Proceedings of the 21st International Conference on Very Large Databases,
Morgan Kaufmann Publishers Inc.: San Francisco, CA, 1995.
46. Schmid, E.-G., personal communication, 2008.
47. Warr, W., Workflow and pipelining in chemoinformatics, http://www.qsarworld.com/
qsar-workflow1.php, last accessed July 2008.
48. Oinn, T., Addis, M., Ferris, J., Marvin, D., Senger, M., Greenwood, M., Carver, T., Glover,
K., Pocock, M., Wipat, A., and Li, P., Taverna: A tool for the composition and enactment
of bioinformatics workflows. Bioinformatics 2004, 20, 3045–3054.
13
Sequence Alignment
Algorithms
Applications to Glycans
and Trees and Tree-Like
Structures
Tatsuya Akutsu
CONTENTS
13.1 Introduction ...................................................................363
13.2 Tree Edit Distance and Tree Alignment......................................364
13.3 Glycan Structures .............................................................368
13.4 Basic Algorithms..............................................................369
13.4.1 MCST Algorithm....................................................369
13.4.2 Global and Local Sequence Alignment ............................370
13.5 KCaM Algorithms ............................................................371
13.5.1 Global Glycan Alignment...........................................371
13.5.2 Local Glycan Alignment ............................................373
13.5.3 Exact Matching Algorithms ........................................374
13.6 Pseudocode....................................................................374
13.6.1 Code for Global Glycan Alignment ................................374
13.6.2 Modification for Local Glycan Alignment .........................376
13.7 Illustrative Example ..........................................................376
13.8 KCaM Web Server ............................................................379
13.9 Concluding Remarks .........................................................379
References ............................................................................380
13.1 INTRODUCTION
Glycans, which are also known as carbohydrate sugar chains, are important
biomolecules. In particular, they are quite vital for the development and function-
ing of multicellular organisms, and they are generally found on the exterior surface
of cells. Some glycans play an important role in cell–cell interactions. For example,
tumor cells make some abnormal glycans, which are recognized by some receptors
on natural killer cells. Some glycans also play an important role in protein folding
cooperating with chaperone proteins.
363
364 Handbook of Chemoinformatics Algorithms
Despite their importance, few computational methods had been developed for
analyzing glycans until the beginning of the twenty-first century. The importance
of glycans has been recognized in the field of bioinformatics since the beginning
of the twenty first-century and then various studies have been carried out. One of
the important studies is the construction of databases of glycans. Based on the early
work on the CarbBank database, a new publically available database called KEGG
Glycan has been constructed [1]. Along with the construction of the database, it was
recognized that there was no tool for similarity search for glycans. Thus, a search
tool named KCaM (KEGG Carbohydrate Matcher) has been developed [2] along
with alignment algorithms for glycans [3]. Following the development of the search
tool, several machine learning or computational methods have been developed, which
include development of score matrices for glycan alignment [4], probabilistic mod-
els the methods for the classification of glycans [5], support vector machine-based
methods for the classification of glycans using newly developed tree kernels [6,7],
elucidation of glycan structures using gene expression data [8], and tandem mass
spectrometry data [9].
Since the purpose of this section is not to give a comprehensive review but to give a
detailed explanation on glycan alignment algorithms, we focus on glycan alignment.
In this section, we first review tree edit distance and tree alignment because glycans
are usually represented as trees and glycan alignment algorithms are based on these
concepts. Next, we briefly review glycan structures. Then, after reviewing some basic
algorithms, we give a detailed description of the glycan alignment algorithms (KCaM
algorithms) [3] along with pseudocodes and examples. Finally, we briefly review the
KCaM search tool [2] and discuss the limitation of the algorithms and possible future
development.
13.2 TREE EDIT DISTANCE AND TREE ALIGNMENT
Trees are very common data structures in computer science and are special cases of
graphs. The problem of comparing trees arises in various areas such as bioinformat-
ics, chemoinformatics, structured text databases (e.g., XML databases) and image
analysis [10]. In particular, a lot of tree-based studies have been carried out for com-
parison of RNA secondary structures [11]. Although trees are classified into rooted
trees and unrooted trees, this section focuses on rooted trees since glycans are usually
represented as rooted trees as well as RNA secondary structures.
A tree T consists of a set of nodes V(T) and a set of directed edges E(T). Nodes are
divided into internal nodes and leaves, where there exists one special internal node
called the root. In this section, we only consider labeled trees in which each node is
assigned a symbol from some finite set Σ.
Each internal node has one or more outgoing edges and each leaf does not have an
outgoing edge. For each edge (u, v), u is called a parent of v, and v is called a child
of u. For each node u, Chd(u) denotes the set of children. Thus, Chd(u) ={}holds
if and only if u is a leaf. Then, we can see that the set of edges is given by
E(T) ={(u, v)|v ∈ Chd(u), u ∈ V(T)}.
Sequence Alignment Algorithms 365
A
B
A C
D
B
E
B A
A
B
A C B E
E
B A
Deletion of ‘D’
Insertion of ‘D’
T
1
T
2
E
FIGURE 13.1 Deletion and insertion operations. In this example, T
2
is obtained from T
1
by
deleting a node labeled ‘D’. Conversely, T
1
is obtained from T
2
by inserting a node labeled ‘D’.
There are two types of rooted trees: ordered trees and unordered trees. A tree is
called ordered if a left-to-right order among siblings is given. Otherwise, it is called
unordered. In ordered trees, this left-to-right order must be preserved among matching
nodes.
Although various measures have been proposed for evaluating the similarity
between two trees, tree edit distance has been extensively studied and applied. Tree
edit distance for ordered trees is defined as follows (see Ref. [10] for details), where
we only consider the unit cost case (i.e., it takes cost 1 per insertion, deletion, or
substitution). Let T be a rooted ordered tree. Let label(v) denote the label of a node
v. |T| denotes the size (the number of nodes) of T.Anedit operation on a tree T is
either a deletion,aninsertion,orasubstitution (see also Figure 13.1).
Deletion: Delete a non-root node v in T with parent u, making the children
of v become children of u. The children are inserted in the place of v as a
subsequence in the left-to-right order of the children of u.
Insertion: Complement of delete. Insert a node v as a child of u in T making v the
parent of a consecutive subsequence of the children of u.
Substitution: Change the label of a node v in T.
The tree edit distance between T
1
and T
2
is defined as the minimum number of
operations to transform T
1
into T
2
.
A close relationship exists between the edit distance and the ordered edit dis-
tance mapping (or just a mapping) [10]. A ⊆ V(T
1
) ×V(T
2
) is called a mapping
if the following conditions are satisfied for any pair (u
1
, v
1
), (u
2
, v
2
) ∈ A (see also
Figure. 13.2):
i. u
1
= u
2
iff. v
1
= v
2
ii. u
1
is an ancestor of u
2
iff. v
1
is an ancestor of v
2
iii. u
1
is to the left of u
2
iff. v
1
is to the left of v
2
Let id(A) be the set of pairs having identical labels in A. The mapping A max-
imizing id(A) defines the largest common sub-tree,
∗
which is the tree obtained by
∗
In this section, we add a “-” between “sub” and “tree” to distinguish the word from the common notion
of a subtree.
366 Handbook of Chemoinformatics Algorithms
A
B
A C
B E
B E
D
E
B
A
B
B
A C
F
B A
E
T
1
T
2
FIGURE 13.2 An example of ordered edit distance mapping. In this example, T
2
is obtained
from T
1
by deleting a node labeled ‘D’, inserting a node labeled ‘F’ and substituting the label
of the root. Thus, the distance between T
1
and T
2
is three. The corresponding ordered edit
distance mapping is shown by broken lines.
deleting nodes not appearing in id(A) from T
1
(or T
2
). It is well known [10] that the
tree edit distance is equal to:
|T
1
|+|T
2
|−|A|−|id(A)|,
which means that the computation of the largest common sub-tree is equivalent to the
computation of the tree edit distance. Acan also be regarded as an alignment between
T
1
and T
2
.
Here we review a dynamic programming procedure to compute the tree edit dis-
tance [10]. For a forest F
1
, let T
1
(u) and u be the rightmost tree of F
1
and its root,
respectively, where a forest is a set of rooted trees and we assume that trees in F
1
are ordered from left to right. Then, T
1
(u) −u, F
1
−u, and F
1
−T
1
(u) denote the
forests obtained by deleting u from T
1
(u), by deleting u from F
1
, and by deleting T
1
(u)
from F
1
, respectively. For a forest F
2
, v, T
2
(v), T
2
(v) −v, F
2
−v, and F
2
−T
2
(v)
are defined in an analogous way. Then, the tree edit distance is computed by the
following dynamic programming procedure (see also Figure 13.3):
D(, ) = 0,
D(F
1
, ) = D(F
1
−u, ) +1,
D(, F
2
) = D(, F
2
−v) + 1,
D(F
1
, F
2
) = min
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
D(F
1
−u, F
2
) +1,
D(F
1
, F
2
−v) + 1,
D(F
1
−T
1
(u), F
2
−T
2
(v)) +D(T
1
(u) −u, T
2
(v) −v)
+δ(label(u), label(v)),
Sequence Alignment Algorithms 367
u
u
F
1
F
2
T
2
(u)T
1
(u)
T
1
(u)–u T
2
(u)–u
(a)
(b)
(c)
u
u
u
u
FIGURE 13.3 Explanation of the dynamic programming algorithm for tree edit distance.
where denotes an empty forest, and δ(x, y) = 1ifx = y, otherwise δ(x, y) = 0.
The meaning of the recursion can be seen from Figure 13.3. This algorithm can be
extended for the general cost function.
The above presented algorithm works in O(n
4
) time, where n = max(|T
1
|, |T
2
|).
There is a long history of efficient algorithms for tree edit distance. Tai-first defined
the notion of tree edit distance and proposed an O(n
6
) time algorithm [12]. Zhang and
Shasha [13] improved it to O(n
4
) time. Klein [14] further improved it to O(n
3
log n)
time. Demaine et al. [15] finally developed an O(n
3
) time algorithm and showed that
it is optimal under a reasonable computation model.
Tree edit distance for unordered trees is defined in the same way as above except
that we need not preserve the ordering among siblings. However, it is known that
computation of edit distance between unordered trees is NP-hard [16]. Therefore, it is
very difficult to compute the edit distance or the largest common sub-tree efficiently
for unordered trees. Horesh et al. [17] developed an A
∗
algorithm to compute the
largest common sub-tree for unordered trees and they showed that it is possible to
compute an optimal solution for trees consisting of dozens of nodes.
Because of NP-hardness of edit distance for unordered trees, some other measures
are proposed. Jiang et al. [18] proposed alignment of trees. In alignment of trees, a
smallest common supertree T is computed from two input trees T
1
and T
2
. That is,
T is a smallest tree such that both T
1
and T
2
become subtrees of T with allowing
substitution of labels paying some cost. It is shown in Ref. [18] that alignment for
unordered trees can be computed in polynomial time if the maximum number of
children is bounded by a constant, otherwise it is NP-hard. However, alignment of
trees is less flexible than tree edit distance.