text:
\section*{Deviations from JavaScript}

We intend the
Source language to be a conservative extension
of JavaScript: Every correct
Source program should behave \emph{exactly} the same
using a Source implementation, as it does using a JavaScript
implementation. We assume, of course, that suitable libraries are
used by the JavaScript implementation, to account for the predefined names
of each Source language.

This section lists some exceptions where we think a Source implementation
should be allowed to deviate from the JavaScript specification, for the
sake of internal consistency and esthetics.

\begin{description}
\item[\href{https://sourceacademy.org/sicpjs/4.1.1\#footnote-4}{Evaluation result of programs:}]
  % from SICP JS 4.1.2, last exercise
JavaScript statically
        distinguishes between \emph{value-producing} and
	\emph{non-value-producing statements}. All declarations are
	non-value-producing, and all
	expression statements, conditional statements and assignments are
	value-producing.
	A block is value-producing if its body statement
	is value-producing, and then its value is the value of its body
	statement. A sequence is value-producing if any of
	its component statements is value-producing, and then its value is
	the value of its \emph{last} value-producing component statement.
	The value of an expression statement is the value of the expression.
	The value of a conditional statement is the value of the branch that
	gets executed, or the value
	\lstinline{undefined} if that branch is
	not value-producing.
	The value of an assignment is the value of the expression
	to the right of its \lstinline{=} sign.
	Finally, if the whole
	program	is not value-producing, its value is the value
        \lstinline{undefined}.

  Example 1:
  \begin{lstlisting}
1;
{
  // empty block
}
  \end{lstlisting}
  The result of evaluating this program in JavaScript is 1.

  Implementations of Source are currently allowed to opt for a simpler scheme.

\item[\href{https://sourceacademy.org/sicpjs/1.3.2\#footnote-2}{Hoisting of function declarations:}] In JavaScript, function declarations
  are ``hoisted''
  (\href{https://sourceacademy.org/sicpjs/4.3.1#footnote-4}{automagically} moved)
  to the beginning of the block in which
  they appear (in Studio 2: the beginning of the program, because there are no blocks yet).
  This means that applications of functions that are declared
  with function declaration statements never fail because the name is not
  yet assigned to their function value. The specification of Source does
  not include this hoisting.
  As a consequence, application of functions declared with function declaration
  may fail in Source if the name that appears as function expression is not yet
  assigned to the function value it is supposed to refer to.
\end{description}


text:
\chapter{Experiment} \label{Experiment}
In this section, LOF is compared to OCSVM on detecting outliers. The methodology of the research, input data and evaluation criteria are described and the results of the two algorithms are interpreted.

A comparison of algorithms is done by using a practical example as a test case. While this doesn't unequivocally say which algorithm is better, it will give some evidence towards which one is better for a complex high-dimensional dataset.

The running environment of this experiment consists of a Dell personal computer with quad-core processors running at 3.20 GHz with 8 GB of main memory DDR3. The operating system used is Ubuntu 14.04 LTS. The experiment was conducted using the Python programming language version 3 \footnote{Python programming language site: \url{https://www.python.org}.}, where both algorithms are implemented using built-in functions imported from the Scikit learn library
\footnote{Scikit learn library site: \url{http://scikit-learn.org}.}.
\section{Methodology}
The question of this research is: which one of LOF and OCSVM is better in detecting outliers in a highly unbalanced dataset? A highly unbalanced dataset means the number of normal observations is very high compared to the number of outliers. The workflow in Figure~\ref{workflow} describes the comparative study steps to answer the previous question.
\begin{figure}[!h]
\centering
\includegraphics[width=8cm,resolution=600]{images/workflow}
\caption{Methodology for comparing the performance of LOF and OCSVM algorithms on detecting fraud transaction on a credit card transactions dataset.}
\label{workflow}
\end{figure}

The LOF algorithm requires one parameter $k$; which is the number of close neighbors that each normal observation should have, as mentioned in Chapter~\ref{Local_Outlier_Factor}. OCSVM requires two parameters: $\gamma$ defines how far the influence of an observation reaches, and $\nu$ is the proportion of outliers expected in the data. More details are in Section~\ref{OCSVM}.

In OCSVM selecting a kernel has a huge impact on the results that are generated. RBF is more flexible than other kernels, so the best possible prediction would be obtained \citep{RBFkernel}.

Once the dataset and algorithm requirements are know, the results of LOF and OCSVM need to be compared. The results of these algorithms are lists of detected outliers. True Positive Rate (TPR) and False Positive Rate (FPR) will be used for comparison this is described in Section~\ref{evaluation_matrices}. Then the study of detected outliers is interpreted to understand the performance of each algorithm in the dataset.
\section{Input Data}
A dataset from Kaggle data science repository is used to evaluate the performance of the algorithms. The dataset that has been used contains information of credit card transactions made by credit cards in September 2013 by European cardholders \footnote{The credit cards transactions dataset is available in \url{https://www.kaggle.com/dalpozz/creditcardfraud}.}. The aim is to detect the fraudulent transactions, for example transferring or withdrawing unusually large amounts of money from one account. These transactions are considered as outliers.
The dataset consists of 284,807 transactions, 492 of which are fraudulent. Each transaction has 32 numerical variables which contain 28 features which are the results of Principal Component Analysis (PCA) transformation. The original features have been obscured to protect anonymity.

Figure~\ref{distribution} represents the transactions amount of the observations in the dataset after the preprocessing. Evidently, the number of fraud observations is less than the number of normal observations, which makes the credit card transactions dataset an unbalanced dataset. The fraud transactions (outliers) has a normal behaviour.
\begin{figure}[!h]
\includegraphics[width=1.0\textwidth]{images/distribution}
\caption{Normal and fraud transactions amounts distribution of a credit card fraud dataset}
\label{distribution}
\end{figure}

The data needs to be preprocessed before applying the algorithms due to running environment limitations. This is performed by selecting the 28 features and by choosing some observations randomly using the Random library in Python \footnote{The Random library in Python is available in \url{https://docs.python.org/3/library/random.html}.}, and including all the outliers in the data set. More precisely, 40,000 observations are selected randomly from the dataset and all the outliers 492 observations were included in the new dataset. \newpage
The percentage of normal observations is approximately 98.59$\%$, while it is approximately 1.41$\%$ outliers out of 100$\%$.  The dataset is classified into two classes: normal observations and outliers.
The new dataset was split into classes as shown in Table~\ref{tab:mylabel} with respect to the algorithm.

In LOF algorithm a range of 10 values has been used for $k$. The $k$-lower bound was 10 and the $k$-upper bound was 100. Also, OCSVM has a range of 10 values for its parameters $\nu$ and $\gamma$. $\nu$ starts from 0.01 and ends with 0.02, $\gamma$ starts from 0.001 and ends with  0.0001. (These parameters are chosen because they showed the best performance after testing).

LOF algorithm uses the entire dataset to train the classifier based on the density of the observations, using the steps described in Chapter~\ref{Local_Outlier_Factor}. OCSVM algorithm splits the data into two sets, the first set is for classifier training which contains just the normal observations, while the second set is used to test the classifier.
\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|}
\hline
\rowcolor[HTML]{9B9B9B}
\textbf{Algorithm}      & \textbf{Training} & \textbf{Testing}  \\ \hline
\textbf{LOF}   & 40492    & 40492        \\ \hline
\textbf{OCSVM} & 30000    & 10492    \\ \hline
\end{tabular}
\caption{Observations division in LOF and OCSVM. LOF takes all the observations in training and testing while OCSVM divide the dataset into training data and testing data.}\label{tab:mylabel}
\end{table}
\vspace{-2.2em}
\section{Evaluation Metrics}\label{evaluation_matrices}
\vspace{-0.5em}
Evaluating the performance of LOF and OCSVM requires a performance measurements that can scale the output into useful information. One of the performance measurements is a confusion matrix. A confusion matrix is a technique to summarize the performance of a classification algorithm by comparing the actual value of the class with the predicted value \citep{Confusion}. Considering a normal observation as positive and an outlier as negative, there are four possible outcomes from the binary classifier. Figure~\ref{confusion-matrix} shows the confusion matrix components.
\begin{figure}[!h]
\qquad \quad
\includegraphics[width=0.7\linewidth,resolution=300]{images/con_mat}
\caption{Confusion matrix components. Positive sign refers to normal observations and minus sign refers to outliers. The components obtain by comparing actual to predicted values.}
\label{confusion-matrix}
\end{figure}

Most of the machine learning methods use an accuracy rate to explain the behavior of a classifier. However, an accuracy rate doesn't perform well in unbalanced datasets \citep{ROC}.

\textbf{Confusion Matrix Components:}
\begin{itemize}
\item True Positive (TP): When the actual value is a normal observation and the predicted value is normal.
\item True Negative (TN): When the actual value is an outlier observation and the predicted value is an outlier.
\item False Positive (FP): When the actual value is an outlier and the predicted value is a normal observation.
\item False Negative (FN): When the actual value is normal and the predicted value is an outlier.
\end{itemize}
To evaluate the classification of unbalanced dataset two components of the confusion matrix, TP and FP are combined to form a new measurement Receiver Operator Characteristic (ROC) curve.

\textbf{ROC curve:}

An ROC curve is a two-dimensional graph with False Positive Rate (FPR) on the x-axis and True Positive Rate (TPR) on the y-axis, which visualizes the performance of the classifier \citep{ROC}.

\textbf{True Positive Rate:}
Also called the recall rate or sensitivity rate, The TPR is defined as the proportion of positive observations that are correctly classified as positive \citep{AUROC}:
$$
\text{TPR} = \frac{\text{Positives correctly classified}}{\text{Total actual positives}} = \frac{\text{TP}}{\text{TP+FN}}
$$

\textbf{False Positive Rate:}
Also called the fallout rate, the FPR is defined proportion of negative observations that are incorrectly classified as positive \citep{AUROC}:
$$
\text{FPR} = \frac{\text{Negatives incorrectly classified}}{\text{Total actual negatives}} = \frac{\text{FP}}{\text{FP+TN}}
$$

In Figure~\ref{OCSVM2D} the top left corner of the graph is the optimal point where the FPR is 0 and TPR is 1 which is the largest Area Under the Curve (AUC) region. AUC is used in order to determine the best model that predicts the classes \citep{AUROC}.

The good classifier is the one with high TPR and low FPR which results in large AUC region \citep{AUC}. In other words, the higher the TPR, the fewer positive observations will be missed. The higher the FPR, the more negative observations will be incorrectly classified \citep{AUROC}.
The AUROC is between 0 and 1, and AUROC = 1 means the prediction model perfectly classifies the test data.
%\vspace{-1em}
\section{Analysis and Results}
%\vspace{-0.7em}
The results of LOF for detecting fraud credit card transactions with two features are shown in Figure~\ref{LOF2D}. The LOF algorithm was able to detect the fraud transactions (outliers) using test features (2-dimensional space). In Figure~\ref{OCSVM2D} OCSVM detects the fraud transactions (outliers) in two features (2-dimensional space), and it also defines the region of the normal credit card transactions.
%\vspace{-1.2em}
\begin{figure}[H]
\centering
\minipage{0.45\textwidth}
  \includegraphics[width=8.5cm]{images/2features_LOF}
  \caption{LOF results of 2 features\\with $k=20$.}
  \label{LOF2D}
\endminipage\hspace{0.7cm}
\minipage{0.45\textwidth}
  \includegraphics[width=8.5cm,height=6.5cm]{images/2features_OCSVM}
    \caption{OCSVM results of 2 features with $\nu$=0.1, $\gamma$=0.1 and RBF kernel.}
      \label{OCSVM2D}
\endminipage
\end{figure}
%\vspace{-1.5em}
The behavior of LOF has been changed when 28 features applied. Table~\ref{tab:myLOF} shows the percentages of the performance measurement results for outlier detection within a range of values for $k$-nearest neighbors with 28 features. Table~\ref{tab:myOCSVM} shows the the percentages of the performance measurement results with different values for $\gamma$ and $\nu$ parameters. the parameters for both algorithms were chosen to be near optimal parameters which is done by testing different ranges of parameter values ranges.

To measure the results, ROC curves have been introduced, which is a performance measurement for unbalanced datasets by comparing the TPR and FPR.

The ROC curve is generated by using ten parameter values for $k$ in LOF algorithm, each one has its own AUC. The same for OCSVM, ten parameter values for $\nu$ and $\gamma$ are used. The values for $k$, $\nu$ and $\gamma$ are the ones that give highest percentages of TPR and AUC, it is also the values that find the lowest percentage of FPR for both algorithms. Note that using different parameter values will result in different TPR, FPR and AUC percentages.
\begin{table}[H]
\centering
\begin{tabular}{|l|c|c|c|c|c|c|l|}
\hline
\rowcolor[HTML]{9B9B9B}
\multicolumn{8}{|c|}{\cellcolor[HTML]{9B9B9B}\textbf{LOF}}                                                                                \\ \hline
\rowcolor[HTML]{C0C0C0}
\multicolumn{1}{|c|}{\cellcolor[HTML]{C0C0C0}$k$} & TP    & FN   & FP  & TN  & TPR    & FPR    & \multicolumn{1}{c|}{\cellcolor[HTML]{C0C0C0}AUC} \\ \hline
10                                              & 35939 & 3986 & 503 & 64  & 0.9001 & 0.8871 & 0.5227                                           \\ \hline
20                                              & 35952 & 3973 & 490 & 77  & 0.9004 & 0.8641 & 0.5163                                           \\ \hline
30                                              & 35967 & 3958 & 475 & 92  & 0.9008 & 0.8377 & 0.5021                                           \\ \hline
40                                              & 35980 & 3945 & 462 & 105 & 0.9011 & 0.8148 & 0.5074                                           \\ \hline
50                                              & 35984 & 3941 & 458 & 109 & 0.9012 & 0.8077 & 0.5128                                           \\ \hline
60                                              & 35982 & 3943 & 460 & 107 & 0.9012 & 0.8112 & 0.5105                                           \\ \hline
70                                              & 35977 & 3948 & 465 & 102 & 0.9011 & 0.8201 & 0.5012                                           \\ \hline
80                                              & 35981 & 3944 & 461 & 106 & 0.9012 & 0.8130 & 0.4848                                           \\ \hline
90                                              & 35980 & 3945 & 462 & 105 & 0.9011 & 0.8148 & 0.4670                                           \\ \hline
100                                             & 35990 & 3935 & 452 & 115 & 0.9014 & 0.7971 & 0.4477                                           \\ \hline
\end{tabular}
\vspace{1em}
\caption{The results of LOF are truncated to 4 digits. When $k$ value increases TPR increases and FPR decreases.}\label{tab:myLOF}
\end{table}

Figure~\ref{LOF_TPR_FPR} shows the highest percentage of AUC for LOF which is 52$\%$ for when $k$ = 10. From Table~\ref{tab:myLOF} the higher the $k$ value goes, the lower the AUC will be. In Figure~\ref{OCSVM_TPR_FPR} the percentage of AUC of OCSVM is higher than LOF. Precisely, AUC = 94$\%$. The value of AUC gets larger by increasing $\nu$ value and decreasing the $\gamma$ value. For both figures, the dashed diagonal line presents the baseline of ROC curve to see the performance of the model when the classes are assigned randomly. Preferable models are the ones above this line \citep{AUROC}.

\vspace{1em}
\begin{table}[H]
\centering
\begin{tabular}{|l|l|c|c|c|c|c|c|l|}
\hline
\rowcolor[HTML]{9B9B9B}
\multicolumn{9}{|c|}{\cellcolor[HTML]{9B9B9B}\textbf{OCSVM}}                                                                                \\ \hline
\rowcolor[HTML]{C0C0C0}
$\nu$ & \multicolumn{1}{c|}{\cellcolor[HTML]{C0C0C0}$\gamma$} & TP & FN & FP & TN & TPR & FPR & AUC \\ \hline
0.01  & 0.001                                                 & 9812        & 113         & 123         & 444         & 0.9886       & 0.2169       & 0.9307       \\ \hline
0.01  & 0.0009                                                & 9730        & 195         & 84          & 483         & 0.9803       & 0.1481       & 0.9350       \\ \hline
0.02  & 0.0008                                                & 9637        & 288         & 72          & 495         & 0.9709       & 0.1269       & 0.9360       \\ \hline
0.03  & 0.0007                                                & 9524        & 401         & 68          & 499         & 0.9595       & 0.1199       & 0.9375       \\ \hline
0.04  & 0.0006                                                & 9419        & 506         & 67          & 500         & 0.9490       & 0.1181       & 0.9387       \\ \hline
0.05  & 0.0005                                                & 9322        & 603         & 65          & 502         & 0.9392       & 0.1146       & 0.9390       \\ \hline
0.06  & 0.0004                                                & 9239        & 686         & 62          & 505         & 0.9308       & 0.1093       & 0.9394       \\ \hline
0.07  & 0.0003                                                & 9116        & 809         & 61          & 506         & 0.9184       & 0.1075       & 0.9399       \\ \hline
0.08  & 0.0002                                                & 9015        & 910         & 60          & 507         & 0.9083       & 0.1058       & 0.9403       \\ \hline
0.09  & 0.0001                                                & 8878        & 1047        & 59          & 508         & 0.8945       & 0.1040       & 0.9407       \\ \hline
\end{tabular}
\vspace{1em}
\caption{The results of OCSVM are truncated to 4 digits. The increase in $\nu$ value and the decrease in $\gamma$, decreases both TPR and FPR values.}\label{tab:myOCSVM}
\end{table}

Note that the LOF spends 17.1835 seconds to find the testing results of 10 parameter values for $k$, while OCSVM spends 85.7840 seconds for 10 parameter values for $\nu$ and $\gamma$.

\begin{figure}[H]
\begin{center}
\minipage{0.5\textwidth}
  \includegraphics[width=\linewidth]{images/LOF_ROC}
  \caption{LOF model results when parameter \\value $k$=10 gives the highest AUC percentage.}
  \label{LOF_TPR_FPR}
  \vspace{-1.5em}
\endminipage
\minipage{0.5\textwidth}
  \includegraphics[width=\linewidth]{images/OCSVM_ROC}
  \caption{Highest AUC (94$\%$) is obtained by setting the parameters $\nu$=0.09 and $\gamma$=0.0001.}
  \label{OCSVM_TPR_FPR}
  \vspace{-1.5em}
\endminipage
\end{center}
\end{figure}

\section{Discussion}
The experiment showed that both of algorithms detect outliers with different percentages. By comparing the values of the TPR rate and the FPR rate. It has been found that OCSVM algorithm had a higher percentage of TPR and a low percentage of FPR. The LOF algorithm on the other hand showed high FPR, which means it classified a large fraction of the fraud transactions as normal transactions. The TPR for LOF was very low, which results in a small number of actual normal transactions that were classified normal.

The poor performance of LOF was unexpected, even though the range of $k$-nearest neighbors was big. This might be because of the high dimensionality of the dataset and closeness of the fraud transactions (outliers) to the normal transactions. The poor performance results of LOF is not a fault of algorithm itself. The LOF algorithm might not be well-tested.

To summarise, the OCSVM algorithm took more time comparing to LOF algorithm (factor of $\frac{85.7840}{17.1835} \approx 1.7$), but it showed an excellent performance on detecting outliers, with a percentage starts from 93$\%$ to 94$\%$ for AUC. \footnote{All the codes that used to generate research results and more are available in: \url{https://github.com/sustecha/LOF_OCSVM.git}}

ext: tex


text:
\section*{Structure of exam \modulecode}
The general shape of a theoretical exam for \texttt{DEV 3} is made up of only two, highly structured open questions.

\paragraph{Question 1: } \ \\

\textbf{General shape of the question:} \textit{Given the following class definitions, and a piece of code that uses them, fill in the stack, heap, and PC with all steps taken by the program at runtime.}

\textbf{Concrete example of question:}

\lstset{numbers=left,basicstyle=\ttfamily\small}\lstset{language=[Sharp]C}
\begin{lstlisting}
interface ICounter {
  void Incr(int diff);
}
class Counter : ICounter {
  private int cnt;
  public Counter() {
    this.cnt = 0;
  }
  public void Incr(int diff) {
    this.cnt = (this.cnt + diff);
  }
}
ICounter c = new Counter();
c.Incr(5);
\end{lstlisting}

\textbf{Concrete example of answer:}

{
\small
\begin{enumerate}
\item Stack:
\begin{tabular}{ |c| }
		\hline
		PC \\
		\hline
		1 \\
		\hline

\end{tabular}
	\\

\item Stack: \begin{tabular}{ |c| }
		\hline
		PC \\
		\hline
		13 \\
		\hline

	\end{tabular}

Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt= \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c|>{\columncolor[gray]{0.8}}c|c|c|c| }
		\hline
		PC & ... & & PC & ret & this \\
		\hline
		13 & ...
		& & 7 & null & ref 1 \\
		\hline

	\end{tabular}

Heap:
\begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt= \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c|>{\columncolor[gray]{0.8}}c|c|c| }
		\hline
		PC & ... & & PC & ret \\
		\hline
		13 & ...
		& & 7 & ref 1 \\
		\hline

	\end{tabular}
	\\Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt=0 \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c| }
		\hline
		PC & c \\
		\hline
		14 & ref 1 \\
		\hline

	\end{tabular}
	\\Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt=0 \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c|>{\columncolor[gray]{0.8}}c|c|c|c|c| }
		\hline
		PC & ... & & PC & ret & diff & this \\
		\hline
		14 & ...
		& & 10 & null & 5 & ref 1 \\
		\hline

	\end{tabular}
	\\Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt=0 \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c|>{\columncolor[gray]{0.8}}c|c|c| }
		\hline
		PC & ... & & PC & ret \\
		\hline
		14 & ...
		& & 10 & null \\
		\hline

	\end{tabular}
	\\Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt=5 \end{tabular} \\
		\hline

	\end{tabular}\\

\item Stack: \begin{tabular}{ |c|c| }
		\hline
		PC & c \\
		\hline
		15 & ref 1 \\
		\hline

	\end{tabular}
	\\Heap: \begin{tabular}{ |c| }
		\hline
		1 \\
		\hline
		\begin{tabular}{c} cnt=5 \end{tabular} \\
		\hline

	\end{tabular}

\end{enumerate}
}

\textbf{Points:} \textit{4 (50\% of total).}

\textbf{Grading:} \textit{Full points for more than 90\% of correct names and values. Three points if at least all names are correctly placed on the stack with at least half the values correct. Half points for more than 40\% of correct names and values. Zero points otherwise.}

\textbf{Associated learning objective:} \glsfirst{abs}

\ \\

\paragraph{Question 2: } \ \\

\textbf{General shape of question:} \textit{Given the following class definitions, and a piece of code that uses them, fill in the declarations, class definitions, and PC with all steps taken by the compiler while type checking.}

\textbf{Concrete example of question:}

\lstset{numbers=left,basicstyle=\ttfamily\small}\lstset{language=[Sharp]C}
\begin{lstlisting}
interface ICounter {
  void Incr(int diff);
}
class Counter : ICounter {
  private int cnt;
  public Counter() {
    this.cnt = 0;
  }
  public void Incr(int diff) {
    this.cnt = (this.cnt + diff);
  }
}
ICounter c = new Counter();
c.Incr(5);
\end{lstlisting}

\textbf{Concrete example of answer:} \textit{}

{
	\small
	\begin{enumerate}
\item Declarations: \begin{tabular}{ |c| }
	\hline
	PC \\
	\hline
	1 \\
	\hline

\end{tabular}

\item Declarations: \begin{tabular}{ |c| }
		\hline
		PC \\
		\hline
		4 \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c| }
		\hline
		ICounter \\
		\hline
		\begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|c| }
		\hline
		PC & this \\
		\hline
		7 & Counter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int)$\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|c|c| }
		\hline
		PC & diff & this \\
		\hline
		9 & int & Counter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c| }
		\hline
		PC \\
		\hline
		13 \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|c| }
		\hline
		PC & c \\
		\hline
		14 & ICounter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|>{\columncolor[gray]{0.8}}c|c|c|c|c| }
		\hline
		c & & PC & ret & $arg_1$ & this \\
		\hline
		ICounter & & 14 & null & int & Counter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|>{\columncolor[gray]{0.8}}c|c|c|c|c| }
		\hline
		c & & PC & ret & $arg_1$ & this \\
		\hline
		ICounter & & 14 & void & int & Counter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

\item Declarations: \begin{tabular}{ |c|c| }
		\hline
		PC & c \\
		\hline
		15 & ICounter \\
		\hline

	\end{tabular}
	\\Classes: \begin{tabular}{ |c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
		\hline
		Counter & ICounter \\
		\hline
		\begin{tabular}{c} Counter=Counter $\rightarrow$ Counter \\Incr=(Counter$\times$int) $\rightarrow$ void \\cnt=int \end{tabular} & \begin{tabular}{c} Incr=(ICounter$\times$int) $\rightarrow$ void \end{tabular} \\
		\hline

	\end{tabular}

	\end{enumerate}
}

\textbf{Points:} \textit{4 (50\% of total).}

\textbf{Grading:} \textit{Full points for more than 90\% of correct names and types. Three points if at least all names are correctly placed on the declarations and classes, with at least half the types correct. Half points for more than 40\% of correct names and types. Zero points otherwise.}

\textbf{Associated learning objective:} \glsfirst{type}

\ \\


text:
% $Id: AppDriver_design.tex,v 1.1.5.1 2013-01-11 20:23:44 mathomp4 Exp $
%
% Earth System Modeling Framework
% Copyright 2002-2012, University Corporation for Atmospheric Research,
% Massachusetts Institute of Technology, Geophysical Fluid Dynamics
% Laboratory, University of Michigan, National Centers for Environmental
% Prediction, Los Alamos National Laboratory, Argonne National Laboratory,
% NASA Goddard Space Flight Center.
% Licensed under the University of Illinois-NCSA License.

%\subsection{Design}

The Application Driver directory contains subdirectories with sample
source files, each of which shows an example of using ESMF in a
different way.  The user decides on which strategy they want to follow
and then copies the files from the corresponding subdirectory into
their own directory. Some of the files can be used unchanged, others
are {\tt template} files which have the rough outline of the code but
need significant amounts of application-specific code added in order
to perform the desired computation.


text:
\section{Data Compression and Archiving}
%     zlib -- Compression compatible with gzip
%     gzip -- Support for gzip files
%     bz2 -- Support for bzip2 compression
%     lzma -- Compression using the LZMA algorithm
%     zipfile -- Work with ZIP archives
%     tarfile -- Read and write tar archive files

%

max_stars_repo_name: remigiusz-suwalski/programming-notes

max_issues_repo_name: remigiusz-suwalski/programming-notes

max_forks_repo_name: remigiusz-suwalski/programming-notes


text:
\section{A trail of breadcrumbs about finding killer words}

Here we outline our method for finding a decomposition of
the initial box ${\cal W}$ into sub-boxes,
each with a condition/killerword that kills off the entire associated sub-box,
or with an indication that it belongs to one of the exceptional regions.
For convenience, we will generally refer to a ``sub-box" simply as a ``box."

A naive approach uses diagonal enumeration
to combine breadth-first enumeration of the tree of boxes
with breadth-first enumeration of the tree of words
(with three edges from each word,
one for each generator or inverse-generator
that isn't the inverse of the last symbol in the word,
pointing to the concatenation of the word with the generator).
The naive algorithm has running time $O(3^L 2^D)$, where $L$ is maximum word length
and $D$ is maximum box depth.
Much too slow - $3^{44} 2^{120}$ operations is not close to reasonable.

To speed it up, there are three basic approaches, all of which are necessary:
\begin{enumerate}
  \item we can avoid considering most boxes by stopping once we have a solution
  \item we can reuse words that work on one box elsewhere
  \item and we can use geometric heuristics to prefer words
        that are more likely to work.
\end{enumerate}
The exposition will proceed in rough chronological order,
in the hope that by describing some of the wrong turns,
we'll help others avoid making the same mistakes.

The most obvious way of speeding up the search is to avoid
the search entirely when feasible: a killerword works on a neighborhood of a
region, and by testing killerwords found for nearby boxes, most of
the time the search is not necessary.

Still, there are words of length as long as 44 that were considered,
and testing all of the roughly $3^{44}$ combinations would be prohibitive.
In practice (due to a bug), the search algorithm used for most of the parameter
space was no better than the brute-force method just described,
but to find killerwords for the remaining regions, an improvement was needed.
Rather than blindly selecting words in first-in-first-out order,
the algorithm can rank the words under consideration
based on a heuristic estimate of the likelihood of their being useful
(a word is {\it useful} if it is a prefix of a killerword).
We note first that short words tend to be better than long words,
as they have fewer steps and less error.
Second, we note that words
with a large translation distance are given a bad ranking, for two reasons:
they will need more generators appended before they get back to the
small translation distance which is needed for a contradiction, and
computations with those words introduce more error per step than
computations with closer words.

This approach was an improvement, but was not finding enough killerwords in the regions
around $X_3$ and $X_4$.  Further investigation showed that the
algorithm was getting stuck on an identity: once it found an identity,
it would consider only words which started with that identity, and
ignored all of the other words.  To fix this problem, a ``diversity"
heuristic was introduced, to give special consideration to unlikely but
unusual words.

To prevent the search from running forever, it is
temporarily abandoned after some number of steps, and re-done
with twice as many steps every time the number of descendant boxes
doubles.  This way, the search could run forever, but only if
the subdivision process runs forever.
This merged process of alternately searching and subdividing we
call the {\it decomposition algorithm}.

The decomposition algorithm went through several revisions; at each stage
of the revision process,
the algorithm effectively increased the extent to which killerwords
found for one region were used to kill other regions.  The first
attempt---used to determine the feasibility of the whole effort---
iterated over regions in depth-first order, performing the search as
described above.
At that stage, it became evident that the search process, as
opposed to the subdivision process,
was consuming nearly all of the computation time, and so the second
version iterated over regions in breadth-first order, and, once it
found a killerword, tried to use that word on all adjacent regions.

The breadth-first version was used to analyze the entire parameter
space, although it skipped some parts due to various bugs; the search
heuristic was replaced once, and there was considerable human input
to tell the search about particularly difficult killerwords, or to tweak
its search parameters (length, and weightings in the heuristic).

The third stage of the revision process reduced the number of boxes
by attempting all found killerwords in a large region (about a thousand boxes)
on all boxes in the region.
It did not  do any searching,
since it was provided with a kist of killerwords known to work.

The final version was created when the bugs in evaluation were
brought to light, and the existing killerword tree was found to be insufficient.
It used the list of killerwords used for the entire tree, and some
statistics about the number of subdivisions required in order for a
given word to kill a particular box, and evaluated each word on each box.
Whenever a word was evaluated,
a kind of triage was used to determine
whether that word was likely to kill the box in question, likely to kill
any of its $n^{\rm th}$ generation descendants, or unlikely to kill any
descendants of the box; the answer to that heuristic either allowed more
detailed evaluation (with the error term included), deferred further
evaluation until the box had been subdivided $n$ more times, or
excluded that word from further consideration on any descendant of
the box.  With these heuristics, this program wound up evaluating on
average about 10 of the roughly 13200 words per box, and was able to
construct the tree consisting of the decomposition into sub-boxes with associated conditions/killerwords.

More recently, an updated version of the search program is in use
to solve a nearby problem, classification by enumeration of cusped hyperbolic
3-manifolds.
It's not far different from the final version of the search.
Indeed, its source code was edited from the final version.
The main differences are:
the search for new words that work is again mixed
with the search for words for all boxes;
the search for words combines pairs of words instead of appending a generator;
the logic for use of words is specific to the context of cusped manifolds.
The updated code is available at https://github.com/njt99/momsearch.


text:
\chapter{Introduction}
In both 2016 and 2017, many major anti-virus companies and Nokia, showed in their security reports how the Android mobile Operating System was the most targeted platform \cite{kaspersky} \cite{mcafee} \cite{nokia}: the reason behind such a great focus on this platform becomes clear when that information is used in combination with the market share data provided by the International Data Corporation. In fact, in the third quarter of 2016, Google's Operating System (OS) was running more than the 85\% of the smart-phones worldwide \cite{idcshare}. Moreover, based on the above-mentioned reports, the majority of devices gets infected by downloading a tainted app from the Play Store, despite Google's efforts to keep it a safe zone by leveraging many layers of automated testing. Furthermore, this is a problem which burdens especially those security-focused environments where devices need to run trusted software and administrators cannot even allow their users to download applications from the main store. In the next sections and chapters, I will investigate what is needed to tackle the problem of hardening Android applications, offering a compiler-based approach to find and patch common vulnerabilities, but even more importantly, evaluating if this solution could be an important asset in the fight against malware on the Android Ecosystem.

\section{Motivations}
Bug discovery and patching is an important part of every development cycle: the goal is always to produce a robust and reliable application for end users, especially for security-oriented ones. However, this process requires time and the modern market for mobile apps\footnote{short for applications}, moves at a tremendous speed, requiring companies to release software fast enough to not be out-sped by competitors. In parallel to this problem, the Android Operating System evolves constantly and, not only Google introduces new APIs in every version, but the entire ecosystem flourishes with new libraries, extensions and forks which get released everyday.
Keeping up with all this novelty can be cumbersome both for developers themselves, but also for companies which would like to provide up-to-date courses to others on how to write secure code. Moreover, Google provides only one page of security tips to programmers\footnote{\url{https://developer.android.com/training/articles/security-tips.html}}, but its worth to note that there is not a single line of code in the whole page and, even though it provides insights on where security holes might happen,  it leaves the task of figuring out how to avoid the described problems to the reader. In addition, developers are not helped in this regard when they are looking for information on the Internet: a quick search on how to solve \texttt{HTTPS} related problems, when making requests with Android, produces results on Stack-Overflow\footnote{\url{www.stackoverflow.com}} where the most up-voted answers tells to accept any kind of certificate for any given URL, as showed in \cite{svm-hunter}. Another example: when a developer looks on the Internet how to execute the sql \texttt{SELECT} statement on Android: the most up-voted answers claim that you need to use the \texttt{rawQuery} method which is subject to SQL Injections, as explained a few pages further. However, the most compelling argument for this work was given by the result of an automated investigation which I conducted on Android apps published on the Play Store. In fact, given all the problems described above, I assumed that most applications would be vulnerable to well known attacks and the results, as described in the evaluation chapter, were indicating that the hypothesis was correct and they also hinted at the necessity of this work.

\section{Contributions of this Work}
Since the first public release of the Android source code, which was made in April 2009\footnote{\url{https://developer.android.com/about/versions/android-1.5-highlights.html}}, tools such as CHEX\cite{chex}, DroidAlarm\cite{droidalarm} and the more recent AppoScopy\cite{apposcopy} provided means to perform static analysis and, on the other hand, AppsPlayground\cite{appsplayground} and AspectDroid\cite{AspectDroid} offered only ways to use dynamic analysis. The only tool which really patches common vulnerabilities is, as the name suggests, PatchDroid\cite{patchdroid}. However, its focus on back-porting patches to old devices for privilege escalation attacks and its reliance on the Dalvik byte-code made it cumbersome to use since Android 5 Lollipop, when ART and its on-device compilation was introduced, thus requiring re-packaging. Therefore, there is a need for a tool which can fill the gap that PatchDroid left on newer devices. The contribution of this thesis started by studying this need and by creating a prototype for it, namely DevArtist, which aim is to patch common security vulnerabilities by leveraging Android's ART runtime. Given the novelty of compiler-assisted patching tools, this work contributes also in evaluating this approach.

\section{Outline}
The structure of this work is as follows: knowledge about Android, ART and Information Flow control are introduced in the second chapter together with a primer on \emph{Artist} and its front-end \emph{ArtistGUI}. The third chapter discusses already existing research and how this work differentiates from it. The fourth chapter provides the need of this work: introducing the problems which \emph{DevArtist} solves and evaluating their severity. Chapter five describes the prototype produced for this thesis: it provides information about the design of such system and explains the algorithms developed. Furthermore, Chapter six shows how the evaluation of \emph{DevArtist} was conducted and presents its result.
Finally, Chapter eight draws the conclusions of this work after chapter seven has discussed what future development paths might be.


text:
In this chapter, we elaborate on deterministic system-level analysis and design
of electronic systems. The techniques that we discuss here do not take
uncertainty into account. However, these techniques provide an adequate
foundation for those that do, which is the topic of the subsequent chapters.

\section{\introductiontitle}
\inputsection{introduction}

\section{Transient Analysis}
\slab{transient-analysis}
\inputsection{transient-analysis}

\section{Static Steady-State Analysis}
\slab{static-steady-analysis}
\inputsection{static-steady-analysis}

\section{Dynamic Steady-State Analysis}
\slab{dynamic-steady-analysis}
\inputsection{dynamic-steady-analysis}

\section{Power-Temperature Interdependence}
\slab{power-temperature}
\inputsection{power-temperature}

\section{Reliability Optimization}
\slab{dream-optimization}
\inputsection{optimization}

\section{\conclusiontitle}
\inputsection{conclusion}

max_stars_repo_name: IvanUkhov/thesis

max_issues_repo_name: IvanUkhov/thesis

max_forks_repo_name: IvanUkhov/thesis


text:
\subsection{Differential forms}

\subsubsection{Type-I}

For type-I, we can integrate over y, then integrate over x.

\subsubsection{Type-II}

For type-II, we can integrate over x, then integrate over y.

max_stars_repo_name: adamdboult/nodeHomePage

max_issues_repo_name: adamdboult/nodeHomePage

max_forks_repo_name: adamdboult/nodeHomePage


text:
\documentclass[11pt]{article}
\usepackage[margin=2cm,a4paper]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{authblk}

\usepackage[superscript,biblabel]{cite}
\usepackage[super]{natbib}

\usepackage[style=numeric,sorting=none]{biblatex}
\addbibresource{references.bib}
\addbibresource{vancouver.bst}

\usepackage[outdir=./img/]{epstopdf}
\usepackage{epsfig}
\usepackage{url}
% Places figures at end of document, and do not print out the figures
\usepackage[nomarkers,nolists,tablesfirst]{endfloat}
%\renewcommand{\includegraphics}[2][]{}

\usepackage{xr}
\externaldocument{supplement}

\usepackage{tikz}
\usetikzlibrary{fit,positioning}
\usetikzlibrary{arrows}

\setlength\parindent{0pt}

\input{./title.tex}

\begin{document}

\maketitle

\begin{abstract}

\end{abstract}

\section*{Introduction}
  Pathway analysis is a relatively new concept in biology, with publications increasing drastically in the last 10 years. Thanks to advances in computational power and databases, pathway analysis has become increasingly feasable as a way of data analysis. The greatest advantage of pathway analysis is that it lets us consider biological processes as units rather than each individual gene or protein. Using pathway databases like the reactome database \cite{reactome}, you can also look at the pathway hierarchy to define subprocesses of particular mechanisms.

  A common conundrum in biology is the observation that nothing occurs in isolation, for example, a ligand binding to a receptor does not only cause a conformational change in the receptor, but also leads to a plethora of secondary actions, all dependent on each other. To account for this potential Whac-a-mole when influencing a specific target it is a good idea to look at the target in its pathway context.

  A common practice in pathway analysis is to tabularly present results. While this does outline the most interesting pathways, a lot of information is lost to truncation. Furthermore, tabular presentations of pathway analysis seldomly characterize the hierarchical relationships of the pathways and even less so in a comprehensive manner.

  EnrichmentMap \cite{enrichmentmap}, a network-based method for pathway visualization uses network nodes and edges to display pathway gene overlap. While effective, it could lead to difficulties in interpretation when it comes to larger pathways with whom many pathways share genes. Therefore, a new way of pathway visualization has been proposed, sunburst plotting. Sunburst plotting uses the same idea of network nodes and edges, but implemented in a hierarchical manner.

  Considering the pathway hierarchy as a tree, with the largest pathways at the bottom, and each subprocess building on top, a sunburst plot simply rotates the tree around the origo to maximize visibility. This directed network significantly lowers the complexity of the undirected network seen in EnrichmentMap. This is partly due to the conceding that a pathway can exist in multiple pathway hierarchies, and the sunburst implementation thus incorporates the pathway at each of its hierarchical positions. To show the differences in pathway activities, we suggest the use of colors based on p-values or q-values.

  As an example, sunburst plotting with a color scale going from green to red as p-value decreases would in a comparison of samples that differ greatly in apoptosis see a red line in the apoptosis hierarchy.

  Sunburst plotting complemented by a tabular view of the most interesting pathways gives a better understanding of the cell. It incorporates hierarchial relationships as well as the complete picture of the cell landscape.

\section*{Methods}
  Skin cell scRNA-seq data from a single cell study on drug-induced hypersensitivity syndrome was analysed through iDEA \cite{idea}. iDEA requires differential expression data as input, which was obtained through the zingeR-DESeq2 method for R \cite{deseq2}. Subsequently, iDEA was run using gene sets from the reactome database. iDEA was run according to the tutorial outlined in the documentation with the only difference being the $min\_precent\_annot$ parameter being set to $5E-5$ instead of $2.5E-3$. This was to allow smaller pathways to be considered in order to produce the complete pathway hierarchy in the sunburst plot.

  The resulting data were compiled into a hierarchical json file containing pathway name, p-value, number of genes and rank. The JSON data was subsequently displayed as a sunburst plot. One methodological choice was to display the plots in html format rather than to use existing pythonic methods. This choice was mainly due to the javascript library d3.js (\url{https://d3js.org/}) allowing for great interactivity and the ability to draw the plots as SVG vectors.

  The display also took the data from the json file and displayed the 40 pathways with the lowest p-value in a table to show where the most interesting areas were. This was done as a complement to the sunburst plot, to allow for pattern identification and to aid in the search for specific pathways, in particular the less visible ones.

  As outlined in the introduction, the sunburst plot is a visualization of a tree-shaped network. The tree is simply rotated around the middle to maximize visibility. The size of the nodes are relative to the size of the pathway and in comparison to all other pathway at the specific hierarchical level.

  When it comes to the color scale, seen in figure \ref{fig:color_scale}, it scales from p=1 to p=0 from green to red. The scale is logarithmic in order to better discern pathways with high p-value from pathways with low p-value.

  In order to reduce clutter and excessive information, the sunburst plot utilizes an information box, seen in the center of figures \ref{fig:full_sunburst} and \ref{fig:mop_specific}. The box contains the pathway name, number of genes, p-value and rank to give specific information about the pathway in question.

  \begin{figure}[t]
    \centering
    \tikzstyle{start} = [rectangle, rounded corners, minimum width=3cm, text width=12cm, minimum height=1.7cm, text centered, draw=black, fill=red!10]
    \tikzstyle{iDEA} = [rectangle, rounded corners, minimum width=3cm, text width=12cm, minimum height=1.7cm, text centered, draw=black, fill=red!20]
    \tikzstyle{JSON} = [rectangle, rounded corners, minimum width=3cm, text width=12cm, minimum height=1.7cm, text centered, draw=black, fill=red!30]
    \tikzstyle{sunburst} = [rectangle, rounded corners, minimum width=3cm, text width=12cm, minimum height=1.7cm, text centered, draw=black, fill=red!40]
    \tikzstyle{arrow} = [thick, ->, >=stealth]

    \begin{tikzpicture}
    \node (start) [start] {Differential expression analysis};
    \node (iDEA) [iDEA, below of=start, yshift=-1.2cm]{Pathway analysis using the iDEA method};
    \node (JSON) [JSON, below of=iDEA, yshift=-1.2cm] {Generate hierarchical data structure including pathway information for sunburst plotting};
    \node (sunburst) [sunburst, below of=JSON, yshift=-1.2cm] {Sunburst plotting};

    \draw [arrow] (start) -- (iDEA);
    \draw [arrow] (iDEA) -- (JSON);
    \draw [arrow] (JSON) -- (sunburst);

    \end{tikzpicture}
  \caption{ A flowchart representation of the pipeline developed for this article.}
  \label{Pipeline flowchart}
\end{figure}

\subsection*{Datasets}
  Datasets are available at \url{https://www.ncbi.nlm.nih.gov/geo/query/acc.cgi?acc=GSE132802}
\subsection*{Code availability}
  Code is available at \url{https://github.com/statisticalbiotechnology/porch}

\section*{Results}

  Results from the iDEA pathway analysis of the single cell data can be seen in figure \ref{fig:full_sunburst} with the color scale in figure \ref{fig:color_scale}. At first glance, you can already tell where the focal points of the study lie. If you consider the plot like a clock, around one o'clock, the pathway with the lowest p-value, metabolism of proteins \cite{reactome} lies. Translation, a child pathway of metabolism of proteins, can be seen in orange right above. Around eight o'clock, the metabolism pathway can be found.

  Also seen in the middle of \ref{fig:full_sunburst} is a box containing information on the pathway at hand. Perhaps not demonstrated perfectly in a static image, the box follows the computer mouse and displays information over which pathway the mouse hovers. The greatest advantage of this is to display the name of the pathway in question, however, information on the number of genes and p-value can definitely come in handy, especially in cases where the pathway can't be found in the table.

  Clicking a specific pathway can be used as a zooming tool. Seen in figure \ref{fig:mop_specific} is the sunburst specific for the metabolism of protein pathway. This plot has the same logic as the full sunburst, with every outer circle being one step further from the main pathway in question. Since the reactome database contains around 2000 pathways, a way of displaying them all would have to find a way of fitting them all into a neat container. The interactive step of being able to view specific pathways individually solves this, by producing a new canvas independent of the complete pathway hierarchy. To aid in navigation, a navigation bar of the pathway hierarchy can be used.

  As can be seen in figure \ref{fig:full_sunburst}, this was done by sizing the cells by pathway size. The middle being

  Furthermore, one quick observation is that the iDEA pathway analysis method seem to prefer larger pathways as the larger pathways tended to be colored more orange, whilst smaller pathways tended to be more green.

  GSEA BRCA analysis.

  The use of sunburst plots has also been demonstrated in cancer transcriptomics. The large metabric dataset for breast cancer was analysed through GSEA, comparing a number of different groups. An example comparing BRCA1 mut/WT samples can be seen figure \ref{fig:brca1}. Compared to the single cell example, GSEA gives clearer "lines" of parent/child pathways following the same pattern. This

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.96\linewidth,clip]{./img/full_sunburst.png}
\caption{\label{fig:full_sunburst} {\bf Sunburst plot.} Hierarchical representation of all cellular pathways colored by p-value}
\end{center}
\end{figure}

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.96\linewidth,clip]{./img/table.png}
\caption{\label{fig:table} {\bf Pathway table.} Tabular representation of the 40 pathways with the lowest p-value}
\end{center}
\end{figure}

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.96\linewidth,clip]{./img/mop_specific.png}
\caption{\label{fig:mop_specific} {\bf Pathway specific sunburst.} Sunburst plot drawn specifically for the metabolism of proteins pathway hierarchy}
\end{center}
\end{figure}

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.96\linewidth,clip]{./img/color_scale.png}
\caption{\label{fig:color_scale} {\bf Sunburst color scale.} The sunburst color scale annotated by which p-value they represent.}
\end{center}
\end{figure}

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.96\linewidth,clip]{./img/BRCA1.png}
\caption{\label{fig:brca1} {\bf Metabric GSEA} A sunburst representation of GSEA comparing BRCA1 mut/WT.}
\end{center}
\end{figure}

\section*{Discussion}
  One of the greatest advantages of sunburst plotting is the possibility to view all cellular pathways simultaneously in their hierarchical context. Tabular views generally only gives a glimpse of the most interesting pathways while neglecting the bulk of pathways.

  Sunburst plotting as a complement to a tabular view gives a more holistic view of pathway activities in the cell.

  One great feature of sunburst plots is the possibility to see parent-child pathway relationships. As seen in figure \ref{fig:mop_specific}, child-pathways of the metabolism of proteins pathway have quite different p-values.

  Another advantage of sunburst plotting is the speed to which a primary conclusion can be made of where the focal points of the experiment lie. While tables might give a similar conclusion, a significant amount of time will have to be spent to reach it.

  Sunburst plotting together with the tabular analysis described above became an excellent combination of analyses as the table provides very specific information of the pathways and the sunburst plots provide a broader picture of the pathway relationships of cells.

  One aspect where the advantage of using sunburst plotting became undeniable was when analysing parent child pathway relationships. As can be seen in figure \ref{fig:mop_specific}, the expression of some pathways (green) differs from the activity of Z (orange). This thus becomes somewhat of a barcoding analysis where a straight line of parent child pathways with low p-value is quite convincing evidence against type I errors.

  Seeing as this is a relatively novel method of analysis, a few points of benchmarking and what the underlying biology might be have been developed.

  \begin{itemize}
      \item A parent pathway with relatively medium p-value and several child-pathways where at least one of them has very low p-value is a good indicator that the parent pathway p-value might be affected by a change in the significant child pathway.
      \item A significant pathway with no children should be an interesting pathway to study as it has been broken down as much as possible and still poses a significant difference in activity compared to other clusters.
      \item A significant parent pathway with insignificant child pathways need to be examined further as neither of the subprocesses have been deemed significant.
    \end{itemize}

\section*{Acknowledgments}

This work was supported by a grant from the Swedish Research Council (grant
2017-04030).

\section*{Author Contributions}

\section*{Competing interests}

The authors declare that they have no conflict of interest.

\printbibliography[title=References]

\end{document}

max_stars_repo_name: statisticalbiotechnology/wall

max_issues_repo_name: statisticalbiotechnology/wall

max_forks_repo_name: statisticalbiotechnology/wall


text:
\subsection{Interface}

The standard netlist include file {\tt{}std.net} adds wrappers for
the basic model functions.  This is also the right place to put
commonly-used composite model functions.

For models that require a material parameter, our convention
is to add the material identifier as an additional ``positional''
parameter to the wrapper function, after the node numbers.
For example, to create a two-dimensional beam in the {\tt{}p1} process,
we would write
\begin{verbatim}
  beam2d {A, B, p1; w=2u}
\end{verbatim}
For contrast, the corresponding call to {\tt{}element} would be
\begin{verbatim}
  element {A, B; model="beam2d", material=p1, w=2u}
\end{verbatim}

\subsection{Implementation}

\nwfilename{std-net.nw}\nwbegincode{1}\sublabel{NWstdA-std7-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWstdA-std7-1}}}\moddef{std.net~{\nwtagstyle{}\subpageref{NWstdA-std7-1}}}\endmoddef
use("xformstack.lua")
use("relpos.lua")
use("subnetize.lua")

\LA{}model wrappers~{\nwtagstyle{}\subpageref{NWstdA-modE-1}}\RA{}
\nwnotused{std.net}\nwendcode{}\nwbegindocs{2}\nwdocspar

The {\tt{}beam2d} wrapper adds relative position information
if the length parameter {\tt{}l} is defined.  The {\tt{}beam2d}
function is ``subnetized,'' so specifying {\tt{}ox}, {\tt{}oy},
and {\tt{}oz} results in a rotated beam (a la SUGAR 2.0).

\nwenddocs{}\nwbegincode{3}\sublabel{NWstdA-modE-1}\nwmargintag{{\nwtagstyle{}\subpageref{NWstdA-modE-1}}}\moddef{model wrappers~{\nwtagstyle{}\subpageref{NWstdA-modE-1}}}\endmoddef
subnet beam2d(A, B, material, l, w, h)
  if l then
    relpos_add(A, B, top_xform(\{l, 0, 0\}))
  end
  element \{A, B; model="beam2d", material=material, l=l, w=w, h=h\}
end

\nwalsodefined{\\{NWstdA-modE-2}\\{NWstdA-modE-3}}\nwused{\\{NWstdA-std7-1}}\nwendcode{}\nwbegindocs{4}\nwdocspar

The semantics of the {\tt{}force} wrapper are not the same
as those of the SUGAR 2.0 force.
Perhaps the {\tt{}force} wrapper should also be ``subnetized''?
Alternatively, we might add a separate wrapper (specifically
to ease porting SUGAR 2.0 netlists) that applies a force along
a specified axis.

\nwenddocs{}\nwbegincode{5}\sublabel{NWstdA-modE-2}\nwmargintag{{\nwtagstyle{}\subpageref{NWstdA-modE-2}}}\moddef{model wrappers~{\nwtagstyle{}\subpageref{NWstdA-modE-1}}}\plusendmoddef
subnet force()
  args.model    = "force";
  element(args);
end

\nwendcode{}\nwbegindocs{6}\nwdocspar

\nwenddocs{}\nwbegincode{7}\sublabel{NWstdA-modE-3}\nwmargintag{{\nwtagstyle{}\subpageref{NWstdA-modE-3}}}\moddef{model wrappers~{\nwtagstyle{}\subpageref{NWstdA-modE-1}}}\plusendmoddef
subnet anchor(A, material, l, w, h)
  element \{A; model="anchor", material=material, l=l, w=w, h=h\}
end

\nwendcode{}

\nwixlogsorted{c}{{model wrappers}{NWstdA-modE-1}{\nwixu{NWstdA-std7-1}\nwixd{NWstdA-modE-1}\nwixd{NWstdA-modE-2}\nwixd{NWstdA-modE-3}}}%
\nwixlogsorted{c}{{std.net}{NWstdA-std7-1}{\nwixd{NWstdA-std7-1}}}%
\nwbegindocs{8}\nwdocspar

\nwenddocs{}

max_stars_repo_name: davidgarmire/sugar

max_issues_repo_name: davidgarmire/sugar

max_forks_repo_name: davidgarmire/sugar


text:
\chapter{The Meaning of Type-1 CDF Instances} \label{chap:type1}

Type-1 CDF instances differ from Type-0 CDF instances simply in that
they allow a new kind of fact: {\tt necessCond/2}.  To explain the
power and usefulness of this kind of fact, we first describe class
expressions, which arise from the field of description logic.

\section{Class Expressions and CDF Facts}

While Type-0 CDF Instances are useful in practice, they lack
expressiveness in certain situations, as the following example shows.

%--------------------------------------------------
\begin{example} \rm \label{ex:ce1}
Consider the following CDF fragment which defines conflicting
materials for the thread of a suture object, named {\tt
\oid{inconSuture}}, using the schema of Example~\ref{ex:maxAttr}.
%
{\small
\begin{tabbing}
foo\=foo\=foo\=foo\=foo\=foo\=foooo\=foooooooooooooooo\=\kill
\> {\tt isa(\oid{inconSuture},\cid{absorbableSuture}) }\\
\> {\tt isa(\oid{inconNeedle},\cid{absSutNeedle}) }\\
\> {\tt isa(\oid{inconThread},\cid{absSutThread}) }\\
\\
\> {\tt hasAttr(\oid{inconSuture},\rid{hasImmedPart},\oid{inconThread}) }\\
\> {\tt hasAttr(\oid{inconThread},\rid{hasMaterial},\cid{gut}) }\\
\> {\tt hasAttr(\oid{inconThread},\rid{hasMaterial},\cid{polyglyconate})}
\end{tabbing}
}
%
\noindent
It is easy to show that when the schema of Example~\ref{ex:maxAttr} is
extended with this fragment, it has a model.  Because the schema
contains the fact:
%
{\small
\begin{tabbing}
foo\=foo\=foo\=foo\=foo\=foo\=foooo\=foooooooooooooooo\=\kill
\> {\tt maxAttr(\cid{absSutPart},\rid{hasMaterial},\cid{absSutMaterial},1) }
\end{tabbing}
}
%
\noindent
the model contains an element that is in the class {\tt
\cid{polyglyconate}} as well as in the class {\tt \cid{gut}}.  However,
such a model is unintended, as gut and polyglyconate are separate
materials.
\end{example}
%--------------------------------------------------

In order to address such situations, classes and objects may be
defined in terms of {\em class expressions}.

\begin{definition} \label{def:ce} \index{class expressions}
\index{class expressions!inclusion statement}
Let $\cL$ be an ontology language.  A {\em CDF class expression} $C$
over $\cL$ is formed by one of the following constructions in which
$A$ is a class or object identifier $C_1$ and $C_2$ class expressions,
$R$ a relation identifier, and $n$ a natural number.
\begin{tabbing}
fo\=foo\=foo\=foo\=foooooooooooooooooooooooooooo\=ooooooooooooo\=\kill
\> $C \leftarrow A | not\ C_1 | C_1 , C_2 | C_1 ; C_2 |
			| all(R,C_1) | exists(R,C_1)
 			  | atLeast(n,R,C_1) | atMost(n,R,C_1)  $
\end{tabbing}
If $C_1$ and $C_2$ are class expressions, then $C_1 \subseteq C_2$ is
an {\em inclusion statement},
\end{definition}
Note that in the definition above, $A$ can be either an atomic or
product identifier. Also note that Prolog-style syntax is used: {\em
and} is represented as {\em ``,''} and {\em or}\  as {\em ``;''}.

The meaning of class expressions in terms of ontology theories will be
defined in \refsec{sec:cesemantics}.  For now, we informally
illustrate their meaning through a series of examples.

As their name implies, class expressions provide a means for
describing classes.  Intuitively, the $all$ constructor may seem to
have some correspondance to {\tt allAttr/3}, $exists$ to {\tt
hasAttr/3}, $atLeast$ to {\tt minAttr/4} and $atMost$ to {\tt
maxAttr/4}.  More precisely if the sorting predicates are ignored,
then
\begin{center}
{\tt allAttr(cid(source),rid(r),cid(target))}
\end{center}
\noindent
translates to an {\em inclusion statement}
 between class expressions.
\[
cid(source) \subseteq all(rid(r),cid(target))
\]
where the inclusion statement $C_1 \subseteq C_2$ is true in an
ontology structure if the set of elements denoted by $C_1$ is a subset
of the set of elements denoted by $C_2$.  The other Type-0 predicates
translate to inclusion statements in a similar manner.

%------------------------------------------
\begin{example} \label{ex:firstce} \rm
Let $C_1$ be the class expression:
%-------------
{\em {\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> \cid{absorbableSutures}, \\
\> all(\rid{hasNeedleDesign},\cid{needleDesign}), \\
\> all(\rid{hasPointStyle},\cid{pointStyle}), \\
\> \> 	exists(\rid{hasPointStyle},\cid{pointStyle}, \\
\> all(\rid{hasImmedPart},\cid{absSutPart}),  \\
\> \> 	exists(\rid{hasImmedPart},\cid{absSutNeedle}),  \\
\> \> 	exists(\rid{hasImmedPart},\cid{absSutThread})
\end{tabbing}
} }
%-------------
This class expression can be read in English as
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> ``The class of all
elements that are in {\tt \cid{absorbableSutures}} and \\
\> all of whose {\tt \rid{hasNeedleDesign}} relations are to elements in
the class {\tt \cid{needleDesign}} and \\
\> all of whose {\tt \rid{hasPointStyle}} relations are to elements in
the class {\tt \cid{pointStyle}} and \\
\> that has a {\tt \rid{hasPointStyle}} relation to an element in
the class {\tt \cid{pointStyle}} and \\
\> all of whose {\tt \rid{hasImmedPart}} relations are to elements in
the class {\tt \cid{absSutPart}} and \\
\> that has a {\tt \rid{hasPointStyle}} relation to an element in
the class {\tt \cid{absSutNeedle}} and \\
\> that has a {\tt \rid{hasPointStyle}} relation to an element in
the class {\tt \cid{absSutThread}}''.
\end{tabbing}
\noindent
Note that from our running example, the CDF facts that pertain to {\tt
absorbableSutures)} are:
%-------------
{\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> {\tt isa(\cid{absorbableSutures},\cid{sutures})}  \\
\> {\tt allAttr(\cid{absorbableSutures},\rid{hasNeedleDesign},\cid{needleDesign})} \\
\> {\tt allAttr(\cid{absorbableSutures},\rid{hasPointStyle},\cid{pointStyle}) } \\
\> \> {\tt hasAttr(\cid{absorbableSutures},\rid{hasPointStyle},\cid{pointStyle}) } \\
\> {\tt allAttr(\cid{absorbableSutures},\rid{hasImmedPart},\cid{absSutPart}) } \\
\> \> {\tt hasAttr(\cid{absorbableSutures},\rid{hasImmedPart},\cid{absSutNeedle}) } \\
\> \> {\tt hasAttr(\cid{absorbableSutures},\rid{hasImmedPart},\cid{absSutThread}) }
\end{tabbing}
}
\noindent
Other facts hold, but they are redundant
(Definition~\ref{def:redund}).  From these facts along with the
semantics given in Section~\ref{chap:type0}, it is not hard to see
that if an element $O$ is in the class {\tt \cid{absorbableSutures}}
then it must also be in $C$.
\end{example}
%------------------------------------------
From Definitions~\ref{def:ontolang} and~\ref{def:IdSort}, a CDF object
identifier denotes a class with a uniqueness constraint.  Because of
this, object identifiers and class identifiers can be intermingled
withing class expressions.

\begin{example} \rm \label{ex:type1cc}
Consider the object identifier {\tt \oid{inconSuture}}, introduced in
Example~\ref{ex:ce1}.  As {\tt \oid{inconSuture}} is a subclass of
{\tt \cid{absorbableSuture}}, the facts
%-------------
{\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> (1) \> {\tt isa(\oid{inconSuture},\cid{absorbableSuture}} \\
\> (2) \> {\tt allAttr(\oid{inconSuture},\rid{needleDesign},\cid{needleDesignType})}
\end{tabbing}
}
%-------------
\noindent
hold (cf. Example~\ref{ex:suture2}).  as does
%-------------
{\small
\begin{tabbing}
fooo\=fooo\=foo\=foo\=fooooooooooooooooooooooooooooooo\=oooooooo\=\kill
\> (3) \> {\tt allAttr(\oid{inconSuture},\rid{hasPointStyle},\cid{pointStyle}) } \\
\> (4) \>{\tt hasAttr(\oid{inconSuture},\rid{hasPointStyle},\cid{pointStyle}) }
\end{tabbing}
}
%-------------
\noindent
(cf. Example~\ref{ex:hasAttr}).  Furthermore, from Example~\ref{ex:maxAttr}
%-------------
{\small
\begin{tabbing}
foo\=fooo\=foo\=foo\=foo\=foo\=foooo\=foooooooooooooooo\=\kill
\> (5) \>{\tt allAttr(\oid{inconSuture},\rid{hasImmedPart},\cid{absSutPart}) } \\
\> (6) \>{\tt hasAttr(\oid{inconSuture},\rid{hasImmedPart},\cid{absSutNeedle}) }
\end{tabbing}
}
%-------------
\noindent
all hold, along with
%-------------
{\small
\begin{tabbing}
foo\=fooo\=foo\=foo\=foo\=foo\=foooo\=foooooooooooooooo\=\kill
\> (7) \> {\tt hasAttr(\oid{inconSuture},\rid{hasImmedPart},\oid{inconThread}) }
\end{tabbing}
}
\noindent
It is not hard to convince yourself that these facts imply that the
{\tt \oid{inconSuture}} belongs to the class $C_2$ described by
%-------------
{\em {\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> \oid{inconSuture}, \cid{absorbableSutures}, \\
\> all(\rid{hasneedleDesign},\cid{needleDesign}),  \\
\> all(\rid{hasPointStyle},\cid{pointStyle}), \\
	exists(\rid{hasPointStyle},\cid{pointStyle}), \\
\> all(\rid{hasImmedPart},\cid{absSutPart}),  \\
\> \> 	exists(\rid{hasImmedPart},\cid{absSutNeedle}),  \\
\> \> 	exists(\rid{hasImmedPart},\oid{inconThread})
\end{tabbing}
} }
%--------------
\noindent
Note that $C_2$ is similar to $C_1$, except that the object
identifiers imply that {\tt \cid{inconNeedle}} and {\tt
\cid{inconThread}} contain one and only one element.
\end{example}

%---------------------------------------------------------------------
\subsection{Class Expressions and Ontology Theories} \label{sec:cesemantics}
%---------------------------------------------------------------------

Class expressions can be formally translated into the ontology
languages of Definition~\ref{def:ontolang} using the following
definition from~\cite{Swif04} (see, e.g. \cite{CGLN02} for a general
exposition of class expressions).

%--------------------------------------
\begin{definition} \label{def:fot}
Let $C$ a CDF class expression, over an ontology language $\cL$ in
which the variables are denoted as $X_i$, for positive integers $i$.
Then the translation of $C$, $C[X_0]^{\cI}$, is a first-order formula
defined by the following rules, which use a global variable number,
$vnum$ that is initialized to 1 at the start of the transformation.

\begin{itemize}
\item if $C = A$ and  $A$ is an object identifier, then  $C[X_N]^{\cI} =
  elt(X_N,A) \wedge \forall X_{vnum} [elt(X_{vnum},A) \Ra X_N = X_{vnum}]$,
	where $vnum$ is incremented before the next step of the translation.
%
\item if $C = A$ and  $A$ is a class identifier, then  $C[X_N]^{\cI} =
		elt(X_N,A)$.
%
%
\item if $C = (C_1 , C_2)$, then $C[X_N]^{\cI} =
		C_1[X_N]^{\cI} \wedge C_2[X_N]^{\cI}$.
%
\item if $C = (C_1 ; C_2)$, then $C[X_N]^{\cI} =
		C_1[X_N]^{\cI} \vee C_2[X_N]^{\cI}$.
%
\item if $C = not\ C_1$, then $C[X_N]^{\cI} = \neg C_1[X_N]^{\cI}$.
%
\item if $C = exists(R,C_1)$, then $C[X_N]^{\cI} =
		\exists X_{vnum}. rel(X_N,R,X_{vnum}) \wedge
		C_1[X_{vnum}]^{\cI}$, where $vnum$ is
			incremented before the	next step of the translation.
%
\item if $C = all(R,C_1)$, then $C[X_N]^{\cI} =
	\forall X_{vnum}. rel(X_N,R,X_{vnum}) \Ra C[X_{vnum}]^{\cI}$,
	where $vnum$ is incremented before the next step of the translation.
%

\item if $C = atLeast(m,R,C_1)$, then $C[X_N]^{\cI} =
\exists^{\geq m} X_{vnum} [rel(X_N,R,X_{vnum}) \wedge C[X_{vnum}]^{\cI}]
$
where $vnum$ is incremented $m$ times before the next steps of the
translation.
%
\item if $C  = atMost(m,R,C_1)$, then
	$C[X_N]^{\cI} = \neg atLeast(m+1,R,C_1)[X_N]^{\cI}$

\end{itemize}
If $C_1 \subseteq C_2$ is an inclusion statement, its tranlation is
$
(\forall X_0) [ C_1[X_0]^{\cI} \Ra C_2[X_0]^{\cI} ]
$
\end{definition}

\begin{example} \rm
If $C_1$ is the class expression from Example~\ref{ex:type1cc}, then
$C_1[X_0] = $
{\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> $elt(X_0,cid(absorbableSutures)) \wedge (\forall X_1)
	[elt(X_1,oid(absorbableSutures)) \Ra X_0 = X_1]$ \\
\> $(\forall X_2) [rel(X_0,rid(hasNeedleDesign),X_2) \Ra
			elt(X_2,cid(needleDesign))] \wedge $ \\
\> $(\forall X_3) [rel(X_0,rid(hasPointStyle),X_3) \Ra
			elt(X_3,cid(pointStyle))] \wedge $ \\
\> \> $(\exists X_4) [rel(X_0,rid(hasPointStyle),X_4) \wedge
			elt(X_4,cid(pointStyle))] \wedge $ \\
\> $(\forall X_5) [rel(X_0,rid(hasImmedPart),X_5) \Ra
			elt(X_5,cid(absSutPart))] \wedge $ \\
\> \> $(\exists X_6) [rel(X_0,rid(hasImmedPart),X_6) \wedge
			elt(X_6,cid(absSutNeedle))] \wedge $ \\
\> \> $(\exists X_7) [rel(X_0,rid(hasImmedPart),X_7) \wedge
			elt(X_7,oid(inconThread)) \wedge $ \\
\> \> \> \> $	(\forall X_8) [elt(X_8,oid(inconThread)) \Ra X_7 = X_8]] $
\end{tabbing}
}
\end{example}

To summarize this section, CDF instances have direct translations into
ontology theories, as presented in Chapter~\ref{chap:type0}.  Class
expressions can also be translated into ontology theories via
Definition~\ref{def:fot}, and these two translations induce a unique
translation from CDF instances to inclusion statements between class
expressions.  Thus a CDF instance can be seen as a set of sentences in
an ontology theory, or as a set of inclusion statements between class
expressions.  At the same time, there are class expresion constructors
that are not used when Type-0 instances are translated into class
expressions, namely {\em ``;''} and {\em not}.  Arbitrary class
expressions are denoted by stating necessary conditions, to which we
now turn.

%------------------------------------------
\section{Necessary Conditions} \index{predicates!necessCond/2}

The unintended model of Example~\ref{ex:ce1} can be prevented by
stating that a necessary condition for an object to be in {\tt
\cid{gut}} is that the object not be in {\tt \cid{polyglyconate}}.  This
is handled by a new type of fact {\tt necessCond/2} that is used to
state necessary conditions.

%--------------------
\begin{example} \rm  \label{ex:nc1}
Adding the fact

{\tt necessCond(cid(gut),vid(not(cid(polyglyconate)))). }

denotes that no element of {\tt cid(gut)} can be in {\tt
cid(polyglyconate)}.
\end{example}
%--------------------

\index{identifiers!virtual}
Type-1 CDF instances thus have a new kind of identifier: a {\em
virtual identifier}, denoted by the functor {\tt vid/1}.  A virtual
identifier indicates that rather than denoting a class by its name, it
is denoted by a class expression whose syntax is given in
Definition~\ref{def:ce}, and whose meaning is given by the translation
of Definition~\ref{def:fot}.

\begin{instance} [Translation of {\tt necessCond/2}] \rm
For each fact of the form {\tt necessCond(Cid,Vid)} add the axiom
\ \\
\begin{tabbing}
foo\=foo\=foo\=foo\=foo\=foo\=foooo\=foooooooooooooooo\=\kill
\> $ isClass(Cid) \wedge
	(\forall X) [elt(X,Cid) \Rightarrow Vid[X]^{\cI}]$
\end{tabbing}
denoted as {\tt necessCond(Cid,Vid)}$^{\cI}$.
\end{instance}

\begin{example} \rm
The translation of the fact from Example~\ref{ex:nc1} is the axiom
\[
isClass(\cid{gut}) \wedge (\forall X_0) [elt(X_0,\cid{gut}) \Ra
					\neg elt(X_0,\cid{polyglyconate})]
\]
It is easy to see that an instance containing this fact and those of
Example~\ref{ex:ce1}, combined with the Schema of
Example~\ref{ex:maxAttr} will not have a model.  Note that
Axiom~\ref{ax:nonnull} (Non-Empty Classes) is essential to deriving
this inconsistency.
\end{example}

The following proposition is straightforward.

\begin{proposition}[First Argument Inheritance Propagation
						for {\tt necessCond/2}]
\label{prop:necesscondinh}\rm
Let $\cM$ be an ontology model.
\begin{enumerate}
\item If $\cM \models {\tt necessCond(Id_1,Id_2)}^{\cI} \wedge
						{\tt isa(Id_0,Id_1)}^{\cI}$
	then $\cM \models  {\tt necessCond(Id_0,Id_2)}^{\cI}$
\end{enumerate}
\end{proposition}

The {\sc inh} proof system can be extended to use a deduction rule
based on this proposition, in a straightforward way.

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

\section{Local Class Expressions} \label{sec:lce}

When translating information in a CDF instance directly to a class
expression, a difficulty can arise.  In the examples~\ref{ex:firstce}
and~\ref{ex:type1cc} class identifiers within the {\em all}, {\em
exists}, {\em atLeast} and {\em atMost} constructors can be considered
``primitive'' in the sense that these class identifiers do not occur
as the first argument of any {\tt allAttr/3}, {\tt hasAttr/3}, {\tt
minAttr/4} or {\tt maxAttr/4} predicates.  However, it is not always
the case that only primitive classes occur in these positions.

\begin{example} \rm
Consider the following schema for family relations, adapted from
~\cite{BaNu03}.
%
{\tt {\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> isa\_ext(cid(gender),cid('CDF Classes')). \\
\>   isa\_ext(cid(female),cid(gender)). \\
\>   isa\_ext(cid(male),cid(gender)). \\
\\
\> isa\_ext(cid(person),cid('CDF Classes')). \\
\> \> allAttr\_ext(cid(person),rid(hasBrother),cid(man)). \\
\> \> allAttr\_ext(cid(person),rid(hasSister),cid(woman)). \\
\\
\>   isa\_ext(cid(woman),cid(person)). \\
\> \>   isa\_ext(cid(woman),cid(female)). \\
\>   isa\_ext(cid(man),cid(person)). \\
%
%  necessCond\_ext(cid(man),vid(not(cid(woman)))).
\end{tabbing}
} }
The class expression for {\tt cid(person)} is
{\em {\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> cid('CDF Classes'), \\
\> all(rid(hasBrother),cid(man)), \\
\> all(rid(hasSister),cid(woman))
\end{tabbing}
} }
while the class expression for {\tt cid(man)} is
{\em {\small
\begin{tabbing}
fooo\=foooo\=foo\=foo\=foooooooooooooooooooooooooooo\=oooooooooo\=\kill
\> cid(person), \\
\> all(rid(hasBrother),cid(man)), \\
\> all(rid(hasSister),cid(woman))
\end{tabbing}
} }
\end{example}
In the above example, a class expression for {\tt cid(person)}
contains subclasses of {\tt cid(person)}, while a class expression for
{\tt cid(man)} contains the class {\tt cid(man)} itself.  A CDF
instance can be seen as a type of {\em termonology system}, (sometimes
called a TBox in the literature).  CDF classes and objects are defined
in terms of other classes and objects that may themselves be defined
in terms of classes and objects.  If a terminology system has a class
identifier that is defined in terms of itself, it is sometimes called
{\em cyclic}, otherwise the terminology system is {\em acyclic}.  As
the previous example shows, many of the most natural terminology
systems are cyclic.

\index{class expressions!local}
At this point, it is useful to introduce some ``terminology'' of our
own, at a somewhat informal level.  Given a class or object identifier
$C$ in a CDF instance $\cO$, a {\em level 1 local class expression}
for $C$ is formed by cojoining all principle classes for $C$ along
with translations of non-isa facts for $C$ (i.e. {\tt hasAttr/3} into
an $exists$ constructor, {\tt allAttr/3} into an $all$ constructor,
etc.)  A {\em level n local class expression} for $C$ is then defined
as follows.  We start with an empty {\em ancestorList}, and construct
a level 1 local class expression, $CE$ for $C$.  Next we add $C$ to
the {\em ancestor list}, and construct a level $n-1$ class expression
for each identifier in $CE$ that is not in the ancestor list.
Intuitively, constructing a level $n$ local class expression
``unfolds'' or ``expands'' class expressions and identifiers $n$
times, ignoring cycles.

The concept of local class expressions is used to explain features of
the Type-1 CDF interface, as descrined in
Section~\ref{sec:type1query}.