\section{Experimental Results}
\label{sec:exp}

The section reports preliminary experimental results; more 
detailed results and analysis will be included in the final 
version of the paper. All reported timings are on an SGI Indigo2
with a 175 MHz MIPS R8000 processor and 384MB RAM. Code was written in
C/C++, and compiled using SGI CC. 

\paragraph{Input:} 
In Figure~\ref{fig:mols}, we show four different inhibitors of the
protease thermolysin. These molecules fit into the same cavity of
thermolysin and by their presence inhibit the activity associated
with that cavity. This example was chosen because all the 
inhibitors have been crystallized with thermolysin and their 
active conformations are known and recorded in the PDB database. 
Note that 1TLP has 69 atoms and 10 torsional
degrees of freedom, 4TMN has 68 atoms and 15 degrees of freedom, 5TMN
has 64 atoms and 13 degrees of freedom, and 6TMN has 63 atoms and 12
degrees of freedom.

\begin{figure}
\centerline{
\psfig{figure=4mols.ps,height=4cm}
}
\vspace{-0.3cm}
\caption{1TLP, 4TMN, 5TMN, and 6TMN are inhibitors of thermolysin.}
\label{fig:mols}
\end{figure}

\paragraph{Conformational Search:}
Each of the molecules in Figure~\ref{fig:mols} was run through
our conformational search software. A THRESHOLD value of 20 Kcals/mol was used
for the energy of the valid conformations. It took 4.3 hours to 
to produce 4000 valid conformations for each molecule and reduce
these to a set of representatives.
The timings reported are very reasonable if one takes into 
account that 10, 15, 13, and 12 dimensional spaces are searched.
The number of representatives produced was 850, 1192, 1024, and 955 for 
1TLP, 4TMN, 5TMN, and 6TMN, respectively.
The TOLERANCE value was set to 1.23 $\AA$ for all runs. 
A few clusters of 1TLP are shown in Figure~\ref{fig:clusters}. 
Since we know the active conformations of all the molecules, we 
performed a consistency check at the end of conformational search and 
we confirmed that the active conformations were 
close to at least one of the produced representatives.

An important issue in conformational search is to decide the number
of valid conformations to produce. At this stage, this number is 
determined experimentally. We plan to modify REDUCE so that clustering
is performed incrementally. The conformational search procedure will
stop producing new conformations when these start falling into existing
clusters and do not increase significantly the overall number of clusters. 

\begin{figure}
\centerline{
\setlength{\unitlength}{1mm}
\begin{picture}(100,38)
\put(-30,0){\psfig{figure=c1.ps,height=3.8cm}}
\put(19,0){\psfig{figure=c2.ps,height=3.8cm}}
\put(55,0){\psfig{figure=c4.ps,height=3.8cm}}
\put(85,0){\psfig{figure=c5.ps,height=3.8cm}}
%\put(100,5){\psfig{figure=c5.ps,bbllx=11mm,bblly=240mm,bburx=50mm,bbury=270mm}}
\end{picture}
}
\vspace{-0.3cm}
\caption{Different clusters of 1TLP.}
\label{fig:clusters}
\end{figure}

\begin{figure}
\centerline{
\psfig{figure=active.ps,height=4cm}
}
\vspace{-0.3cm}
\caption{1TLP, 4TMN, 5TMN, and 6TMN overlapped in their active
conformations.}
\label{fig:plot}
\end{figure}

\paragraph{Identification of Invariants:}


To find the invariants in these four molecules, the conformations produced by 
the first stage were given as input to the search algorithm described in 
Section~\ref{sec:inv}. For these tests, we considered each non-hydrogen
atom to be a separate feature. Thus, each conformation had approximately
$30$ features drawn from $6$ feature classes. We define the ``solution''
to be the overlapping portions of the molecules when aligned as shown in
Figure~\ref{fig:plot}. This is the upper right hand
T-shaped portion of this diagram.  The entire invariant
consists of roughly $7$ atoms and an additional $7$ atoms of
``scaffolding,'' or connecting atoms with no pharmacophore functionality.

Table~\ref{CRS-PARM} details the parameters used for invariant identification.
The parameters $\epsilon$, $\delta$, and $\alpha$ are as described in
Section~\ref{sec:inv}. 
The value $n$
is the number of times the MATCH algorithm is run per comparison, 
or the maximum number of invariants found per MATCH. These parameters
were chosen by experimentation. For example, $\delta$ was selected to
be much lower than $\epsilon$. We found that higher values of $\delta$
increased the running time without improving the quality of the solution.


{\small
\begin{table}
\begin{center}
\begin{tabular}{|c|l|l|} \hline
Parameter	& Search Value	& Prune Value 	\\ \hline
$\epsilon$	& $1.3$		& $3.5$		\\ 
$\delta$	& $0.5$		& $1.0$		\\ 
$\alpha$	& $0.3$		& $1.0$		\\ 
$n$		& $5$		& $5$		\\ 
\hline
\end{tabular}
\end{center}
\caption{Parameters for Invariant Search Trials}
\label{CRS-PARM}
\end{table}
}

In section \ref{sec:inv}, we assume that the distance distribution for
molecules satisfies certain properties, and show certain performance
bounds based on this. Here, we show experimental validation of these
bounds.

Fig. \ref{fig:search} plots the number of candidate transformations
produced ($\sum_{i=1}^{n/\alpha^2} \Delta_i$) by TWO-SET against
$\alpha$. Superimposed on this is a plot of $n/\alpha^2-1/\alpha^3$.
We do the same for BASIC-SAMPLE in Fig. \ref{fig:search}. For both
algorithms, the experimental results follow the predicted behaviour.
In Fig. \ref{fig:compare}, we compare the two schemes experimentally,
which clearly shows that TWO-SET performs better experimentally, although
its asymptotic performance seems worse.

\begin{figure}
\label{fig:search}
\vspace{0.3in}
\centerline{
\setlength{\unitlength}{1mm}
\begin{picture}(100,50)
\put(-30,0){\psfig{figure=hs.ps,height=6cm}}
\put(55,0){\psfig{figure=rs.ps,height=6cm}}
\end{picture}
}
\caption{Experimental results vs. Theoretical predictions}
\end{figure}


This discrepancy can be partly explained by the following sequence of
figures, Figs. \ref{fig:1tlp}, \ref{fig:4tmn}.
For each molecule in the input set, we plot its distance
distribution function, (which BASIC-SAMPLE samples from), as well the
distribution function induced by the subset of distances that TWO-SET
samples (for varying values of $\alpha$). 

\newpage

\begin{figure}
\label{fig:compare}
\centerline{
\psfig{figure=hr.ps,height=6cm}
}
\caption{How the two schemes perform relative to each other}
\end{figure}

\begin{figure}
\label{fig:1tlp}
\centerline{
\setlength{\unitlength}{1mm}
\begin{picture}(100,50)
\put(-30,0){\psfig{figure=1tlp.ps,height=6cm}}
\put(55,0){\psfig{figure=4tmn.ps,height=6cm}}
\end{picture}
}
\end{figure}

\begin{figure}
\label{fig:4tmn}
\centerline{
\setlength{\unitlength}{1mm}
\begin{picture}(100,50)
\put(-30,0){\psfig{figure=5tmn.ps,height=6cm}}
\put(55,0){\psfig{figure=6tmn.ps,height=6cm}}
\end{picture}
}
\end{figure}

\newpage
We also present comparisons between the two schemes on large data sets, 
where we vary the number of conformations per molecule. In all cases, the
the quality of solutions (in terms of the largest solution found) is
comparable, and TWO-SET consistently runs faster than BASIC-SAMPLE.

{\small
\begin{table}
\begin{center}
\begin{tabular}{|c|c|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline
Number of 	& Time to	& \multicolumn{13}{|c|}{Histogram of Solution Sizes}	\\  \hline
Conformations	& Completion (in s)& 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & total\\ \hline \hline
\multicolumn{15}{|c|}{BASIC-SAMPLE} \\ \hline
1		& 4.62	&   & 2  & 1  &   &   &   &    &    &    &    & 1 &  &    \\ \hline
11		& 2127.66 & 90  & 34  & 20  & 5 & 6 & 4  & 1 & 1 & 1 &  & & &  \\ \hline
21		& 24175.42 & 289  & 110  & 46  & 35  & 42  &18 & 3 &6 & 2 & 2
&  1& &  \\ \hline
\multicolumn{15}{|c|}{PARTITION-SAMPLE} \\ \hline
1		& 2.85	&   &   & 1  &   & 1  &   &    &    &    &  1  &   &    &     \\ \hline
11		& 656.47  & 20  & 9  & 8 & 11  &  11  & 3  &    &    &    &      & & &\\ \hline
21		& 8060.00  & 73 & 55  & 53  & 30  & 21  & 25 & 7 & 8 & 1 &
1 & 4 & 1 &  \\ \hline

\end{tabular}
\end{center}
\vspace{-0.3cm}
\caption{Comparison of the two schemes}
\label{CRS-COMPARE}
\end{table}
}

produced are given in Table \ref{CRS-COMPARE}.
In all cases, the correct invariant was found.  In trials with more
conformations, larger sized solutions were produced because some of the added
conformations had additional ``scaffolding'' which also could be matched.
Yet, in every case, the invariant of the largest size was the ``correct
solution.'' Many non-trivial solutions of size $8-14$ were produced, as
well a large number of trivial solutions of size $4$, 

