FRAGMENT HIERARCHIES Figure 5. Fragmentation tree where molecule coordinates are obtained by unconstrained depiction layout. Figure 6. Same fragmentation tree as shown in Figure 5, after the colligative depiction layout procedure has been applied. shows the same molecules and fragments after this process has been applied. 4. Interbranch Orientation. At the completion of the previous step, each of the root branches has been arranged and oriented to show the common features within the branch. There is as yet no frame of reference for comparing the structures within different root branches, because there is no common ancestor and hence not even a partial common mapping system. There is, however, quite a high likelihood that the root branches are structurally related, and so it is useful to devise a scheme to orient them in a common way by means of translation/rotation/inversion. To do this, we take advantage of the fact that the constituent fragments of the root branches are depicted in a very constrained way. Their 2D shape now encodes a signiﬁcant amount of information, which is generally not the case for unconstrained depiction layout. Therefore, it is quite viable to search for a single transformation for each whole branch which maximizes the overall shape overlap of the 2D structures. Since the orientation is a relatively imprecise step, it is sufﬁcient to use a greedy algorithm, rather than a more J. Chem. Inf. Model., Vol. 50, No. 1, 2010 41 rigorous clustering method. One begins by ﬁrst deﬁning the reference set to be the root branch with the largest number of constituent molecules. The subject set is the root branch with the second highest molecule count. For the subject set, an orientation is selected such that its combined 2D shape is most similar to that of the reference set. The orientation is applied to the subject set, and then it is merged into the reference set. A new subject set is selected, and the algorithm proceeds until all of the root branches have been processed. To compare the shapes of two sets, each of the molecules in each set is ﬁrst translated so that the center of the root fragment is at the origin. A grid is deﬁned, which is large enough to capture the bounds of each set as it is rotated around the origin.8 For each set, grid values are deﬁned by addition of a Gaussian function, for each atom in each molecule: f(r) ) 1 e-|r|2 N where r is the distance from the grid point to the center of the corresponding atom and N is the number of molecules in the set. The two grids are now directly comparable, and their similarity can be computed: similarity ) ∑ (|Rij - Sij|+|Rihjet - Sihjet|) ij where i and j iterate over each of the grid points, R is the grid for the reference set and S is the grid for the subject set. Rhet and Shet are analogous grids where only heteroatoms are plotted. Lower values indicate more similar grids. To ﬁnd the most similar orientation, the subject set is varied by rotating about the origin in increments of 5°; inverting along one of the axes; and translating by [dx, dy] ∈ {-2, 1, 0, 1, 2}, which makes for a total of 3600 evaluations. Figure 7 shows the resulting orientations and the corre- sponding grid pattern for each of 9 root fragments from a database of DHFR inhibitors, which contains 397 structures.9 As can be seen, at the completion of the orientation step, the layout coordinates of molecules with different root fragments are approximately comparable, and the 2D coor- dinates now encode signiﬁcant information about shared structural features. RESULTS 1. DHFR Inhibitors. Once the fragment tree has been generated and the appropriate steps have been taken to ensure that the layout and orientation of the molecules shows the common fragmentation patterns, there are a number of ways to display this information visually. The most direct method is to display the fragmentation tree as a hierarchical structure, with each root node being a distinct entity. To make examination of the tree practical from a user- interface perspective, it makes sense to allow nodes to be interactively opened or closed, so that parts of the tree can be displayed as necessary. Because molecules are usually grouped together according to common fragmentation pat- terns, it is helpful to plot summary information in the vicinity of each node. This elicits information about the activities of