FRAGMENT HIERARCHIES Figure 2. For the pyridine root fragment, there are multiple ways to map the branches to each other, which are not of equal quality. Figure 3. Shell patterns for substituents of disubstituted benzene fragments. bonded carbon atom at position 6. The molecule in 3b is described as [2-O, 6-C]. For the second shell, the patterns are [2-C, 2-C, 6)O, 6-C] and [2-C, 6-O, 6-C], while the third shell is [2-C, 2-C] and [6-C, 6-C]. Substitution points are assigned as being the topologically closest mapped atom, while the highest bond order is taken if there is a choice of pathways. Similarity between two fragments is determined by examining one shell at a time, and matching up pairs of atoms that are assigned to the same mapped atom. The score is computed as follows: 1 point for each pair, 1 point for both being carbon or both being heteroatoms, and 1 point for having the same bond order. When there are multiple mapping permutations, the best matched set of pairs is selected. The score for each shell is divided by N, which is the shell number, which starts at 1 and is incremented with each step in the breadth ﬁrst search. This method of comparing substituents is simple and fast, and emphasizes the value of sharing any substition at analogous positions, with those having similar topology and heterosubstitution being further favored. The assignment of a common numbering system is done recursively. For each unique root fragment, its root nodes are considered as a group. For each of these groups, the UQO equation is formulated and solved, which yields a unique solution for each member of the group. Once the atom equivalency is established for the group of substructures which share a tree node, these assignments are stored in the fragments themselves, and also percolated J. Chem. Inf. Model., Vol. 50, No. 1, 2010 39 through down the tree. The descendent nodes therefore share the common mapping within their partial substructures. The process is continued for each child fragment. Figure 4 illustrates the mapping procedure in a stepwise fashion. In Figure 4a, the assignment has been completed for the pyridine root fragment, which has been mapped for all four molecules. As can be seen, the mapping is such that the substitution is always at the atom labeled as number 6, which is an optimal solution. In Figure 4b and c, the process has been recursively applied to each of the distinct children of the root fragments, and a large proportion of the structures have been mapped. These two steps are carried out sepa- rately, so the numbering systems used for the benzyl and the methylfuran substituents are not related. Figure 4d shows the completed mapping, where tree singletons are assigned arbitrary numbers for the remaining atoms. 3. Colligative Depiction. The method for 2D layout of atom coordinates which we use in this work normally operates by searching for a globally optimum aesthetic ideal, which is the appropriate goal for depiction of individual molecules.7 When examining a set of molecules, such as the fragmentation tree we have described thus far, it is important to be able to represent common fragments with a common depiction motif. While this is often the case for unconstrained depiction, it cannot be relied upon, since arbitrary substituents may inﬂuence overall layout decisions in conﬂicting ways. Consider the following simple fragment, which has a prominent degree of freedom in the form of a methylene linker: Two different derivatives of this fragment clearly indicate that a free-for-all depiction is not the most suitable way to produce a common layout, since the common substructure fragments which correspond to the overall aesthetic ideal are no longer superimposable: To solve this problem, we make use of the tree structure and the mapping numbering scheme, to build up the fragment depictions sequentially. While the results must honor the requirement of common layout for common fragments, degrees of freedom within the constituent fragments are dealt with in a way that emphasizes overall layout aesthetics. As a ﬁrst step, we submit each of the input molecules to the depiction layout algorithm, without constraints, and store the new coordinates within the molecule datastructure. While many of the structures will have their coordinates further modiﬁed by subsequent depiction layout procedures, the coordinates obtained by unconstrained layout are used during the following procedure for clustering purposes. The tree is analyzed recursively, starting with each root fragment. For each sibling node, the 2D coordinates of the