Current Topics in Medicinal Chemistry, 2006, 6, 31-39 31

Decision Tree Methods in Pharmaceutical Research

Paul E. Blower* and Kevin P. Cross

Leadscope, Inc., 1393 Dublin Road, Columbus, OH 43215, USA

Abstract: Decision trees are among the most popular of the new statistical learning methods being used in the
pharmaceutical industry for predicting quantitative structure-activity relationships. This article reviews applications of
decision trees in drug discovery research and extensions to the basic algorithm using hybrid or ensemble methods that
improve prediction accuracy.

INTRODUCTION et al. [9]; and Rusinko, et al. [10]) applied recursive partit-
ioning (RP) for the analysis of structure-activity relation-
The routine use of combinatorial chemistry and high- ships in large, structurally diverse datasets. The authors
throughput screening in modern drug discovery has resulted
developed a version of RP called SCAM (Statistical
in massive amounts of testing data. In order to make better Classification of Activities of Molecules), using a variety of
use of compound testing data, there has been considerable binary 2D and 3D descriptors (predictor variables), each of
recent interest in adapting new machine learning techniques
which represents the presence or absence of a molecular
to classification and prediction of biological activity from
feature.
chemical structure. Among the many statistical learning
techniques that have been applied to drug discovery research, Decision trees have a number of desirable attributes for
the most popular include Classification and Regression Trees building prediction models for pharmaceutical research: (1)
[1] (CART, also known as Recursive Partitioning and DTs can handle very large, structurally diverse compound
Decision Trees), Neural Networks [2], k-Nearest Neighbors sets; (2) DTs can handle large descriptor sets which may be a
[3] (k-NN), and Support Vector Machines [4] (SVM), and mixture of continuous, discrete, and categorical variables; (3)
other kernel methods [5]. This article reviews the use of DTs can ignore irrelevant descriptors; (4) they have been
Decision Trees (DT) in drug discovery research. useful for explaining a complex, nonlinear response; and (5)
DTs provide a readily interpretable decision path for
Decision trees provide a simple yet powerful method for
understanding the prediction of a test compound, and
building models for prediction of structure-activity
incorrect predictions can be easily analyzed. Table 1, which
relationships. If the response variable is continuous, it is a
is adapted from Hastie, et al. [3] compares the strengths and
regression model; if the response variable is a categorical,
weaknesses of tree-based methods with other statistical
such as active/inactive, it is a classification model. The
learning methods. The major weakness of decision trees is
method recursively partitions the dataset into two or more
their relatively low prediction accuracy compare with the
subsets based on the presence or absence of a structural
other learning methods. In order to improve the predictive
feature or the value of a molecular characteristic such as
power of decision trees while retaining the desirable
logP. The key elements of the analysis are rules for (1)
attributes, a number of extensions have been introduced.
splitting each node in the tree into subsets, (2) stopping rules
which determine when a node cannot be split further, and (3) In the sections that follow, we first describe and illustrate
rules for pruning or simplifying the initial tree. the basic algorithm for recursive partitioning along with
several applications to pharmaceutical research. Next we
The first published application of decision trees to describe hybrid techniques which combine recursive
pharmaceutical research was a 1995 paper by Young and
partitioning with other optimization or machine learning
Hawkins [6] which analyzed a full factorial chemical library methods. Then we describe ensemble methods which seek to
using a recursive partitioning algorithm named FIRM
improve predictive power by combining predictions from
(formal inference-based recursive modeling). The authors multiple trees. Finally we describe multiple objective
analyzed the effect of D/L stereoisomers at 9 amino acids in methods which extend classification trees to accommodate
an 11-amino acid polypeptide. Beginning with the full set of
multiple response variables.
29 = 512 D/L stereoisomers, they systematically examined
the effect on potency at each of the 9 amino acids. The RECURSIVE PARTITIONING
position showing the largest difference on mean potency
RP begins with a potentially large heterogeneous set of
between the D-isomer and the L-isomer was selected as the
compounds and attempts to produce smaller and more
first split, and the process was repeated with the two
daughter nodes. Subsequent work by scientists at Glaxo homogeneous sets. This is accomplished recursively by
finding features that successively split a set of compounds
Wellcome Inc. (Hawkins, et al. [7]; Young, et al. [8]; Chen,
into two subsets (+ and – response branches) that are more
similar to each other in terms of their biological activity than
*Address correspondence to this author at the Leadscope, Inc., 1393 Dublin the original set. In the standard application of RP, each
Road, Columbus, OH 43215, USA; Tel: 614-675-3766; Fax: 614-675-3732; feature can be used to divide the set of compounds into two
E-mail: pblower@[Link]
groups, those with the feature (+) and those without (–). At

1568-0266/06 $50.00+.00 © 2006 Bentham Science Publishers Ltd.

32 Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 Blower and Cross

Table 1.

Characteristic Neural Nets SVM Trees k-NN

Natural handling of data of mixed type l l l l

Handling of missing values l l l l

Robustness to outliers in input space l l l l

Insensitive to monotone transformations of inputs l l l l

Computational scalability (large N) l l l l

Ability to deal with irrelevant inputs l l l l

Ability to extract linear combinations of features l l l l

Interpretability l l l l

Predictive power l l l l

Characteristic of different learning methods; key: l = good, l = fair; l = poor

Adapted from Ref. 3.

each step of RP, the feature chosen for the split is the one descriptors for a variable j and the corresponding splitting
that creates the most diverse groups according to a criterion value s that gives the highest t-statistic for regression
such as the difference in mean biological activity of the two problems or best purifies the subgroups for classification
groups; alternatively, the criterion for feature selection may problems. Thus the two subtrees TL and T R are: T L = {X | Xj
be a measure of increased homogeneity within the two ≤ s} and TR = {X | Xj > s}.
subsets that are produced. For continuous response variables,
A common strategy is to overgrow the initial tree which
the criterion typically used for variable selection is the t-
may overfit the training data then prune it back using cost
statistic (or t-test) for comparing groups with and without a
complexity criteria. The pruning phase seeks a subtree that
given feature.
balances tree size and number of misclassifications or the
mean square error on the training set. Other mechanisms for
x 1-x0 controlling tree size include specifying a minimum node
t=
SD 1/n1+ 1/n0 size, a maximum tree depth, or stopping when partition
significance, as determined by p-value, is no longer
where x 1,x0 are the mean activities of the (+)-branch and the maintained.
(-)-branch, respectively, n1 and n0 are the set sizes and SD is An alternative method to avoiding overfitting, is to use
the pooled standard deviation. Splitting stops when the cross-validation to assess the model quality [11]. To avoid
Bonferonni adjusted p-value for the test fails to achieve problems with the bias of hold-out test sets, and to consider
significance at some predetermined level. Note that choosing all the data in building the model, a K-fold cross-validation
the largest t-statistic for comparing two groups is equivalent can be employed which uses K-1 sections of data to train the
to choosing the largest, absolute F-statistic, since F = t2. model, and one section of data to test the model. For a 10-
If the response variable is a classification with fold cross-validation, 10 equal partitions of the data set are
compounds taking on class labels 1, 2,…, k, then the splitting created, and 10 different models are created, each trained
criteria are based on node purity. A popular measure of node with a different 9 partitions of data, and each predicting
purity is the Gini index [1] which maximizes the decrease in values for the single partition held-back from training
impurity (DI) as a tree is split into two subtrees TL and TR respectively. The predictions across all 10 held-back
partitions are used to calculate a cross-validated R 2 value and
a predicted sum of squares both of which can quantify model
∆I = I - pLIL - pRI R quality and be used to prune the tree. The choice of K
2 depends on the data set size. Too few partitions for a small
I = ∑ pipj = ∑ pi - ∑ pi2 = 1 - ∑ pi2 data set substantially degrades the models used to predict the
i≠j i i i
hold-back partition, resulting in an overestimate of
prediction error due to high bias. Too many partitions, such
where pL and pR are the proportions of compounds in as in leave-one-out (n-1) cross validation, results in an
subtrees TL and TR and pi is the proportion of class i underestimate of prediction error due to high variance [3].
compounds in a node. In the case of two classes such as
active/inactive, the Gini index becomes 2p(1 – p). Once a decision tree is constructed from a training set, it
can be applied to any other compound containing the
If the descriptors have continuous values, at each necessary descriptors. The test compound is filtered into one
splitting node, the RP algorithm searches the pool of of the terminal nodes by applying the splitting rules in
Decision Tree Methods in Pharmaceutical Research Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 33

sequence, and a prediction is made based on response values it replaces incremental variable selection with a genetic
of the training set compounds in the node, the average value algorithm that is used to select combinations of descriptor
for regression problems or the majority class for splines as the “best-subset” to partition compounds into
classification problems. active and inactive sets. This prediction method, designed to
support virtual screening, was validated against five series of
Example RP Tree
compounds: cyclooxygenase-2 inhibitors, benzodiazepine
Figure 1 illustrates recursive partitioning of a large, receptor ligands, estrogen receptor ligands, dihydrofolate
heterogeneous dataset, the September 2003 release of the reductase inhibitors (DHFR), and monoamine oxidase
National Cancer Institute’s (NCI) antitumor drug screening inhibitors (MAO). In a separate study [17], Sutherland, et al.
database obtained from the NCI’s Developmental developed a QSAR to predict anticonvulsant activity of
Therapeutics Program website [12]. Since 1990, the DTP hydantion derivatives in mice and rats. Results were
Human Tumor Cell Line Screen has been testing compounds compared against RP and SIMCA [18] (a Principal
for growth inhibition against a panel of 60 human tumor cell Components approach). SFGA produced models that were
lines. The data provide GI50 values for each compound-cell comparable with or slightly better than SIMCA results for all
line pair, the concentration that causes 50% growth datasets. RP models were consistently worse. However, run
inhibition. The example uses the GI50 data for the NCI-H23 times for SFGA were approximately 30 times longer than
non-small cell lung cancer panel. In the September 2003 SIMCA and RP. Also, SIMCA produced more stable models
release there were 39,769 compounds with measured values as the distances of the test set compounds from the training
of pGI 50 for the NCI-H23 cell line, with an average value of set compounds increased due to its use of latent variables
4.49. The set of splitting features used was the standard which are less sensitive to variations in the training set.
LeadScope® Structural Feature Hierarchy [13], comprised of Substantially better classification rates were obtained when a
structural features typically found in small molecule drug unanimous consensus model was built using all three
candidates. The t-statistic was used to select the best splitting models, where only unanimous predictions of activity
feature, and the minimum nodes size was set at 20. Fig. 1 resulted in an active prediction.
shows the first four levels of the RP tree. Van Rhee, et al. [19] studied the use of recursive
Pharmaceutical Applications partitioning to increase efficiency of high-throughput
screening in a combinatorial library of 21,000 compounds.
The remainder of this section reviews applications of RP Compounds were assigned to one of four activity categories,
in pharmaceutical research. Chen, et al. [14] extended and a diverse training set was selected by D-optimal design
SCAM to identify 3D pharmacophores in the program [20]. The authors studied the effect of several factors on the
SCAMPI (Statistical Classification of Activities of model’s success: splitting method, maximum tree depth,
Molecules for Pharmacophore Identification). This combined number of ways a descriptor range is divided, and number of
a fast conformational search with recursive partitioning for cross-validation groups. Hit rates of the primary screen could
identification of three-dimensional pharmacophores from be improved 4- to 5-fold, and 75% of the actives could be
large, heterogeneous datasets. Multiple conformations are recovered by screening less than 20% of the test set.
examined using a random search technique. These are
combined with recursive partitioning to identify the chemical Sequential screening is an iterative procedure comprising
features and configurations that best correlated with cycles of design_synthesis/acquisition_screening that can
biological activity as measured by the t-test. From this greatly increase hit rates over random screening or non-
analysis, more complex pharmacophores are then iterative procedures. Jones-Hertzog, et al. [21] incorporated
constructed from simpler ones; e.g., 3-point pharmacophores recursive partitioning into a sequential screening protocol to
from 2-point pharmacophores. predict activity in G-protein-coupled receptor binding
assays. In general, the sequential screening procedure is as
Cho, et al. [15] extended the FIRM algorithm by follows:
employing a method to extract multiple features at each
splitting node. Recursive partitioning models were built 1. Select and experimentally screen a small X% sample
using binary atom pair descriptors. An F-test, the ratio of (e.g., X = 1) to use as an initial training set.
variances between the (+) descriptor and (–) descriptor 2. Build a predictive model from training set; in this case,
branches, is the statistical measure for selecting descriptors. recursive partitioning was used for model building.
Multiple descriptors were selected from among those with
the highest individual F-test values. The resulting trees were 3. Apply the model to all untested compounds.
typically linear; that is, splitting usually gave + branches that 4. Experimentally screen the highest ranking X% of
were terminal nodes. The authors point out that more useful compounds and augment the training set.
structural information is obtained when multiple descriptors
are used for splitting since compounds in the + branch have a 5. Repeat steps 2 – 4 until Y% of compounds (e.g., Y = 5)
have been screened.
larger common substructure than with single descriptor
splits. The method was tested using 27,000 compounds from In the Jones-Hertzog [21] study, data from 14 GPCR
the National Cancer Institute with experimental GI50 values assays were used, and a diverse set of 23,000 compounds
for the NCI-H23 cell line. was used as an initial training set for the RP model. RP trees
were generated for each assay, and terminal nodes with high
Sutherland, et al. [16] developed a new method of
recursively partitioning data sets based on spline-fitting with average activity were identified. These were used to select
compounds from a 160,000 compound collection. In seven
a genetic algorithm (SFGA). The method is similar to RP but
34 Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 Blower and Cross

Figure 1, node table

Node Splitting Feature Frequency Mean

1 Root 39769 4.49

2.1 [+]1,4-benzoquinone 977 5.34

2.2 [-]1,4-benzoquinone 38792 4.47

3.1 [+]pyran(H), 4-amino- 65 7.26

3.2 [-]pyran(H), 4-amino- 912 5.21

3.3 [+]oxycarbonyl, O-(alkyl, cyc)- 2673 4.95

3.4 [-]oxycarbonyl, O-(alkyl, cyc)- 36119 4.44

4.1 [+]pyran(H), 4-alkylamino- 42 7.59

4.2 [-]pyran(H), 4-alkylamino- 23 6.65

4.3 [+]hacceptor-path3-pcharge 249 5.62

4.4 [-]hacceptor-path3-pcharge 663 5.05

4.5 [+]hacceptor-path7-hdonor 1299 5.41

4.6 [-]hacceptor-path7-hdonor 1374 4.51

4.7 [+]tropone 141 6.28

4.8 [-]tropone 35978 4.43

Fig. (1). Figure 1 illustrates recursive partitioning of the NCI antitumor drug screening database. The standard LeadScope® Structural
Feature set was used to partition the dataset, and the tree was constructed to optimize mean pGI50 values for the NCI-H23 lung cancer cell
line. Compounds containing the selected splitting feature form the left branch; the remaining compounds form the right branch. The t-statistic
was used to select the best splitting feature, and the minimum nodes size was 20. The accompanying table gives node details: For example,
the root node corresponds to the full dataset of 39,769 compounds with average pGI50 value of 4.49. The best splitting feature for the root
node was 1,4-benzoquinone. The 977 compounds containing this structural feature formed node 2.1 with an average pGI50 value of 5.34. The
remaining 38,792 compounds not containing this feature were partitioned to node 2.2 with an average pGI50 value of 4.47.
Decision Tree Methods in Pharmaceutical Research Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 35

of 14 assays, second round hit rates were substantially better HYBRID METHODS
than random screening. The authors noted that this protocol
provides an opportunity to learn from experimental data and The basic recursive partitioning procedure uses a greedy
use the newly acquired knowledge to focus future algorithm that selects the best descriptor at any splitting
experiments. node. In general, this will not produce the optimal decision
tree. However, it is not possible to examine all combinations
In a study by Rusinko, et al., [22] recursive partitioning of descriptors even for small descriptor sets. In this section,
models are incorporated into a sequential screening protocol we describe hybrid techniques which combine recursive
to optimize the design of focused libraries. Two focused partitioning with optimization procedures such as simulated
libraries of approximately 2,500 trisubstituted guanidines annealing or other machine learning methods.
were synthesized and tested. After each iteration of
Izrailev and Argrafiotis [25] introduced a stochastic
sequential screening, a genetic algorithm was used to select
partitioning algorithm for growing regression trees based on
monomer subsets trisubstituted guanidines in Library 2.
artificial ant colony systems (ANTP). During ants search for
Activity predicted by the current RP model was used as the
food, ants leave pheromones along their paths marking their
fitness function for the genetic algorithm. Even though no
compounds in Library 1 were active (greater than 50% trail. While all paths to a food source are initially probable,
inhibition), the weak SAR signal was amplified over four the shorter paths have more ants making round trips and their
iterations from a maximum of 49.3% in the initial library to pheromone deposits increase, reinforcing shorter subpaths,
and ultimately the shortest path. Each ant path represents a
89.4%. Only 160 compounds were virtually “synthesized
and tested” from Library 2. This paper illustrates that even separate RP tree that uses the repetition of common
descriptor and split values (in “good” paths) to increase the
weak, noisy HTS data can be amplified by sequential
probability of using that split in future RP trees. A number of
screening and mined to design experimental libraries and
trees are grown consecutively and the most predictive tree
reduce the number of compounds that need to be synthesized
(based on R2) is recorded. The process is repeated several
and tested.
times to avoid convergence to a poor local minimum. ANTP
Bai, et al. [23] described the first application of CART to was compared against RP and completely random searches
predict the fraction of drug dose absorbed in humans. A for three data sets: antimalarial activity of antimycin
structurally diverse set of 1260 compounds compiled from analogues, binding affinities of ligands to benzodiazepine/
the literature which was split approximately 3:1 between GABA receptors, and inhibition of dihydrofolate reductase
training and test sets. The authors only used data where by pyrimidines. ANTP created better predictive models than
dissolution was not a rate-limiting factor, and separate RP or random searches for each of the three data sets. When
branches of the decision tree were created for active and the number random searching models increased from 10 to
passive transport. The fraction dose absorbed was divided 1000, the best random models improved significantly. They
into six classes. The classification tree was built from 28 were better than RP models and comparable to the best
structural descriptors important for drug transport including ANTP models, but had a much larger scatter in the accuracy
calculated logP, number of hydrogen bond donors and of their solutions. The performance of ANTP is limited by
acceptors, and polar surface area. A graph-based algorithm the number of nodes in the tree. This limits the applicability
was developed to estimate intramolecular hydrogen bonding. of ANTP to smaller models, but not necessarily small data
Contributions from specific functional groups such as sets.
quaternary amines were also included. For the test set, 65%
Miller [26] described a hybrid statistical learning method
of the compounds were correctly classified, and 80% were
that combines k-nearest neighbors (k-NN) and recursive
within one class error. In a comparison of 39 compounds, the
partitioning. The method is a modification of flexible metric
CART predictions were superior to those from artificial
nearest neighbor classification (FMNN) developed by
membrane studies.
Friedman [27]. It seeks to take advantage of complementary
Feng, et al. [24] compared recursive partitioning with attributes of k-NN and RP. An advantage of k-NN is that it
other statistical learning methods for the predicting toxic builds a local model for each test set compound which tends
effects from the chemical structure. The objective of this to be near the center of the local neighborhood. However, k-
study was to determine which combinations of statistical NN uses a global similarity to determine the neighbors that
methods and molecular descriptors are most effective. Three comprise the local neighborhood. For example, if the
statistical methods were studied: RP, PLS and neural neighborhood is based on structural similarity, then all
networks; and four types of descriptors: constitutional, structural features are considered equally important in
topological indices, BCUTs and fragment/property identifying the neighborhood around the test compound. RP
descriptors. The method-descriptor combinations were tested constructs a global model from the training set and
on four public datasets ranging in size from 270 to 29,000. iteratively partitions the training set into a series of disjoint
Two of the datasets provided continuous responses, the other classes. Then each test compound is assigned to the class
two binary. Because of the large number of 3-factor based on the decision tree rules used to create the
combinations, a block design of 18 dataset-method- partitioning. In a sense, the RP model is local in that it only
descriptor combinations were studied. Conclusions were uses a small subset of descriptors that best discriminate for
tentative, and none of the three statistical methods was activity. The hybrid FMNN method constructs a local
clearly superior. neighbor for each test sample but uses only the most
significant features to measure distance between a test
compound and its nearest neighbors.
36 Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 Blower and Cross

For the purpose comparing performance with k-NN and from the literature and other public sources. Prediction
RP, a public dataset of compounds tested for anti-HIV accuracies on the external test set averaged 76%, an
activity was obtained from the National Cancer Institute. improvement of 5-10% compared with standard RP and
MDL MACCS keys were used as descriptors, and principle comparable to multiple RP tree ensembles; see paper by
component analysis was used to reduce the descriptor set to Cheng and Dixon below.
18 dimensions. The modified FMNN method outperformed Godden, et al. [31] described a variation of RP called
both k-NN and RP in terms of enrichment. However k-NN recursive median partitioning (RMP). Given a continuous
(but not RP) gave better coverage; that is, the ratio of true molecular descriptor, median partitioning separates
positives to the total number of active compounds. compounds into two subsets; those with descriptor values
Blower, et al. [28] used simulated annealing (SA) to find above and below the median. In a virtual screening
combinations of molecular descriptors and incorporated the application, a database is first seeded with known actives
search into a recursive partitioning design to produce a called bait compounds. The seeded database is split by
regression tree for biological activity. SA is used at each median partitioning. Then database compounds in partitions
split to find combinations of molecular descriptors whose containing fewer than two bait compounds are discarded
simultaneous presence best separates the most active, resulting in a smaller dataset with database compounds more
chemically similar group of compounds from the current set. similar to the active seeds. All bait compounds are added to
The search is incorporated into a recursive partitioning the smaller dataset, and the process is repeated until
design and thus is called Recursive Partitioning with sufficiently small partitions are obtained. In examples using
Simulated Annealing (RP/SA). It produces a regression tree 10 bait compounds, this was achieved after five iterations.
for biological activity in the space of structural features. Unlike RP where a set is recursively split into smaller
Each node is characterized by a specific combination of subsets that cover the full dataset, RMP produces a more
structural features. However, some features in the focused subset with each iteration.
combination may be negative features. For example, in the
Miller [32] compared global versus local recursive
feature combination {A, B, -C}, features A and B must be
partitioning models. Local models were built using a class-
present, and feature C must be absent. The key distinction
based approach, in which the training set is first partitioned
between RP/SA and standard RP is that RP optimize features
into structurally homogeneous classes, and independent
individually using a greedy algorithm to select the best
models are constructed within each class. Structural classes
single feature at each step, whereas RP/SA searches for were based on scaffolds comprised of one or more ring
optimal combinations of features at each step. Because systems each joined by an unbranched, acyclic chain.
RP/SA is a stochastic process that produces a different
Because a compound may contain several class scaffolds, it
solution (tree) with each run, for use in ranking, n trees are
may be a member of zero or more local neighborhoods and
generated from the training set. For each test compound, the
contribute to multiple models. Test compounds not belong-
predicted value is the average of training set compounds in
ing to a structural neighborhood are not predicted. Local
the tree node, and then these average values were averaged
neighborhoods were also restricted by frequency, and models
over the n trees. Cross, et al. [29] used RP/SA to identify
were not built for neighborhoods containing fewer than 16
major active structural classes in the NCI-H23 dataset and compounds. The study compared several descriptors sets
their respective discriminating feature sets, as well as feature comprised of structural fragments or simple molecular
sets discriminating for the major therapeutic categories in the
properties. Models were tested on a 6,500 compound subset
LeadScope Known Drugs database.
of the NCI AIDS data with categorical active/inactive
DeLisle, et al. [30] described a novel method for building designations for protection against HIV-1 infection. Models
decision trees using evolutionary programming techniques; built from local neighborhoods have advantages of greater
the trees are called EPTrees. The target dataset was interpretability and greater reliability.
partitioned 8:1:1 as training set: cross-validation set: external
ENSEMBLE APPROACHES
test set. The process begins with an initial population of
decision trees constructed at random from the training set. As noted above decision trees have many desirable
The only restriction is that terminal nodes must contain at attributes for building prediction models. Unfortunately the
least a predetermined minimum number of compounds, and models often have relatively low prediction accuracy
this is also the stopping rule. To build the initial population, compared to neural networks or support vector machines.
at any non-terminal node a random descriptor and cutoff The low prediction accuracy is due to the fact that decision
value is used to split the node into two children. During the trees are unstable predictors; i.e., small changes in training
evolutionary phase, two trees from the current generation are data can lead to large changes in model structure and output.
selected with replacement using a fitness function and the One method for improving performance while retaining
pair is acted upon either by crossover or mutation giving two desirable features is to use ensemble trees. In this section we
new trees for the next generation. This is repeated until the consider techniques for combining the results of multiple
size of the next generation is the same size as the current classification models to produce a single model.
generation, and at that point, it replaces the current
generation. The evolutionary process is in turn repeated for a Dixon, et al. [33] compared recursive partitioning with
predetermined number of generations. To avoid overtraining, other classification methods for the predicting pharm-
acological activity of compounds in diverse chemical
the prediction accuracy of the best trees is compared between
libraries. The study compared three classification methods:
training and cross-validation sets. The EPtree method was
tested on a hepatotoxicity dataset 436 compounds derived RP, linear discriminant analysis, and hierarchical agglomera-
Decision Tree Methods in Pharmaceutical Research Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 37

tive clustering and two descriptor sets: Molconn-X predetermined size. There is no interaction between trees: the
topological descriptors and MDL structural keys. Because selection of training and descriptor sets for one tree have no
pharmaceutical databases tend to be skewed toward inactive influence on other trees. In contrast with the DF approach,
compounds and classification models built from unbalanced all trees are built using the original training set. However, the
training sets show low sensitivity for active compounds, the descriptor set use to build the tree at iteration i is removed
authors built a series (ensemble) of balanced training sets from the descriptor pool before the next iteration. Thus, each
containing equal numbers of active and inactive compounds. tree is built from a unique set of descriptors. Decision
The ensemble prediction for a test compound is the average Forests are based on two key ideas: (a) To ensure that each
over individual balanced models. The authors found that individual model makes a unique contribution to the final
replacing a single training set that is highly skewed towards prediction, individual trees should be as different as possible,
inactive compounds with an ensemble of smaller, balanced and (b) all trees should meet minimum quality criteria. When
training sets improves model sensitivity toward active the initial tree is constructed the algorithm determines the
compounds. minimum number of misclassified compounds, and this
serves as a quality criteria for subsequent trees. Subsequent
Svetnik, et al. [34] investigated the use of a Random
Forest (RF), an ensemble of unpruned classification or trees are pruned using a cost-complexity algorithm and the
regression trees, for predicting a compound’s biological misclassification rate calculated from the initial tree.
activity based on a description of molecular structure. An RF Each tree in the ensemble assigns a probability of activity
is an ensemble of B trees which is a p-dimensional vector of to a test compound based on the proportion of training set
molecular descriptors or properties associated with a actives in the corresponding node, and the ensemble
molecule. The prediction from the RF is the aggregate prediction is the average probability over all trees. The DF
prediction from the individual B trees. This aggregate procedure was tested on a set of 232 with data from a
prediction is the class predicted by the majority of trees for competitive estrogen receptor binding assay. Compared with
classification problems and the average of the individual tree a standard decision tree, the DF improved the
predictions for regression problems. concordance—that is the number of compounds correctly
classified divided by total compounds—from 92.6% to
Training an RF is comprised of the following steps:
97.8%.
1. From the training data of n molecules, draw a bootstrap
Sussman, et al. [37] built ensemble RP models using
[35] sample. This is a random sample of size n with
bagging [38] for predicting developmental toxicity of
replacement of the compound after each selection is
compounds and compared results with single model RP.
made.
Bagging uses a bootstrap approach for selecting individual
2. For each bootstrap sample, grow a decision tree using a training sets. Each resampled training set consists of n
randomly selected subset of mtry descriptors. Using only compounds (where n is the size of the original training set)
the mtry descriptors, the tree is grown to the maximum selected at random with replacement from the original
size and not pruned. In tuning experiments with several training set. Thus each training set compound may appear
literature datasets, the authors found optimal values of zero or more times in any of the replicate training sets.
mtry to be p1/2 for classification and p/3 for regression.
The standard and ensemble RP procedures were tested on
3. Repeat the above steps until a predetermined number B a set of 293 compounds assayed for teratogenicity of which
of such trees are grown. For comparison with other 40% were active. Models were built using 19 physico-
learning methods in this study, B = 500 was used. chemical descriptors calculated from three-dimensional
RFs also provide a performance assessment method structures. Two-thirds of the compounds were selected for
called out-of-bag estimation which uses the compounds the training sets; both random and balanced training sets
excluded from the bootstrap sample to measure the mean were compared. For the random training set, the ensemble
square error for regression problems or the misclassification procedure showed improvements in accuracy, 65% versus
rate for classification problems. Typically, approximately 60%, compared with standard RP and specificity, 75% vs
37% of the compounds are omitted from the bootstrap 61%, but there was a decrease in sensitivity, 50% vs 54%.
training sets. This built-in assessment method avoids having Comparing results from random vs balanced training sets,
to set aside a portion of the training set for model validation. there was no difference in accuracy, but sensitivity improved
In comparison with other prediction methods such as PLS, from 50% to 65% while specificity declined from 75% to
SVM and neural networks over several literature datasets, 62%.
the authors found RF to be among the best prediction Susnow, et al. [39] used an ensemble recursive partit-
algorithms using default parameters with no need for ioning procedure for classifying potential cytochrome P450
descriptor selection. 2D6 inhibitors as inhibitor or non- inhibitor. For each tree of
Tong, et al. [36] described an approach, named Decision the ensemble the procedure selects a balanced, random
Forest (DF), that combines multiple Decision Tree models. sample of actives and inactives as the training set. In the
The Decision Forest differs from RFs in several important study reported, 101 trees were built on training sets of 70
ways. RF uses a bootstrap resampling technique to select compounds. The ensemble prediction for a test compound is
replicate training sets. Each is the same size as the original the average over individual trees giving a predicted value in
training set, but some compounds may appear multiple times the range -1.0 – 1.0. The absolute value of the prediction can
while others are omitted. For each replicate training set, a serve as a confidence estimate with lower confidence near
decision tree is built using a random subset of descriptors of zero and higher confidence near either endpoint.
38 Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 Blower and Cross

This ensemble RP procedure is similar to bagging, except Interpretation of the PUMP-RP tree indicates which
that bagging uses bootstrap resampling for selecting descriptors and split values are important for all properties
individual training sets. With bagging, each replicate training and which is specific to a given property. Generic nodes,
set is the same size of the original training set, but which were constructed using several specific trees in their
compounds are selected at random with replacement from creation, have more data supporting the training of the model
the original training set. that single-property RP nodes and should have better
Because RP models often have low predictivity when predictability as well as compensate for missing data for
built from large descriptor sets, a large number of molecular some properties. This technique also demonstrated how a
descriptors was initially generated and then pared down to a common dependence of several different properties on
correlated descriptors can be used to uncover descriptor
25-descriptor set using a simulated annealing procedure.
correlations (and equivalences) that would otherwise be
Literature K i values for 100 structurally diverse compounds
difficult to elucidate due to the greedy nature of RP.
were converted to a binary classification inhibitor/non-
inhibitor of P450 2D6. Compared with standard RP, the Roa, et al. [43] applied PUMP-RP to analyze a database
ensemble RP approach improved accuracy from 62% to of cyclooxygenase (COX-1 and COX-2) inhibitors using
75%. three different sets of physiochemical descriptors. From an
initial set of 454 COX inhibitors, training sets of 86 and 246
Cheng and Dixon [40] used an ensemble of RP tress to
COX-1 and COX-2 inhibitors were created, respectively, and
predict hepatotoxicity in a dataset of 382 diverse, drug-like
compounds. The modeling technique was essentially the test sets of 12 and 27 inhibitors, respectively. Several
same as Susnow [39] where an ensemble of RP tress is PUMP-RP trees were created, under various parameter
developed from random, balanced subsets of the training set. settings, to predict (in each tree) COX-1 activity, COX-2
Again the ensemble predictions were compared with activity, and COX-2 selectivity. Test set predictions for
COX-1 inhibitors contained 60-100% of the true actives
standard RP and found to be considerably improved:
(with a maximum concordance of 46%) while predictions for
accuracy 85% vs 66%, sensitivity 78% vs 56%, and
COX-2 inhibitors contained 50-89% true actives (with a
specificity 90% vs 73%
maximum concordance of 72%). PUMP-RP trees were
Van Rhee [41] introduced Consensus Selection by moderately predictive of COX-2 selectivity, with up to 59%
Multiple Recursion Trees. Instead of forming an aggregate of the true selective structures retrieved (and a maximum
class prediction is the majority vote, Consensus Selection concordance of 68%). The overall success rates in predicting
constructs the Boolean intersection of multiple trees. In COX-1 and COX-2 activities for PUMP-RP is similar to that
examples shown, consensus models were constructed from 2 observed for single-property RP trees. However, PUMP-RP
– 3 trees, and trees contributing to the consensus models identified a set of descriptors common to both COX-1 and
were typically closely matched. The new method improved COX-2 activities that single-property RP did not identify as
prediction accuracy over single RP in a sequential screening well as descriptors that only discriminate between the two
process [19] at the expense of interpretability. activities.
MULTIPLE OBJECTIVE METHODS SUMMARY
This section describes methods which extend To make better use of large quantities of compound
classification trees to accommodate multiple dependent testing data being generated in the pharmaceutical industry,
properties. Stockfisch [42] described Partially Unified scientists have adopted new machine learning methods for
Multiple Property Recursive Partitioning (PUMP-RP) which predicting quantitative structure-activity relationships.
allows prediction of a separate activity class for several Decision trees have a number of desirable attributes, making
properties within a single tree model. RP trees are first them among the most popular of the new statistical learning
created for each individual property and attached to the root methods. They can handle large, diverse sets both in terms of
node as subtrees of “specific” nodes. All properties are compounds and descriptors. DTs have been useful for
combined in a single-Y column and then used to regrow the explaining complex, nonlinear responses, and they provide
tree from the root where the splitting rule is modified with a predictions for test compounds that are readily interpretable.
growth phase metric that considers each of the properties. The major weakness of decision trees is their relatively low
The worst score over all of the properties is selected as the prediction accuracy, but this has been largely addressed
score for this “generic” node. Splitting must be favorable for through extensions using hybrid or ensemble methods.
each and every property for a generic node to be kept. Each
branch from the generic node is again regrown using the REFERENCES
single-property procedure and pruned. This process of [1] Breiman, L.; Friedman, J. H.; Olshen, R. A.; Stone, C. J.
addition of generic nodes from the root downward and Classification and Regression Trees; Wadsworth, 1984.
regrowth of specific property paths from generic nodes is [2] Zupan, J.; Gasteiger, J. Neural Networks for Chemists; Wiley-VCH:
Weinheim, 1999.
repeated until no more generic nodes can be split (without [3] Hastie, T.; Tibshirani, R.; Friedman, J. The Elements of Statistical
the growth phase metric getting worse for one of the Learning; Springer-Verlag: New York, 2001.
properties or when no splits can survive pruning). The [4] Zernov, V. V.; Balakin, K. V.; Ivaschenko, A. A.; Savchuk, N. P.;
resulting tree contains generic nodes at the upper-levels of Pletnev, I. V. Drug discovery using support vector machines. The
case studies of drug-likeness, agrochemical-likeness, and enzyme
the tree where splits are made which are favorable to all inhibition predictions. J. Chem. Inf. Comput. Sci. 2003, 43 , 2048-
properties, and specific property nodes at the lower-levels 2056.
where splitting results favor one property over another.
Decision Tree Methods in Pharmaceutical Research Current Topics in Medicinal Chemistry, 2006, Vol. 6, No. 1 39

[5] Harper, G.; Bradshaw, J.; Gittins, J. C.; Green, D. V.; Leach, A. R. classification regression tree in predicting oral absorption in
Prediction of biological activity for high-throughput screening humans. J. Chem. Inf. Comput. Sci. 2004, 44, 2061-2069.
using binary kernel discrimination. J. Chem. Inf. Comput. Sci. 2001, [24] Feng, J.; Lurati, L.; Ouyang, H.; Robinson, T.; Wang, Y.; Yuan, S.;
41, 1295-1300. Young, S. S. Predictive Toxicology: Benchmarking Molecular
[6] Young, S. S.; Hawkins, D. M. Analysis of a 2(9) full factorial Descriptors and Statistical Methods. J. Chem. Inf. Comput. Sci.
chemical library. J. Med. Chem. 1995, 38, 2784-2788. 2003, 43, 1463-1470.
[7] Hawkins, D. M.; Young, S. S.; Rusinko, A., 3rd Analysis of a large [25] Izrailev, S.; Agrafiotis, D. A novel method for building regression
structure-activity data set using recursive partitioning. Quant. tree models for QSAR based on artificial ant colony systems. J.
Struct-Act Relat. 1997, 16, 1-7. Chem. Inf. Comput. Sci. 2001, 41, 176-180.
[8] Young, S. S.; Hawkins, D. M. Using recursive partitioning to [26] Miller, D. W. Results of a new classification algorithm combining
analyze a large SAR data set. SAR QSAR Env. Res. 1998, 8 , 183- K nearest neighbors and recursive partitioning. J. Chem. Inf.
193. Comput. Sci. 2001, 41, 168-175.
[9] Chen, X.; Rusinko, A., 3rd; Young, S. S. Recursive Partitioning [27] Friedman, J. H. Flexible Metric Nearest Neighbor Classification;
Analysis of a Large Structure-Activity Data Set Using Three- Department of Statistics, Stanford University: Stanford, CA, 1994.
Dimensional Descriptors. J. Chem. Inf. Comput. Sci. 1998, 38, [28] Blower, P.; Fligner, M.; Verducci, J.; Bjoraker, J. On combining
1054-1062. recursive partitioning and simulated annealing to detect groups of
[10] Rusinko, A., 3rd; Farmen, M. W.; Lambert, C. G.; Brown, P. L.; biologically active compounds. J. Chem. Inf. Comput. Sci. 2002, 42,
Young, S. S. Analysis of a large structure/biological activity data 393-404.
set using recursive partitioning. J. Chem. Inf. Comput. Sci. 1999, [29] Cross, K. P.; Blower, P. E.; Myatt, G. J. Identifying Discriminating
39, 1017-1026. Structural Features for Compound Classes. In 223rd ACS National
[11] Hawkins, D. M.; Basak, S. C.; Mills, D. Assessing model fit by Meeting: Orlando, FL, 2002.
cross-validation. J. Chem. Inf. Comput. Sci. 2003, 43, 579-586. [30] DeLisle, R. K.; Dixon, S. L. Induction of decision trees via
[12] Nonconfidential screening results and chemical structural data from evolutionary programming. J. Chem. Inf. Comput. Sci. 2004, 44,
the NCI's Developmental Therapeutics Program are available 862-870.
online: Human Tumor Cell Line Screen: [Link] [31] Godden, J. W.; Furr, J. R.; Bajorath, J. Recursive median
cancer/cancer_data.html partitioning for virtual screening of large databases. J. Chem. Inf.
[13] Roberts, G.; Myatt, G. J.; Johnson, W. P.; Cross, K. P.; Blower, P. Comput. Sci. 2003, 43, 182-188.
E., Jr. LeadScope: software for exploring large sets of screening [32] Miller, D. W. A chemical class-based approach to predictive model
data. J. Chem. Inf. Comput. Sci. 2000, 40, 1302-1314. generation. J. Chem. Inf. Comput. Sci. 2003, 43, 568-578.
[14] Chen, X.; Rusinko, A., 3rd; Tropsha, A.; Young, S. S. Automated [33] Dixon, S. L.; Villar, H. O. Investigation of classification methods
pharmacophore identification for large chemical data sets. J. Chem. for the prediction of activity in diverse chemical libraries. J.
Inf. Comput. Sci. 1999, 39, 887-896. Comput. Aided Mol. Des. 1999, 13, 533-545.
[15] Cho, S. J.; Shen, C. F.; Hermsmeier, M. A. Binary formal [34] Svetnik, V.; Liaw, A.; Tong, C.; Culberson, J. C.; Sheridan, R. P.;
inference-based recursive modeling using multiple atom and Feuston, B. P. Random forest: a classification and regression tool
physicochemical property class pair and torsion descriptors as for compound classification and QSAR modeling. J. Chem. Inf.
decision criteria. J. Chem. Inf. Comput. Sci. 2000, 40, 668-680. Comput. Sci. 2003, 43, 1947-1958.
[16] Sutherland, J. J.; O'Brien, L. A.; Weaver, D. F. Spline-fitting with a [35] Efron, B.; Tibshirani, R. An Introduction to the Bootstrap;
genetic algorithm: a method for developing classification structure- Chapman and Hall: New York, 1993.
activity relationships. J. Chem. Inf. Comput. Sci. 2003, 43, 1906- [36] Tong, W.; Hong, H.; Fang, H.; Xie, Q.; Perkins, R. Decision forest:
1915. combining the predictions of multiple independent decision tree
[17] Sutherland, J. J.; Weaver, D. F. Development of quantitative models. J. Chem. Inf. Comput. Sci. 2003, 43, 525-531.
structure-activity relationships and classification models for [37] Sussman, N. B.; Arena, V. C.; Yu, S.; Mazumdar, S.; Thampatty, B.
anticonvulsant activity of hydantoin analogues. J. Chem. Inf. P. Decision tree SAR models for developmental toxicity based on
Comput. Sci. 2003, 43, 1028-1036. an FDA/TERIS database. SAR QSAR Environ Res. 2003, 14, 83-96.
[18] Dunn III, W. J.; Wold, S. SIMCA Pattern Recognition and [38] Breiman, L. Bagging Predictors. Machine Learning 1996, 24, 123-
Classification. Chemometric Methods in Molecular Design; VCH: 140.
New York, 1995; pp 179-193. [39] Susnow, R. G.; Dixon, S. L. Use of robust classification techniques
[19] van Rhee, A. M.; Stocker, J.; Printzenhoff, D.; Creech, C.; for the prediction of human cytochrome P450 2D6 inhibition. J.
Wagoner, P. K.; Spear, K. L. Retrospective analysis of an Chem. Inf. Comput. Sci. 2003, 43, 1308-1315.
experimental high-throughput screening data set by recursive [40] Cheng, A.; Dixon, S. L. In silico models for the prediction of dose-
partitioning. J. Comb. Chem. 2001, 3, 267-277. dependent human hepatotoxicity. J. Comput. Aided Mol. Des. 2003,
[20] Higgs, R. E.; Bemis, K. G.; Watson, I. A.; Wikel, J. H. 17, 811-823.
Experimental Designs for Selecting Molecules from Large [41] van Rhee, A. M. Use of recursion forests in the sequential screening
Chemical Databases. J. Chem. Inf. Comput. Sci. 1997, 37, 861-870. process: consensus selection by multiple recursion trees. J. Chem.
[21] Jones-Hertzog, D. K.; Mukhopadhyay, P.; Keefer, C. E.; Young, S. Inf. Comput. Sci. 2003, 43, 941-948.
S. Use of recursive partitioning in the sequential screening of G- [42] Stockfisch, T. P. Partially Unified Multiple Property Recursive
protein-coupled receptors. J. Pharmacol. Toxicol. Methods 1999, Partitioning (PUMP-RP): A New Method for Predicting and
42, 207-215. Understanding Drug Selectivity. J. Chem. Inf. Comput. Sci. 2003,
[22] Rusinko, A., 3rd; Young, S. S.; Drewry, D. H.; Gerritz, S. W. 43, 1608-1613.
Optimization of focused chemical libraries using recursive [43] Rao, S. N.; Stockfisch, T. P. Partially Unified Multiple Property
partitioning. Comb. Chem. High Throughput Screen 2002, 5, 125- Recursive Partitioning (PUMP-RP) Analyses of Cyclooxygenase
133. (COX) Inhibitors. J. Chem. Inf. Comput. Sci. 2003, 43, 1614-1622.
[23] Bai, J. P.; Utis, A.; Crippen, G.; He, H. D.; Fischer, V.; Tullman,
R.; Yin, H. Q.; Hsu, C. P.; Jiang, L.; Hwang, K. K. Use of