\documentclass[12pt,a4paper]{article}
\usepackage{graphicx}
\graphicspath{{eps/}{pdf/}}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

%-----------------------------------------------------------------------

\noindent
{\bf Data Mining 2: Frequent Pattern Mining} \hfill Summer 2018 \\
Christian Borgelt \hfill from 09.07.2018

%-----------------------------------------------------------------------

\vskip3ex
\centerline{\bf Exercise Sheet 10}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 36 \quad\rm Molecular Description Languages}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Draw the molecule that is described
     by the following SMILES string: \par
     \centerline{\tt
     S2c1c4c(ccc1N(c3c2cccc3)C(=O)C)cccc4}
\item[b)\hfill]
     Draw the molecule that is described
     by the following SLN string: \par
     \centerline{\tt\ \ \ 
     NH2C[1]:N:C(:C(:N:C:@1C(=O)OCH3)C(=O)C[2]:CH:CH:CH:CH:CH:@2)NH2}
\item[c)\hfill]
     \parbox[t]{90mm}{Construct a SMILES description
     of this molecule:}\hskip12mm
     \lower5.2ex\hbox{\includegraphics{fpmex-0}}
\item[d)\hfill]
     \parbox[t]{90mm}{Find at least three different SMILES
     descriptions of phenol, that is, of this molecule:}\hskip12mm
     \lower2.7ex\hbox{\includegraphics{fpmex-1}}
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 37 \quad\rm Molecular Description Languages}

\newsavebox\mybox
\begin{lrbox}{\mybox}
\begin{minipage}{\textwidth}
\begin{verbatim}
4728
          1016 111283D                        4728

  9  9        0                 1 V2000
   -0.0965    1.3884    0.0104 N   0  0  0  0  0  0  0  0  0
    1.8297   -0.2821   -0.0166 S   0  0  0  0  0  0  0  0  0
    1.0302    2.1371    0.0038 N   0  0  0  0  0  0  0  0  0
    0.1607    0.0664    0.0009 C   0  0  0  0  0  0  0  0  0
    2.1519    1.3924   -0.0108 C   0  0  0  0  0  0  0  0  0
    3.3971    1.9238   -0.0196 N   0  0  0  0  0  0  0  0  0
   -0.5873   -0.6698    0.0040 H   0  0  0  0  0  0  0  0  0
    3.5072    2.8871   -0.0156 H   0  0  0  0  0  0  0  0  0
    4.1746    1.3453   -0.0300 H   0  0  0  0  0  0  0  0  0
  1  4  2  0  0  0  0
  1  3  1  0  0  0  0
  2  4  1  0  0  0  0
  2  5  1  0  0  0  0
  3  5  2  0  0  0  0
  4  7  1  0  0  0  0
  5  6  1  0  0  0  0
  6  8  1  0  0  0  0
  6  9  1  0  0  0  0
M  END
$$$$
\end{verbatim}
\end{minipage}
\end{lrbox}

Draw the molecule that is described by the following SDfile: \\[.7ex]
\scalebox{0.62}{\usebox\mybox}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 38 \quad\rm Subgraph Isomorphisms}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How often does the fragment {\tt C-C-C} occur in phenol
     (see Exercise~36d)? \\
     In other words: How many subgraph isomorphisms exist?
\item[b)\hfill]
     Does phenol (see Exercise~36d) possess an automorphism
     that is not the identity? \\
     How many different automorphisms does phenol possess?
\item[c)\hfill]
     Construct the set of all connected subgraphs of phenol
     (see Exercise~36d)!
\item[d)\hfill]
     Find all bonds in phenol (see Exercise~36d) that are bridges! \\
     Are any of these bridges proper bridges?
\item[e)\hfill]
     Find all bonds in the graph/molecule from Exercise~36c)
     that are bridges! \\
     Which of these bridges are proper bridges?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 39 \quad\rm Searching for Frequent Subgraphs}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{86mm}{Find all frequent (sub)graphs containing sulphur
     for a minimum support $s_{\min} = 3$ in the graph database
     (SMILES format) shown on the right:}\hfill
     \begin{minipage}[t]{49mm}
     \begin{verbatim}
CCS(O)(O)N    CCS(=N)N
CCS(O)(C)N    CS(=N)N
CS(O)(C)N     CS(=N)O\end{verbatim}%
     \end{minipage}
\item[b)\hfill]
     Why is it more difficult to avoid redundant search
     when searching for frequent (sub)graphs
     than for frequent item sets?
     What are the main problems?
\item[c)\hfill]
     What is the purpose of constructing code words of (sub)graphs? \\
     What is a canonical code word? What do we actually need?
\item[d)\hfill]
     How do we assign a unique parent (sub)graph
     based on a canonical code words for a (sub)graph?
     What information from the canonical code word do we use?
\end{enumerate}

%-----------------------------------------------------------------------

\end{document}
