FRAGMENT HIERARCHIES top left, which is divided up into a number of slices, one for each constituent compound. The color scheme used is green for highly active (<0.1 µ M), red for inactive (>10 µ M) and yellow-orange for moderately active (∼1 µ M). As can be seen from the color pattern of the root fragment itself, the constituent molecules exhibit a wide spectrum of activity. By traversing the hierarchy from the root downward, it is possible to reveal groups of structurally related molecules, which show distinctive inhibition patterns. The branch shown in Figure 8b shows a high degree of consistency, which suggests that the inhibition capabilities can be ascribed to the core fragments. The branch shown in Figure 8c, on the other hand, shows a mixture of active and inactive constitu- ents, which suggests that the inhibition properties are determined to a large extent by the substituents, rather than just the scaffolds. While the hierarchy display is appropriate for detailed analysis of the fragments themselves, it is impractical to examine more than several dozen structures at once with a typical display device. An alternate approach is to display the fragmentation hierarchy of all of the input structures in the form of a dendrogram, where all of the root branches are considered to be descended from a point in the center of a circle, and the branches extend outward from the center.10 Each of the leaf nodes is located at a position about the rim. To ascribe signiﬁcant structural information to this layout, the ordering of the descendency pattern is chosen to maximize the similarity of any two adjacent leaf nodes. In preparation, ﬁngerprints are calculated for each leaf node structure, using the GpiDAPH3 scheme.11 A reference node is selected, which is initially set to the leaf node with the highest average Tanimoto similarity to all other nodes. The tree is then traversed recursively, according to the following procedure: (1) For each of the immediate child nodes, assemble a list of all of the leaf nodes of which it is an ancestor. (2) Select next-in-sequence child node to be that whose descendent leaf nodes has the highest average Tanimoto similarity to the reference node. (3) If the selected node is a leaf node, set the new reference node to this. Otherwise, recursively process the child node. (4) Goto step 2, until all child nodes have been selected. Once the ordering of the tree is determined, the actual layout of the dendrogram is straightforward. The ﬁnal position of each node is obtained by evenly spacing about the rim of a disk, in order of tree traversal. The parent of all root nodes is considered to be the center, and the remaining nodes are arranged in between. If the background is chosen so that each pixel within the enclosing circle is assigned a color derived from the value of the average activity of the molecules belonging to the nearest fragment node, it is possible to gain considerable insight into structure-activity relationships. This is shown in Figure 9, which plots activity data against P. carinii, using the red/yellow/green activity scheme described in the previ- ous section. It is possible to quickly identify which regions of the fragmentation tree have consistently high or low activity, suggesting that the core fragment is responsible for these properties, as well as branches whose activity is quite mixed, suggesting that the substitution patterns are primarily responsible. Figure 10 shows a cutout section of the dendrogram, where several of the structures of leaf nodes are indicated. The leaf J. Chem. Inf. Model., Vol. 50, No. 1, 2010 43 Figure 9. Dendrogram-style fragment tree layout, arranged onto a disk. The background color reﬂects activities of close-by fragments. node clustering is evident by comparison of structures (a) and (b), which are descended from a different root fragment, but are almost identical structures, differing only by an additional chlorine atom on (a) and an additional nitrogen into the fused heterocycle scaffold of (b). The structures (c) and (d) have the same core fragmentation sequence, and denote the two ends of a block of very similar compounds clustered together, sharing high activity against P. carinii DHFR. The dendrogram display is very compact and information- rich. Combined with an interactive user interface which allows facile examination of the structures, which are represented by the fragment nodes, a signiﬁcant amount of structure-activity information can be inferred from the layout and color-coding. 2. COX-2 Inhibitors. A collection of 467 structures with corresponding activity against the COX-2 enzyme9 was submitted to the fragmentation and depiction sequence described within. Each of the structures was embedded in 3D, and its atom ordering scrambled randomly to ensure that there was no residual bias from the input sketch. Figure 11 shows a selection of substructure fragments, upon which most of the structures are based. In each case, a certain motif is observed: central 5-membered ring, usually a heterocycle, is decorated by two adjacent substituents, which are either 5- or 6-membered rings, a mixture of phenyl, pyridyl, or a 5-membered heterocycle. Some of the fragments show an additional substituent on the opposite side of the central ring, which is a consequence of the fragmentation ordering. The ﬁgure shows each of the fragments with a common orientation, which is chemically intuitive. In all cases, the central heterocycle bears the two adjacent substituents at approximately the 10 o’clock and 12 o’clock positions. The common orientation is a consequence of the layout methods described in this work: each of the branches of the fragmentation tree are depicted in such a way as to trade off aesthetic depiction against showing common substitution patterns in analogous positions, taking degeneracy into account. Because this data set has a high degree of structural similarity within the core fragments and the substitution