a cornerstone of ligand optimization in drug discovery research is the comparison of activity and property data for a collection of molecules which are related by similar structural cores.(1 ) in order to rationalize the relationship between structure and activity , it is often beneficial to organize the structures in the form of a hierarchical tree . structures with a common core fragment are arranged in branches , in which each parent fragment is a smaller , pared - down substructure that is common to each of the children . if the tree is well constructed , considerable insight can be gained regarding which core fragments and which peripheral substituents are responsible for the properties of interest , such as binding affinity against some number of protein targets , toxicity , and relevant physical properties . given a collection of arbitrary molecular structures , there is typically no single unambiguous way to arrange them in a tree such that each parent node is a substructure of all its children . if the molecules happened to be synthesized in a particular sequence , such as by introducing a variety of substituents in a stepwise fashion to some number of similar core fragments , it may be sensible to produce a fragmentation tree which is based on the synthetic procedures . or , if a set of common scaffolds is already known , it may be sensible to start with these scaffolds as the root fragments , and from these , construct the descendency hierarchy . if the collection of molecules has significant structural similarity , but no specific information about common substructures is available , then algorithms exist for estimating which parts of a structure are most scaffold - like . these can be used to generate a fragmentation sequence which can then be expressed as a tree.(2 ) while the fragmentation techniques have been well developed , one part of the process remains conspicuously undocumented . a fragmentation tree of molecules with similar common scaffolds is significantly less informative if the 2d coordinates of the molecular diagrams are not arranged such that common fragments are drawn with a common layout and uniform orientation . molecular structures are often sketched by chemists showing a standard orientation when structures are added to a database , but this is not always the case . for a small group of structures , or for a rare showcase example , it is typically not a herculean task to manually ensure that all of the fragments are properly drawn and aligned . for larger collections , or if charged with the task of regularly regenerating this data , one would at least begin to feel like sisyphus . unfortunately , even if a good 2d depiction algorithm is already available , the procedure of generating 2d layout coordinates that honor common fragment ancestry , with group layout decisions made in the context of the global optimum , is not trivial . in this work , a method will be described for obtaining 2d coordinates suitable for structure diagrams , which are chosen for both independent aesthetic appeal and for clearly showing the common substructure patterns by means of layout and orientation . also discussed are higher level presentation methods for making use of the structureactivity information , which is contained in the fragmentation hierarchy . in the following section , methods will be described for generating a fragment tree , mapping sibling fragments onto each other in an optimal way , then using this mapping to guide the 2d depiction process . the results section will describe methods of presenting this information in the context of examining structureactivity relationships . for each molecule in the data set , it is necessary to propose a scheme whereby the molecule is peeled away in some number of steps , such that the last remaining fragments are the most scaffold - like . the definition 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 decomposition 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 modification 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 first 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 . ( 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 . in the following section , it will be necessary to know the correspondence between each fragment and its parent fragment . 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 
  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 molecules 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 first necessary to find 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 degenerate , it is desirable to consider an ensemble of possible solutions , and find 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 . an arbitrary numbering scheme is chosen for the pyridine root fragment of the first molecule . as shown for the first 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 the pyridine root fragment , there are multiple ways to map the branches to each other , which are not of equal quality . 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 find 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 sequentially and pick the case that best matches the previous assignments , the method described here uses the unary quadratic optimization ( uqo ) method,(5 ) which has previously 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 first search of the molecular graph , starting from each direct substitution point . for the first 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 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 first 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 , 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 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 separately , 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 . stepwise assignment of a common numbering system , for a fragmentation tree consisting of 4 molecules . 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 can not be relied upon , since arbitrary substituents may influence overall layout decisions in conflicting 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 first 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 modified 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 fragments comprising the node are extracted , and clustered in a greedy fashion . starting with the first set of coordinates as the first cluster , each subsequent set of coordinates is added to the same cluster as any fragment for which its coordinates can be superposed with an rmsd of less than 0.1  or to a new cluster if none . the common atom mapping scheme derived in the previous step if there is more than one cluster , which can occur when fragments have layout degrees of freedom such as rotational symmetry or aliphatic chains , the cluster with the largest number of members is selected . the first set of coordinates in this cluster is used as the definitive reference . for fragments that were found in the same cluster , this transformation is applied simultaneously to all fragments belonging to a particular molecule , not just the fragment under consideration . fragments which are not in the reference cluster require more sophisticated treatment . in each case , the whole molecule for the fragment is resubmitted to the depiction layout algorithm , with a special constraint : the coordinates for the fragment are submitted as a preblock , which forces the layout algorithm to construct the rest of the 2d molecule around the predefined fragment , whose coordinates are taken from the reference fragment . this process has been previously described for drawing molecules with common scaffolds , and is used to obtain coordinates which are optimal for the collection of molecules , if not necessarily each individual molecule.(6 ) the coordinates from all of the fragments corresponding to the whole molecule are updated accordingly . the fragmentation patterns for 3 molecules are shown , each of which has been subjected to unconstrained depiction layout . consider the fragments in column ( b ) , which form a single node in the resulting tree , and are directly descended from the common root fragment shown in ( a ) . the fragments ( 1,b ) and ( 2,b ) can be superposed onto each other , and so they are part of the same cluster of size 2 . fragment ( 3,b ) can not be superposed , and so it is assigned to its own cluster of size 1 . the coordinates of ( 1,b ) are used as the reference point . for the fragment ( 2,b ) , the coordinates are superposed onto the reference . for fragment ( 3,b ) , the coordinates are obtained by redepiction , using the reference coordinates as the preblock . same fragmentation tree as shown in figure 5 , after the colligative depiction layout procedure has been applied . 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 significant 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 sufficient to use a greedy algorithm , rather than a more rigorous clustering method . one begins by first defining 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 first translated so that the center of the root fragment is at the origin . a grid is defined , 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 defined by addition of a gaussian function , for each atom in each molecule : 

 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 : 

 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 . lower values indicate more similar grids . to find 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 corresponding 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 coordinates now encode significant information about shared structural features . 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 patterns this elicits information about the activities of the molecules which are represented by each node , which can be used to identify trends in activity data . figure 8 shows several subsets of the fragmentation hierarchy for a data set compiled to show activity against various species of dhfr , using the data set described in the previous section.(9 ) figure 8a shows a single root fragment , and several of the immediately descended fragments . each of the nodes provides an indication of the activity values against pneumocystis carinii dhfr of the constituent molecules by means of a colored pie chart display at the 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 . ( b and c ) selected child of the root fragment and a selection of their descendents . 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 constituents , 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 significant 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 , fingerprints 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 . once the ordering of the tree is determined , the actual layout of the dendrogram is straightforward . the final 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 structureactivity relationships . this is shown in figure 9 , which plots activity data against p. carinii , using the red / yellow / green activity scheme described in the previous 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 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 . combined with an interactive user interface which allows facile examination of the structures , which are represented by the fragment nodes , a significant amount of structureactivity information can be inferred from the layout and color - coding . a collection of 467 structures with corresponding activity against the cox-2 enzyme(9 ) 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 figure 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 oclock and 12 oclock 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 patterns , the final spatial orientation using 2d structures reveals the alignment shown . figure 12 shows a portion of a radial dendrogram , composed from the hierarchy of cox-2 inhibitors , using the same algorithm as described in the previous section . one sub - branch is shown in its entirety , and the structures of six of these compounds are shown . all of these compounds are based on the same 1,2-diphenylimidazole core , with a trifluoromethyl substituent in the 4-position . the activity values vary from 68 to 0.03 m . compounds a and b , as well as all of the compounds that are arranged in between them in the linear cluster , feature a sulfonamide substituent in the same position on the phenyl ring at the 1-position , and all of them exhibit high activity , as can be seen by the bright green color coding . the remainder of the compounds in this sub - branch have a methylsulfonyl substituent in place of sulfonamide , and their activity is much more varied and is determined by the substitution pattern on the phenyl ring at the 2-position . for example , compounds c and d , which have a small substituent in the meta position , exhibit strong activity , while compounds e and f , which have larger substituents , exhibit weaker activity . each of the compounds shown has a meta - substituted phenyl ring at the 2-position , and in each case , one of the meta substituents is depicted so that it is oriented at approximately the 2 oclock position . while an unconstrained depiction algorithm will be likely to make these layout choices on the grounds of congestion , the symmetrical phenyl substituents are explicitly mapped to each other on an atom - by - atom basis , in order to maximize the topological similarity of the interstructure mapping . a single depiction is chosen for the precursor fragment , and applied to all descendents , which ensures that the most similar substituents are placed at a consistent position . all algorithms described in this work have been implemented in svl ( scientific vector language ) , running in moe ( molecular operating environment).(12 ) the total processing time for the data set of dhfr inhibitors described in part 1 ( 397 compounds ) is approximately 16 s , measured on an intel 2.0 ghz 32-bit processor . the time taken for each step breaks down roughly as follows : initial depiction ( 4 s ) , fragment generation ( 2 s ) , deriving common mapping ( 4 s ) , colligative redepiction ( 2 s ) , and branch orientation ( 4 s ) . for the cox-2 inhibitors described in part 2 ( 467 compounds ) , the total time taken was approximately 50 s , of which 33 s were devoted to deriving the common mapping scheme . the rate limiting steps scale linearly in proportion to the number of input molecules , with the exception of the mapping step , in the presence of symmetry - containing fragments . an abundance of degenerate partial fragments causes the uqo portion of the common mapping algorithm to dedicate additional computational resources to finding an optimal mapping . this is the principal reason why the cox-2 data set takes longer to analyze than does the dhfr data set , since the dhfr inhibitors are largely based on heterocyclic ring blocks with low symmetry , while the core fragments of the cox-2 inhibitors contain an abundance of substituents , such as phenyl rings , that have rotational symmetry . a method has been demonstrated for treating scaffold - like fragmentation trees so that common ancestor fragments are depicted and oriented in a consistent way that makes common structural features readily evident to the observing chemist . the algorithm operates without supervision and produces aesthetically desirable results using a combination of new and preexisting techniques . with the molecule layout and orientation method established , software applications that present fragmentation trees become significantly more valuable to medicinal chemists . there is no longer a requirement to sketch the input molecules in any particular way , nor is it necessary to postprocess the structures to elicit insight into the structureactivity information that is encoded in such trees . the value of presenting structural data in this way has been demonstrated , by using high - level and medium - level hierarchical tree views , which combine constrained clustering with activity color - coding , and the ability to examine individual structures that have a common depiction and orientation . such views are effective ways to examine structureactivity data , and the algorithms that have been described essentially remove the manual effort required to produce them . use of such visualization and grouping tools can allow the user to make intuitive selections of compounds for further development . for example , if a set of compounds which has balanced activity and diverse structure is necessary for producing a qsar validation set , either the tree or dendrogram presentation methods could be used to identify such a subset , either by visual inspection or automated selection . alternatively , when considering hypothetical new compounds to add to the collection , it may be informative to depict them under the same conditions as for the existing compounds , and insert them into their appropriate locations within the hierarchy according to the ordering scheme used by the visualization method . examination of the patterns exhibited by neighboring structures may aid in qualitatively assessing the expected properties of the compound . future research will involve developing new ways to present information - rich , easily comprehensible graphics in a concise area , for example , single computer screen , projected slide or printed page , as well as developing interactive user interfaces for arranging and querying content data . the hierarchical atom - to - atom mapping system developed in this work has been used primarily for depiction purposes , but the assignment can also be used to differentiate scaffolds vs substituents at any level within the hierarchy , which opens up possibilities for fragment - based qsar and clustering studies .
drug discovery projects often involve organizing compounds in the form of a hierarchical tree , where each node is a substructure fragment shared by all of its descendent nodes . 
 a method is described for producing 2d depiction layout coordinates for each of the nodes in such a tree , ensuring that common fragments within molecular structures are drawn in an identical way , and arranged with a consistent orientation . 
 this is achieved by first deriving a common numbering scheme for common fragments , then using this scheme to redepict each of the molecules , one fragment at a time , so that common fragments have common depiction motifs . 
 once complete , the distinct root branches can be overlaid onto each other , after which all of the fragments and whole molecules have a common layout and orientation . 
 several methods are described for preparing visual representations of molecular structure hierarchies alongside activity information . 
 combining high level tree display and structure depiction showing common features readily facilitates insight into structureactivity relationships .