38 J. Chem. Inf. Model., Vol. 50, No. 1, 2010 CLARK Figure 1. (a) shows the fragmentation sequence for four molecules which share a common root, which are grouped according to common fragments, while (b) shows the corresponding tree representation, which subsumes adjacent, analogous fragments into individual nodes. of scaffolds, and the fragmentation sequences which relate them to the whole molecules, may be adapted to suit the data. The method published by Schuffenhauer and Ertl et al. has been found to consistently produce agreeable results for pharmacologically relevant molecules.3 These decom- position rules are such that the last remaining fragments are typically those that have been used as scaffolds and tend to be common substructures for a particular drug discovery campaign. One modiﬁcation is applied, which is to collapse sequential breaking of fused aromatic ring systems into a single fragmentation step. This fragmentation method is used exclusively in this work, but the layout methods described are general and apply equally well to any scheme which is appropriate to the data. The fragments generated for each molecule need to be organized in the form of a tree. This can be accomplished by ﬁrst producing canonical string representations for each fragment (e.g., SMILES).4 The canonical strings are arranged from smallest to largest for each molecule, and sorted by alphabetical order. In this way, for a given row and column, the fragments above or below are considered to be part of the same tree node if all the fragments up to and including that column are equal, which is illustrated in Figure 1. In the following section, it will be necessary to know the correspondence between each fragment and its parent frag- ment. This can be accomplished by assigning an arbitrary label to each atom in the original molecule, and retaining these labels as the fragmentation proceeds, for example 2. Mapping Root Branches. For any node position in the tree which has more than one child molecule, the objective is ultimately to obtain an ideal 2D depiction layout and orientation such that analogous atoms in related mol- ecules are placed in the same location, in order to make visual perception of the common features as easy as possible. Before this can be accomplished, it is ﬁrst necessary to ﬁnd an atom-to-atom mapping scheme that relates each of the equivalent substructure fragments to each other. When all of the fragments are nonsymmetrical and nondegenerate, this process is not especially complicated, since there will only be one correct mapping between any pair of fragments. When the potential mappings are degener- ate, it is desirable to consider an ensemble of possible solutions, and ﬁnd a combination that leads to the most compatible topological overlap of whole molecules. Consider the example shown in Figure 1, where four molecules share a common root fragment, the pyridine core. Pyridine itself has permutational symmetry, which means that when two such fragments are mapped onto each other, it is necessary to choose a mapping from multiple pairwise combinations. Figure 2 illustrates the need to choose wisely. An arbitrary numbering scheme is chosen for the pyridine root fragment of the ﬁrst molecule. The atom assigned as number 6 has a benzyl substituent for the descendent fragment. For the second molecule, there are two valid numbering schemes. As shown for the ﬁrst option, the descendent fragment also has a benzyl substituent at atom number 6, for the second option, the benzyl fragment is attached to atom number 2. For this simple example, it is clear that a suboptimal atom- to-atom mapping scheme would eventually lead to molecules being superposed on top of each other in a manner that misleads rather than elucidates the common structural features. Unfortunately, the number of possible solutions grows combinatorially, which means that it is not viable to rely on an algorithm which examines every combination to ﬁnd the best topological overlap. While adequate results could be achieved by using a greedy algorithm, that is, assign the possible graph automorphisms for each fragment se- quentially and pick the case that best matches the previous assignments, the method described here uses the Unary Quadratic Optimization (UQO) method,5 which has previ- ously been applied to the problem of common scaffold detection.6 Each fragment can have one possible assigned permutation, and the quality of the ensemble can be reasonably expressed as the sum of compatibility scores between each pair of assignments. The interaction energy between each pair of states not belonging to the same fragment is expressed in terms of the compatibility between the substituents which are not part of the shared substructure. Figure 3 shows two molecules that share a commonly assigned benzene fragment, with the tentative mapping numbers shown. The similarity of the substitution patterns is obtained by a breadth ﬁrst search of the molecular graph, starting from each direct substitution point. For the ﬁrst shell, the molecule in 3a is described as [2-N, 6-C], for a singly bonded nitrogen atom adjacent to position 2 and a singly