   design   of new   medical drugs is an exhaustive process with many challenges .
that is , they are used to examine different compounds with a desired activity and extract some common substructures that provide this activity .
several methods are proposed to determine a mathematical equation correlating different properties of the compounds .
these methods are called as quantitative structure activity relationships methods . several other methods known as qualitative - sar methods examine different compounds and extract some common significant substructures with desired activity . in this paper ,
the main focus is a qualitative - sar method that uses active fragments as a map to guide for molecular design .
an active fragment ( pharmacophore ) is a set of similar structural features in the structure of active molecules ( or drugs ) that is responsible for their biological activity .
a graph is a kind of data structure that consists of a set of nodes and a set of edges between them .
for example , in a 3d fully weighted molecular graph representation , each node may represent characteristic features of atoms ( e.g. , electrical properties ) , and each edge may represent characteristic   features of bonds between them ( e.g. , length , value of wiberg 's index , and so on ) .
therefore , researchers study frequent subgraph mining approaches [ 2 , 3 ] to find frequency of common fragments ( e.g. , pharmacophores ) , which is a collection of bonds and atoms in the structure of compounds with the same activity for a specific disease .
the success of the proposed methods relies on the features used for the representation . as the complexity of representation increases , interpretation of the represented molecular information becomes harder , because the graph - based approaches usually have high complexities .
for example , while comparing two molecules in terms of their structure and activity , it may be necessary to compare their substructures , which are represented as graphs .
unfortunately , deciding whether two graphs have identical topological structures or not has an unknown complexity .
the subproblem that is deciding whether one graph is a subgraph of another or not is known to be np - complete . therefore , frequent subgraph mining approaches may not find exact solutions in a bounded time because of their high complexities .
researchers use heuristics to reduce search space while solving subgraph mining problems [ 5 , 6 ] . in this way
, they try to get rid of high computational burden inherent to these problems . for example , subdue algorithm uses a greedy search technique for frequent subgraph mining   to reduce the time complexity with a possible cost of missing some important substructures . as stated above
, many researches convert the problem of discovering frequent substructures in active molecules into a frequent subgraph discovery problem , in order to use graph mining approaches .
however , current graph mining approaches can determine frequent subgraphs only if these subgraphs repeat exactly the same in a graph database .
therefore , in many settings , these methods may not find the most informative substructures that do not exactly repeat in the molecules but exist   in those molecules with some fine differences . furthermore , because these approaches work like black boxes , domain experts can not easily interrupt the process to incorporate their knowledge into the solution .
that is , another problem related to current substructure discovery approaches is their blind calculations .
therefore , even if these approaches find solutions , their solutions should be extensively examined , tested , and verified at the end by the domain experts .
this leads to a system where any failure in the early stages of the process can not be corrected until the overall process is completed .
alternatively , in this paper , we advocate directly incorporating domain knowledge into the solution process at different levels . for this purpose
, we propose to use a data pipelining approach , where domain experts can intervene the overall process to enhance the solution with their knowledge and expertise .
more specifically , in this paper , we propose a visual data mining method for frequent substructure extraction , where histogram - based filtering method is used to reduce the search space . in our approach ,
graph representations of molecules are projected into a 3d feature space ( named atom - bond - atom space ) .
each bond of a molecule ( an edge with nodes at each end in the graph ) is represented as a point in this space .
when we project all of the molecules with a certain activity into this space , the resulting points compose clusters of bonds that are repeated in the structure of the active molecules ( possibly with fine differences ) . however , discovering these clusters is nontrivial because of the noisy points that represent infrequent bonds . at this stage ,
we filter the noise using a histogram - based visual data mining method   so that the clusters can be discovered more clearly by various clustering algorithms .
once the clusters are discovered , frequent substructures of active molecules are computed . during all these steps ,
a domain expert can intervene to guide the system if necessary ( e.g. , during filtering , clustering , and so on ) .
we demonstrate how our approach can determine frequent substructures of molecules step by step through a case study , using the tuberculosis dataset from    literature [ 7 , 8 ] .
our experiments show that our approach can successfully determine active fragments that account for the activity of those molecules .
we lastly show how the determined fragments can be used as features to automatically categorize new molecules as active or inactive with respect to a specific disease .
we experimentally evaluate the performance of the proposed approach with respect to other approaches from    literature .
   there are two groups of sar methods . the first one is known as quantitative - sar , which derives a correlation between the descriptors of molecules and their activity .
then , different machine learning techniques are applied to the prepared dataset as described in    literature to learn how to classify molecules .
linear discriminant analysis ( lda ) , multilayer perceptrons , support vector machines ( svm ) , k - nearest neighbors ( k - nn ) , simulated annealing , partial least squares , linear regression , and classification trees are the most studied methods on quantitative - sar for classification of molecules [ 9 , 10 ] . qualitative - sar is the second group of approaches which is interested in finding some common substructures in the structure of molecules .
there are many approaches related to qualitative - sar in   literature which are based on frequent substructure mining methods .
some qualitative - sar approaches use graph mining methods to find common substructures that exist in active molecules with high probability , but exist in inactive molecules with low probability [ 2 , 3 ] .
our research is related mainly to two important research areas : frequent substructure extraction and visual data mining . especially in qualitative - sar applications ,
graph - based data mining approaches are used to find frequent substructures ( subgraphs ) in graph - based mass datasets .
graph isomorphism is the problem of deciding whether two graphs have identical structures ( e.g. , finding common fragments from two molecules ) .
the second problem , subgraph isomorphism , is the problem of deciding whether one graph is a subgraph of another graph .
graph - based frequent substructure extraction methods avoid this high complexity using some limitations . in recent years
they rely their approaches on candidate subgraph extraction processes and pruning some of them using some methods or representations .
subdue is one of the well - known graph - based frequent substructure mining approaches .
simplifying the data by compressing repetitive substructures , subdue method finds frequent substructures within the data .
it also enables abstraction of detailed and complex structural data by iteratively constructing a hierarchical description of it . the algorithm first searches a single vertex that matches with the substructure . at each iteration
, algorithm expands matching substructure using a greedy selection of best suitable neighbor edges until all possible substructures are found .
subdue finds an incomplete set of frequent substructures , because of the greedy idea behind it .
some other approaches depend on the principle of a priori algorithm in basket analysis . a priori - based frequent substructure mining methods extract association rules which have higher support and confidence than those of   a threshold value .
for example , to minimize computation and storage , frequent subgraph discovery ( fsg ) algorithm also uses canonical representations .
a graph can be represented with many different canonical labels depending on the orders of vertices and edges .
therefore , fsg searches all permutations of vertices to find a unique canonical label . to narrow down the search space , vertex invariants technique that partitions the graph into subgraphs ( not mentioning candidate frequent subgraphs )
fsg generates candidate subgraphs and increases the size of the candidate subgraphs by adding one edge to   each candidate at each time . using a breadth - first approach
frequencies of achieved candidate subgraphs are calculated to prune the subgraphs that do not satisfy the support constraint . for each candidate , a mapping with the other graph is searched to solve the graph isomorphism problem using canonical representations .
graph - based substructure pattern mining ( gspan ) transforms the problem into finding common related parts in depth - first search ( dfs ) codes to find frequent subgraphs .
it uses depth - first search tree structure and dfs lexicographic order to find frequent subgraphs . in this approach
, each graph has a dfs code , and minimum dfs codes are used for comparison of two graphs .
there is a counter in each node that shows the number of graphs including the subgraph . to prune the search space in the tree structure ,
, it removes nodes which have a counter value smaller than support threshold value . in the second one
, it removes nodes which have a number of nodes more than the desired number of nodes .
it also uses a tree structure where each node represents a subgraph and uses depth - first search in the tree structure .
inductive logic programming ( ilp ) is one of the well - known techniques in graph mining .
although many graph - based searching approaches focus only on instances from only one class , ilp uses observations from every class .
however , it generally does not support numerical calculations and can not model quantitative classification problems .
   in this section , we propose a novel approach to discover frequent fragments of active and inactive molecules .
previous researches mostly use graph - based frequent substructure mining methods to discover frequent active fragments that account    for the activity of the molecules for a specific disease [ 3 , 11 ] .
however , these methods work like black boxes where the data with some parameters are fed in the beginning and the solution is outputted at the end .
hence , domain experts can not easily interrupt the process to incorporate their knowledge into the solution .
this leads to two main problems : ( 1 ) the found solutions should be extensively examined by the domain experts at the end and ( 2 ) any failure in the early stages of the process can not be corrected by the domain experts until the overall process is completed . in this paper
, we advocate directly incorporating domain knowledge into the solution process at different levels . for this purpose
, we propose to use a data pipelining approach , where domain experts or users can intervene the overall process to enhance the solution with their knowledge and expertise .    

figure 1 shows the data flow diagram of the proposed data pipelining structure , where raw molecular data from a dataset are filtered iteratively .
the dataset contains 3d graph representations of molecules that are either active or inactive with respect to a specific disease , for which a new drug is to be designed . with the proposed data pipelining , a domain expert or a user is able to provide critical information to the system at the intermediate steps . at the beginning
using these parameters and the dataset , the system computes two histogram - based visual representations as described in section 3.2 : activity map and inactivity map .
before the fragment mining begins , activity and inactivity maps are displayed to the user to show information about candidate frequent fragments for the active and inactive molecules , respectively .
if the candidate frequent fragments are not clearly seen from the visual representations , the user can change the parameters .
once the resulting maps are satisfactory for the user , infrequent and insignificant substructures in the data are filtered automatically using the proposed approach in section 3.2 . after filtering process
then , the proposed method transforms filtered data to atom - bond - atom space , where each point represents features of a bond .
these clusters can be determined by a suitable clustering algorithm easily as described in section 3.4 , because the filtering step eliminates insignificant and infrequent fragments that constitute the noise between the clusters in atom - bond - atom space . at the initial step of clustering ,
the found clusters are converted to the corresponding 3d fragments and visualized to the user . using the advantage of data pipelining structure ,
the user can change the automatically calculated parameters of the clustering algorithm depending on her / his expertise after analyzing the visualized 3d fragments . as a result ,
she / he either confirms these clusters or tunes the clustering parameters to force the system to recalculate clusters depending on the new parameter values . once the user confirms the computed clusters , unfiltered data and cluster information are used for fragment discovery as described in section 3.4 . because we use the whole dataset ( unfiltered data ) together with the cluster information , fragment discovery is not significantly affected by the data loss caused by the filtering process . using the proposed pipelining structure , we enable users to enhance the solution with their domain knowledge and expertise .
if the users are not confident with their expertise , they can simply confirm the automatically calculated intermediate results ( e.g. , discovered clusters ) . in this case , the overall system works almost like a fully automated process .   
although edges and nodes are used to represent some properties of molecules , it is inefficient to compare different properties of molecules using 3d graph visualization . in this paper , a transformation from 3d graphs to molecular information visualization
is implemented . to make this representation more understandable to the experts , images that display information about molecules are created .
to represent molecular graphs , electron - topological matrices of conjugency ( etmc ) are used . in this method , a molecule with n atoms is represented with a number of upper triangular fully weighted etmc matrices , each representing various characteristics of molecules .
the main advantages of etmc matrices are that their molecular representation reflect a molecule 's electronic and 3d conformational properties and do not depend on the numbers and types of atoms : 
 ( 1)etmc=[a1,1a1,2a1,n1a1,na2,2a2,n1a2,nan1,n1an1,nan , n ] . 
 
in our study , diagonal elements ai , i ( i = j ) of an etmc matrix contain information about electronic properties of atoms , and nondiagonal elements ai , j ( i  j ) include information about chemical properties of bonds between the corresponding atoms in etmc matrix representation .
if there is no bond , the distance between two atoms is used instead . for various characteristics   of molecules ( e.g. , bond properties such as value of wiberg 's index ) ,
hence , different descriptors of molecules can be examined for their accountability on activity for a specific disease . for all integer values of i and
j  ( 1  i , j  n ) ,   vectors [ ai , j , min  ( ai , i , aj , j ) , max  ( ai , i , aj , j ) ] are obtained from etmc matrices . hence , corresponding molecules are split into pieces ( bonds ) , where each bond is represented with a vector including information about the bond ( ai , j ) and two atoms at each end   ( ai , i and aj , j ) . these pieces are plotted with point pairs , ( ai , j , min  ( ai , i , aj , j ) ) and ( ai , j , max  ( ai , i , aj , j ) ) , using a transformation from 3d to 2d coordinate system as shown in figure 2 .
thus , points are derived from an etmc matrix   and then projected onto 2d cartesian system . in the following section ,
we propose a visual data mining approach that uses the points derived from etmc matrices .     in this section
therefore , we enhance the understandability of the molecular information by the experts and enable the experts to compare different molecules easily in terms of their desired descriptors .
one of the problems while comparing molecules is that molecules posseses different degrees of flexibility .
because of this flexibility , even the topological structure of the same molecule can vary under different conditions .
therefore , values from etmc matrices can not be compared in a straightforward manner . to overcome this difficulty
first , a 2d image is generated from the etmc matrix of a molecule by dividing   x , y coordinate system into regular intervals in order to compose a 2d mesh . for this purpose ,
two parameters are used : x and y . using the parameter x ,   x - axis of the coordinate system is divided into the intervals   so that the width of each interval is x .
the crossing intervals on the coordinate system compose a 2d mesh ( a regular grid ) . in   literature ,
moreover , when finding similar frequent substructures , a general grid structure common for every molecule is needed .
however , it is difficult to fix an irregular grid suitable for every molecule , because of the noisy data .
hence , not to increase complexity of process , a regular grid structure is used in this work .
then , the rectangular regions of the mesh where the points fall   are shaded .
figure 3 shows an example for the creation of a 2d image from an etmc matrix .   in our   dataset
, we have two different disjoint classes of molecules : active molecules and inactive molecules . using the methods described above , we produce images for each molecule in the dataset .
now , using these images , we describe how to compose activity and inactivity maps that show characteristic properties of active and inactive molecules , respectively .
that is , each map shows the percentage of bonds that are common for the corresponding class of molecules .
hence , the frequent bonds in each class of molecules are seen easily on the related map . for active molecules ,
this time , shades of the rectangles in the activity map denote   percentage of molecules falling into the rectangular cells . for this purpose ,
we use a 2d histogram - based visualization method that shows frequent active fragments in the molecular dataset   as follows .
a rectangle ri , j can be considered in the 2d mesh , where 0 < i  n and 0 < j  m. in order to determine the shade of each ri , j in the activity map , we average the shade of the corresponding rectangles ri , j in the images of the active molecules . in order to average shades ,
hence , an activity map gives information about the parts of molecules that appear frequently in the structure of active molecules in a better perceivable format .
the same methodology is used for creation of the inactivity maps , but this time , images from the inactive molecules are used , instead of images from the active molecules .
resulting activity and inactivity maps provide important perceivable information to the experts using a histogram - based data visualization . for example
, the activity map in figure 4 shows the rectangles with darker and lighter shades .
the dark fragments are the structures that are common to the most of the active molecules , whereas the lighter fragments represent the structures that are not repeating in the active molecules , so those fragments may not be significant for the activity . for various characteristics of molecules ,
we filter the substructures of active molecules if these substructures fall into the lighter rectangles in the activity map . for this purpose
if the dataset is noisy ( i.e , it highly contains infrequent fragments ) , a small threshold value will be chosen ; otherwise , the chosen threshold value will be high . in summary ,
first an activity map is constructed using all of the active molecules in the dataset , then algorithm determines the insignificant parts of each molecule in the dataset using the decisions of expert ( e.g. , provided threshold ) .
lastly , the determined parts are filtered to eliminate redundant and noisy information . alternatively , in respect to her / his domain knowledge and expertise , data falling into some regions on the activity map can be removed directly by the expert .
selection of x and y parameters does not affect the extracted active fragments significantly , because the filtered data give   only preliminary information about activity and inactivity clusters .
nevertheless , several values of the x and y parameters should be tried for the best filtering and the best results .  
after filtering the data using activity and inactivity maps as described in section 3.3 , redundant and noisy bonds are removed from the active molecules in the dataset .
the remaining bonds of the active molecules may contain the ones that compose active fragments , so we mine these bonds to discover these fragments .
first , the remaining bonds of each active molecule are transformed into 3d atom - bond - atom space , where features of each bond ( and the atoms at its each end ) are represented as a single point .
hence , an active molecule with m remaining bonds after filtering is represented with m points .
each point is in the form of ai , j , min  ( ai , i , aj , j ) , max  ( ai , i , aj , j ) , where ai , j ,   ai , i , and aj , j are values from the etmc matrix of the molecule and correspond to feature values of a bond and feature values of the atoms connected by this bond , respectively . in this way , bonds of the active molecules are transformed into the 3d atom - bond - atom space .
the result is a set of points that are distributed over the space , where the points representing bonds with similar features are in proximity .
that is , the points are not distributed randomly in the space , but in a way that groups of points representing bonds with similar properties appear .
we name these groups of points as candidate activity clusters , which are used to derive candidates of active fragments . in order to find candidates of activity clusters , we use average - link clustering method . in this clustering method , initially each point in the space is regarded as an individual cluster .
that is , two clusters are merged if their distance is smaller than that in a predefined threshold .
each of   found clusters is composed of points that represent bond patterns of active molecules .
however , all of these substructures may not be considered as active fragments , because some of them may also be repeated in the inactive molecules .
active fragments should be the substructures that exist frequently in active molecules , but rarely in inactive molecules .
this means that we are looking for clusters that are composed of bond patterns that are not repeated in the inactive molecules .
therefore , after determining clusters , for each cluster , we compute the percentage of active and inactive molecules that contain the molecular pieces in the cluster .
the candidate clusters including higher percentages of active molecule bonds and small percentage of inactive molecule bonds are regarded as activity clusters .
bonds falling into active clusters are expected to compose active fragments .   in order to show advantage of the proposed filtering method
, we show the points extracted from raw molecular data in figure 5 and the filtered molecular data in figure 6 in the 3d atom - bond - atom space .
although , figure 5 gives a messy view of the molecular data , figure 6 gives a cleaner view of clusters on the filtered data , because noise and uninformative points that show infrequent substructures ( bonds ) are removed from the data after filtering . in figure 9 , we show the resulting clusters on the filtered data with an example of molecule 's two pieces falling into two activity clusters . as we mentioned before , time complexity of subgraph isomorphism
hence , heuristics are used instead of exact algorithms to solve frequent substructure discovery problem in graphs . in this paper
this approach is composed of four sequential steps : activity map creation , filtering , clustering , and fragment extraction .
the highest complexity belongs to clustering step , where average - link clustering is used .
complexity of the used clustering algorithm is   o(n  m ) , where n is the number of molecules in the dataset and m is the maximum number of atoms in a molecule .
therefore , the overall computational complexity of the proposed approach is only   o(n  m ) .
   in order to demonstrate our approach better , we design realistic experiments with real - life data and simulations on the synthesized graphs . in our experiments , we have used antituberculosis dataset [ 7 , 8 ] .
this dataset is composed of 33 molecules ( 13 active and 20 inactive molecules ) . in order to examine our approach extensively
first , in section 4.1 , we show a case study to demonstrate how an expert can use our approach for creating activity and inactivity maps and deriving active fragments interactively .
second , using antituberculosis dataset and synthetic datasets , we   empirically compare our approach with the well - known approaches from   literature : subdue , fsg , gspan , gaston , mofa , and ffsm .
we have repeated each experiment 10 times and our results are significant according to 2-tailed   t - test with 95% confidence level .  
third , in section 4.4 , we derive active and inactive fragments from the antituberculosis dataset .
then , we use the derived fragments as features and evaluate the performance of well - known classification methods in classifying molecules as active or inactive . intuitively , if our approach is successful in determining active and inactive fragments that account for the activity and inactivity of the molecules , then the classification methods using those fragments as features are expected to demonstrate a good performance .
all the experiments of the proposed method are tested on 1.6  ghz intel pentium core ii duo , 1  gb ram running windows vista operating system , and matlab 7.1 . to make the approach easily repeatable , we used prtools toolbox for classification methods .
those parameters are selected as x = 0.12 and y = 0.07 by the expert . using those parameters , activity and inactivity maps
are created as in figures 7 and 8 , respectively . using those activity and inactivity maps
this threshold value is decided by the expert in order to keep more information unfiltered . although it may seem that using a 2d activity maps rather than a 3d representation may cause loss of data .
it is important to note that   these maps are only used in finding approximate locations of clusters where unfiltered data and the preliminary information about clusters are fully preserved .
lastly , using unfiltered data and preliminary information about the clusters , the system finds final active fragments . to visualize 3d topology of active fragments , an active template molecule that is selected by the expert is used .
graph - based representation of extracted active fragments on the template molecule is shown at figure 9 .  
we measure the processing time of each step of our approach during the case study .
we tabulate these values in table 2 , where the time consumed during human - computer interactions is neglected .
our approach consumes around 20 seconds for clustering , while it consumes around only 2 , 0.5 , and 0.7 seconds for activity map creation , filtering , and fragment extraction , respectively .
the overall time from beginning to finding active fragments on the case study ( including the time consumed during human - computer interactions ) is around 11 minutes .     in this section , using the antituberculosis dataset , we compare our approach with two well - known approaches from   literature : subdue and fsg .
these approaches are chosen , because they are often used in   literature to find frequent substructures of graphs and molecules .
therefore , we   have used only the active molecules to determine active fragments by fsg and neglected inactive molecules which cause a great decrease in the success of fsg . in our experiments ,
we use publicly available original implementations of subdue ( http://ailab.wsu.edu/subdue )   and fsg ( http://glaros.dtc.umn.edu/gkhome/pafi/overview ) in order to increase reliability and repeatability . for the basis of comparisons
, we use a set of   active fragments ( fa * ) that are determined for antituberculosis using extensive analysis in . in order to compare subdue , fsg , and the proposed approach
let fa , fa , and fa represent the sets of active fragments computed by subdue , fsg , and the proposed approach , respectively .
then , we compare the most significant fragments in fa , fa , and fa with the ones in fa*. by the most significant fragment , we mean the fragment that has the largest support value , which represents the percentage of active molecules including this active fragment at the dataset .
let sa ,   sa ,   sa , and sa * denote the most significant fragments in fa , fa , fa , and fa*. for comparison of the methods , we used two measures : recall and precision .
recall is defined in    ( 2 ) as the ratio of correctly discovered bonds of sa * by an approach . in the equation ,  
f(b , s ) is a function that returns 1 if the bond b is contained by the fragment s ( b  s ) ; otherwise , it returns 0 .
high recall value of an approach implies that it can correctly find most of the bonds in sa * , which is the most significant active fragment  
 ( 2)recall(x)=bsa*f(b , sax)|sa*| . 
							 using only the recall metric
, we can not measure success of an approach in determining active fragments , because this measure does not use the excess bonds found by the approach .
that is , recall of an approach x is 1 if sa  sa * or sa *  sa , where x finds also the bonds that are not a part of an active fragment ( sa * ) .
therefore , we introduce precision metric in    ( 3 ) . the precision value of an approach x is high if all of the bonds in sa are included in sa*. if both of the recall and precision values are close to 1.0 for an approach , this means that this approach can correctly and precisely find most significant active fragments  
 ( 3)precision(x)=bsaxf(b , sa*)|sax| . 
 
the table implies that our approach can correctly determine the most significant active fragments , because its recall and precision values are both close to 1.0 .
although   the performance of subdue is also high , our approach significantly outperforms it . unlike subdue and the proposed approach ,
the performance of fsg is low ; its recall and precision values are 0.40 and 0.67 , respectively .
this performance difference is intuitive , because fsg can not use the class information ( e.g. , active molecule and inactive molecule ) while determining fragments .
although fsg can find fragments belonging to active molecules , these fragments may not be active fragments , because they may also repeat in the structure of inactive molecules .
however , unlike fsg but similar to the proposed approach , subdue uses class information while determining frequent fragments .
hence , it can determine frequent fragments that exist in active molecules but not in inactive molecules .
therefore , in our experiments , performance of subdue is higher than the performance of fsg .
these findings imply that inactive molecules may have a significant importance on determining active fragments .
hence an approach that uses both active and inactive molecules should be used to solve active fragment discovery for drug design .  
one of the main deficiencies in the methods proposed in graph - based data mining is their narrow view on the problem .
however , molecules may have fragments that give them activity with respect to a specific disease , but these fragments may not repeat exactly in each active molecule . instead , these fragments may repeat with some deviations , which implies the necessity of subgraph mining methods that    discover not only exactly repeating substructures but also the ones that repeat with some deviations . in this paper , we propose a clustering - based molecular graph mining method for frequent substructure extraction , where pieces ( atom - bond - atom triples ) with similar features fall into the same clusters .
this enables frequent substructures to be discovered even though these substructures repeat in molecules with some variations . in this part of our experiments , using synthetic datasets , we show how successful our approach is with respect to others when substructures giving activity to a molecule do not exactly repeat   but repeat with some small variations .
we compare the proposed approach with parmol   ( http://www2.cs.fau.de/forschung/projekte/parmol/ )   package for frequent molecular subgraph mining , which includes publicly available implementations of gspan , gaston , mofa , and ffsm .
we compare our approach with these well - known methods using the synthetic datasets . like the proposed approach ,
a synthetic graph dataset is composed of two sets of graphs : the graphs representing active molecules ( sa ) and the graphs representing inactive molecules ( si ) . in these graphs ,
labels are real numbers , where the nodes and edges take their labels in the ranges of [ 04 ] and [ 06 ] , respectively . before creating the graphs in sa or si ,
we first create three different sets of patterns : the subgraphs repeating only in active molecules ( pa ) , the subgraphs repeating only in inactive molecules ( pi ) , and lastly the subgraphs repeating both in active and inactive molecules ( pai ) .
each graph g  sa is created so that it includes subgraphs from both pa and pai .
however , before adding these subgraphs to g , we modify them according to a parameter pn , called probability of noise .
this is done because of the fact that a pattern may not exactly repeat in real - life molecular datasets ; instead the same pattern may repeat in different molecules with slight variations . if pn = 0 , then we directly add subgraphs from sa and sa i to g. however , if pn > 0 , then we slightly modify the labels of the nodes and edges in these subgraphs with probability pn by adding some noise , before adding them to g. the amount of noise to be added is determined randomly in the range of [ 00.25 ] .
we also add m other nodes to g , where the number m and the labels of these nodes are chosen randomly . in order to ensure connectivity of the graph , we add edges randomly between these nodes and the others .
lastly , we randomly give a unique i d to each node in the graph .
similarly , we create graphs for inactive molecules , but this time these graphs are produced using the patterns from pi and pai . using this procedure ,
we compute a number of graphs representing active and inactive molecules . in the resulting graph dataset ,
some similar patterns repeat in almost every graph , while some others repeat only in the graphs representing either the active molecules or the inactive molecules .
there is a similar case in the real - life datasets , where only the substructures repeating in active molecules are responsible for the activity of the molecule , while the substructures repeating almost in every molecule or only in the inactive molecules do not have any significant effect on the activity .
we created eight different datasets using different numbers of active and inactive molecules as well as different values for the probability of noise .
for each dataset , we exactly know which subgraphs are repeating only in the graphs representing active molecules .
note that these subgraphs are not repeating exactly the same but with some small differences ( called noise ) .
hence , we can quantitatively measure how successful our approach is , compared to the other approaches ( gspan , gaston , mofa , and ffsm ) , while finding these subgraphs .
our experiments show that the proposed approach and the graph mining methods gspan , gaston , mofa , and ffsm can find all of the active substructures correctly when there is no noise ( pn = 0 ) . however , an increase in the probability of noise results in a dramatic performance decrease in the graph mining methods gspan , gaston , mofa , and ffsm . for example , when pn is increased to 0.25 , although their precisions remain 1.0 , the recall values of gspan , gaston , mofa , and ffsm decrease to 0.33 , 0.28 , 0.21 , and   0.19 , respectively .
this means that they do not find fragments that are not frequent ( precision is 1.0 ) , but they can only find 33% , 28% , 21% , and 19% of the frequent fragments , respectively .
on the other hand , precision and recall of the proposed approach are both 1.0 , which means that the proposed approach can correctly determine frequent fragments even though these fragments do not eactly repeat in molecules , but repeat   with some variations ( pn = 0.25 ) .
the situation becomes more dramatic when pn becomes 1.0 ; both    precision and recall become zero for gspan , gaston , mofa , and ffsm .
this means that they can not find any part of the frequent fragments , because nodes and edges in these fragments do not exactly repeat in molecules .
in all these cases , our approach can find almost all of the active substructures correctly ; it has precision and recall values almost equal to 1.0 when pn > 0 . for varying size of the datasets , performance of our approach does not change .
these experiments show that our approach can successfully find frequent substructures even though these substructures do not repeat exactly in the molecules ; however , the other methods can find these substructures correctly only if they repeat exactly the same in the molecules ( pn = 0 ) . searching a molecular substructure rapidly in a molecular database is an important research problem in drug design . in    literature , graph - mining techniques
are mostly used to search molecular databases for the new molecules that are likely to be active for a specific disease [ 1 , 21 ] .
using classical graph - searching methods , it is difficult to find molecules with specific frequent substructures , because of the time complexity of subgraph isomorphism . instead of using graph - searching methods , classification methods from    machine learning literature
are also used for the estimation of active and inactive molecules in a molecular database .
therefore , the molecular data should be preprocessed before using these methods . in this paper
, we propose an approach for deriving active fragments that account for the activity of the active molecules .
we can also derive inactive fragments from inactive molecules using the same method . in this case , the derived inactive fragments account for the inactivity of the inactive molecules .
then , we can use information about activity and inactivity clusters ( representing active and inactive fragments ) as features to represent each molecule using the same dimensions .
let us have n1 activity clusters and n2 inactivity clusters that we derive using the proposed approach .
for each molecule , we prepare an array of n1 + n2 dimensions , where each dimension represents one cluster . if the molecule has an active or inactive fragment , the corresponding dimension of the vector is set to the minimum distance from the points of molecules to the corresponding cluster 's center ; otherwise , it is set to 0 . this way ,
then , we input this training set to different classifiers : lda , k - nn , svm , and decision trees ( dt ) .
lastly , using one - leave - out cross validation method , we measure the classification performance of the classifiers .
then , for each molecule in the dataset , they compose a feature array of a + b dimensions , where each dimension takes binary values ( 1 or 0 ) to show   whether a specific fragment exists in the molecule or not . using the derived arrays as training set
, they train a classifier to measure how well the derived fragments can be used to classify molecules as active or inactive with respect to antituberculosis . their activity / inactivity prediction using leave
- one - out cross validation is 80% . in order to measure the performance of our approach better
, we also train the classifiers with the original unfiltered data that    contain not only active / inactive fragments but also other fragments that are filtered out while determining these active / inactive fragments .
unfiltered data contain more information about the molecules , so classifiers using the unfiltered data may have a better performance with respect to their performance using only a subset of these data ( i.e. , only active and inactive fragments ) .
our main aim in this paper is to correctly determine active / inactive fragments that are responsible for the activity / inactivity of the molecules .
if we determine these fragments correctly , the classifiers using only those fragments as features should also demonstrate a good performance in classifying molecules . in table 5
, we tabulate our results for x = 0.12 and y = 0.07 using the original ( unfiltered ) data and the filtered data , where only active and inactive fragments are used as features .
our results show that most of the classifiers ( except lda ) achieve the same performance when they use only active / inactive fragments as features ( filtered data ) and when they use the whole molecular data ( unfiltered data ) . in our experiments
, the best performance belongs to svm and dt classifiers , which always correctly classify active and inactive molecules ( success is 100% ) .
performance of other classifiers is also very good ; almost all of the classifiers can correctly classify molecules in more than 95% of the cases .
we immediately recognize that lda can not find active molecules and labels all of the molecules as inactive when unfiltered data are used .
the reason behind this is the fact that lda maps all data into a ( c  1)-dimensional feature space , where c is the number of classes . in our case
, there are only two classes , which means that lda tries to discriminate these two classes in a 1-dimensional space . since the unfiltered data contain highly overlapping structures and features between active and inactive molecules , classification in a 1-dimensional space is clearly not enough when unfiltered data are used . however ,
when we filter the data using the proposed method , we remove the common and noisy parts of the molecules that are not significant for being active or inactive .
hence , lda can successfully learn active and inactive molecules in a 1-dimensional space using the filtered data .
those results imply that our approach can correctly determine the active and inactive fragments , and those fragments can successfully be used as features in classification .
moreover , when the classifiers use only the active / inactive fragments extracted from filtered data rather than fragments extracted from original ( unfiltered ) data , it is observed that overall classification process is 2.7 times faster .
   infectious diseases like tuberculosis are the leading causes of death and suffering worldwide . the world organization of health reports a significant rise in drug resistance of diseases like tuberculosis .
this increasing drug resistance highlights the need for new , safer , and more effective drugs .
however , designing new drugs is an exhaustive process , where discovery of fragments that account for biological activity and prediction of biological activity in relation to the chemical structures of molecules are crucial . in this paper , we extend our previous studies in .
unlike the previous work , this paper discusses the role of human experts in the process , presents computational complexity of the overall approach , analyzes the robustness of the approach to the noise , and lastly compares the proposed approach with current approaches ffsm , mofa , gspan , and gaston in detail using synthetic datasets .
first , previous graph - based approaches for frequent pattern mining methods are fully automated and do not allow experts to interact with the system to incorporate their expertise to the process .
however , the proposed approach enables experts to interact with the system and improve the solution with their expertise .
second , current methods can determine frequent patterns only if these patterns exactly repeat in molecules .
however , in many settings , patterns may not repeat exactly , but with some variations .
for example , in different conditions ( e.g. , temperatures ) , some features of the bonds and atoms in a molecule may slightly change ( e.g. , orientation of atoms ) ; this means that the same pattern may appear slightly different even in the same molecule under different conditions . while current methods may not determine these patters that appear with slight variation in molecules , our approach successfully determines them using clustering .
we have evaluated the performance of our approach using experiments on antituberculosis dataset and various synthetic datasets .
our experiments show that our approach can correctly determine active fragments of molecules that account for the activity of those molecules .
we also show using our approach that classification methods can achieve good performances while determining biological activity or inactivity in relation to the chemical structures of molecules . in this work ,
we use antituberculosis dataset in order to demonstrate and evaluate our approach . as a future work ,
 designing new medical drugs for a specific disease requires extensive analysis of many molecules that have an activity for the disease . 
 the main goal of these extensive analyses is to discover substructures ( fragments ) that 
 account for the activity of these molecules . 
 once they are discovered , these fragments are used to understand 
 the structure of new drugs and design new medicines for the disease . in this paper 
 , we propose an interactive approach for visual molecule mining to discover fragments of molecules that are responsible for the desired activity 
 with respect to a specific disease . 
 our approach visualizes molecular data in a form that can be interpreted 
 by a human expert . using a pipelining structure 
 , it enables experts to contribute to the solution with their expertise 
 at different levels . in order to derive desired fragments 
 , it combines histogram - based filtering and clustering 
 methods in a novel way . 
 this combination enables a flexible determination of frequent fragments that repeat in 
 molecules exactly or with some variations . 
1. Introduction
2. Related Work
3. Interactive Mining of Molecules
4. Evaluation
5. Conclusions