summary.tex

\begin{filecontents*}{summary.bib}
@ARTICLE{Thanei2016-wf,
	title         = "The xyz algorithm for fast interaction search in
	high-dimensional data",
	author        = "Thanei, Gian-Andrea and Meinshausen, Nicolai and Shah, Rajen
	D",
	abstract      = "When performing regression on a dataset with $p$ variables,
	it is often of interest to go beyond using main linear
	effects and include interactions as products between
	individual variables. For small-scale problems, these
	interactions can be computed explicitly but this leads to a
	computational complexity of at least $\mathcal\{O\}(p^2)$ if
	done naively. This cost can be prohibitive if $p$ is very
	large. We introduce a new randomised algorithm that is able
	to discover interactions with high probability and under
	mild conditions has a runtime that is subquadratic in $p$.
	We show that strong interactions can be discovered in almost
	linear time, whilst finding weaker interactions requires
	$\mathcal\{O\}(p^\alpha)$ operations for $1 < \alpha < 2$
	depending on their strength. The underlying idea is to
	transform interaction search into a closestpair problem
	which can be solved efficiently in subquadratic time. The
	algorithm is called $\mathit\{xyz\}$ and is implemented in
	the language R. We demonstrate its efficiency for
	application to genome-wide association studies, where more
	than $10^\{11\}$ interactions can be screened in under $280$
	seconds with a single-core $1.2$ GHz CPU.",
	month         =  oct,
	year          =  2016,
	archivePrefix = "arXiv",
	primaryClass  = "stat.ML",
	original_id   = "e4d8125b-1093-0fb9-a9a5-244e8c45f1cd",
	eprint        = "1610.05108"
}
\end{filecontents*}

\documentclass{article}

\usepackage[colorinlistoftodos]{todonotes}
\usepackage{amsmath}
%\usepackage{float}

\begin{document}

\listoftodos
\clearpage

\section{Data Generation}
%\begin{quotation}
We simulated siRNA–gene perturbation matrices based on four
commercially available genome–wide libraries for 20,822 human genes from Qiagen with an overall size of 90,000 siRNAs. First, we predicted sequence dependent off-targets using TargetScan [23] for each siRNA as described in [13]. We thresholded all predictions to be 1 if
larger than zero and 0 otherwise
\todo{from old main.tex, this is presumably Q1\_binary, which hasn't changed. Not sure who wrote this.}
to produce the matrix $Q$.
%\end{quotation}

% X
\subsection{Perturbation matrix}
$n$ siRNAs and $p$ genes were sampled from $Q$ without replacement to form $X$. We simulated and analysed a small ($n = 1000,\ p=100$), and large ($n = 10000,\ p=1000$) matrix.

% interactions (& lethals)
\subsection{Interactions}
We chose $i \in \{5, 20, 50, 100\}$ distinct pairs of genes at random, from those that occur together at least once in some row of $X$, to be interacting pairs. The strength of their interactions was sampled from Norm(0,2).\todo{note on log scale?}

For testing xyz's ability to find synthetic lethal pairs, $l \in \{0, 10,20,50,100\}$ additional interactions were added in the same fashion, with strengths of -1000.\footnote{Since the data is generated on a log scale, a fitness value of exactly 0 cannot be represented. Any row in which these interactions occurred, however, would have at most $\frac{1}{2^{1000}} \approx 0$ of the population survive each generation.}


% main effects
\subsection{Main effects}
For each gene present in an non-lethal interaction effect, a main effect strength was sampled from Norm(0,1). In the cases were no lethal pairs were added, this produces a strong hierarchy. While xyz does not require a strong hierarchy, having one improves performance.\cite{Thanei2016-wf}
\todo{(and also because it was part of the glinternet simulation)}
\todo{Since the performance on random interactions was quite poor, it seemed reasonable to leave this in. For the synthetic lethal test (which seemed to be the one where this mattered most), no main interactions were added.}

% fitness
\subsection{Fitness and Noise}
For every row $X_i$, the initial fitness value $Y_i$ is the sum of the main, interaction, and lethal effect strengths present in it's row.

% noise
For signal to noise ratios $SNR \in \{2,5,10\}$, noise was sampled from Norm(0,1) and added to $Y$ as $Y \leftarrow Y + \sqrt{\frac{var(Y)}{SNR \times var(noise)}} * noise$.

% Test
\subsection{Significance test}
%It's probably best to refer to the original main.tex significance section here, the test hasn't changed. Long story short, $p > 0.05$ using chi-squared, which may or may not be appropriate.
We tested whether the estimated interactions strength was significantly $> 0$ using the chi-squared test, adjusted using the Benjamini \& Hochberg procedure. For each performance measure, we used both the complete set of interactions returned by xyz, and those that significantly deviated from 0, with a q-value $< 0.05$.
~\\
\todo[inline]{This may or may not have been the appropriate test for xyz.}

\begin{quotation}
	(original glinternet version):\\
	In classical linear regression analysis, the significance of the $j$th predictor is tested by comparing the two nested models with with fixed subsets of predictors $M$ and $M \cup \{j\}$ using the chi-squared test. However, if the two sets of predictors $M$ and $M \cup \{j\}$ are not fixed, as is the case for any greedy or adaptive procedure such as the lasso, the use of the $\chi^2_1$ null distribution is too liberal. Lockhart et al. suggest the \emph{covariance test statistic} $T_k$ for the lasso which, under reasonable assumptions on $\vec{X}$, is asymptotically distributed as $\operatorname{Exp}(1)$~\cite{Lockhart:2013hm}. Due to the overlap of coefficients in the overlapped group lasso, it is however unclear if the proposed test is applicable to our model. Therefore, we resort to the classical chi-squared test, well aware of the inflation of type I error. We correct p-values for multiple testing using the procedure by Benjamini and Hochberg and reject at the level of $\alpha = 0.05$.
\end{quotation}

\subsection{xyz}
For every combination of parameters, ten simulations were run.
We used \verb|xyz_regression| to find interactions, with a regression value of 0.9, and, except where specifically testing the effect of different values of L, $L = \sqrt{p}$ projections, to focus on the strong interactions\cite{Thanei2016-wf}.

\section{Evaluation}

% precision, recall F1
We primarily evaluated xyz's ability to propose interacting pairs, rather than its ability to estimate interaction strengths. To that end, we measured the number true positives (TP), false positives (FP), and false negatives (FN) in each run, and compared the following performance measures:

$$\textnormal{Precision} = \frac{TP}{TP + FP}$$
$$\textnormal{Recall} = \frac{TP}{TP + FN}$$
$$\textnormal{F1} = 2 \times \frac{\textnormal{Precision} \times \textnormal{Recall}}{\textnormal{Precision} + \textnormal{Recall}}$$
To avoid misleading graphs, where only high values were present, F1 values were set to $0$ when both precision and recall were 0.

~\\
The following aspects of xyz's performance were evaluated:
%\subsection{PrecRecF1}

\begin{figure}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n1000_tno_large0_"}%
		\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n1000_tyes_large0_"}
	\end{minipage}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n10000_tno_large1_"}%
		\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n10000_tyes_large1_"}
	\end{minipage}
	\caption{Precision, recall, and F1 performance measures for varying numbers of interactions, additional main effects, and signal to noise ratios.}
\end{figure}




%\subsection{PrecRecF1\_lethal}
\begin{figure}
\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n10000_tno_large0_lethalTRUE_lethal"}%
	\includegraphics[width=0.5\linewidth]{"output/PrecRecF1_n10000_tno_large0_lethalTRUE_lethal"}
\end{minipage}
\caption{Precision, recall, and F1 performance for varying numbers of synthetic lethal pairs, with additional background interactions. This was the only comparison for which lethal interactions were added. Neither side of the lethal interactions were used as main effects, and as far as lethal interactions are concerned, there is no hierarchy present.}
\end{figure}
%\subsection{l\_diff}


\begin{figure}
	\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/l_diff_n10000_SNR5_tno"}%
	\includegraphics[width=0.5\linewidth]{"output/l_diff_n10000_SNR5_tyes"}
\end{minipage}
\caption{Precision, recall, and F1 as a result of increasing the number of projections. This was run entirely on $p = 1000$ genes with a signal to noise ratio of five.}
\end{figure}

\begin{figure}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/quant_analysis_n10000"}
	\end{minipage}
	\caption{True positives and false positives as a result of increasing the number of projections. This was run entirely on $p = 1000$ genes with a signal to noise ratio of five.}
\end{figure}


\todo{slightly misleading scale, but I wanted TP to actually be visible.}

%\subsection{FXstrength}


\begin{figure}
	\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/FXstrength_PRF_n1000_tno_mult1_"}%
	\includegraphics[width=0.5\linewidth]{"output/FXstrength_PRF_n1000_tyes_mult1_"}
\end{minipage}
\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/FXstrength_PRF_n10000_tno_mult10_"}%
	\includegraphics[width=0.5\linewidth]{"output/FXstrength_PRF_n10000_tyes_mult10_"}
\end{minipage}

\caption{Precision, recall, and F1 performance for effects of difference strengths, with varying numbers of interactions. This was run on both $n = 1,000$, $p = 100$ and $n = 10,000$, $p = 1,000$.	
}
\end{figure}

\begin{figure}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/FXstrength_direction_n1000_tno_mult1_"}%
		\centering
		\includegraphics[width=0.5\linewidth]{"output/FXstrength_direction_n1000_tyes_mult1_"}
	\end{minipage}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/FXstrength_direction_n10000_tno_mult10_"}%
		\centering
		\includegraphics[width=0.5\linewidth]{"output/FXstrength_direction_n10000_tyes_mult10_"}
	\end{minipage}
	\caption{The proportion of effect strength estimates with the correct sign was also compared for both sizes. Above: $p = 100$, below: $p = 1000$.}
\end{figure}


%\subsection{NumObservations}


\begin{figure}
	\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/NumObservations_n1000_tno"}%
	\includegraphics[width=0.5\linewidth]{"output/NumObservations_n1000_tyes"}
\end{minipage}
\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/NumObservations_n10000_tno"}%
	\includegraphics[width=0.5\linewidth]{"output/NumObservations_n10000_tyes"}
\end{minipage}
\caption{Precision, recall, and F1 performance measures compared to the number of times each interaction was observed. The number of main effects was fixed to 20 when $p=100$ (above), and 200 when $p=1000$ (below).}
\end{figure}

\begin{figure}
	\begin{minipage}{\linewidth}
		\centering
		\includegraphics[width=0.5\linewidth]{"output/NumObservations_n1000_percGenes"}%
		\includegraphics[width=0.5\linewidth]{"output/NumObservations_n10000_percGenes"}
	\end{minipage}
	\caption{Number of observations of double knockdown for $p = 100$ (left) and $p = 1000$ (right).\todo[inline]{check parameters}}
\end{figure}


%\subsection{FXdiff}


\begin{figure}
	\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/FXdiff_n1000_tno"}%
	\includegraphics[width=0.5\linewidth]{"output/FXdiff_n1000_tyes"}
\end{minipage}
\begin{minipage}{\linewidth}
	\centering
	\includegraphics[width=0.5\linewidth]{"output/FXdiff_n10000_tno"}%
	\includegraphics[width=0.5\linewidth]{"output/FXdiff_n10000_tyes"}
\end{minipage}
\caption{The proportion of effect strength estimates with the correct sign compared to the number of times the interaction was observed.}
\end{figure}



\bibliography{summary.bib}
\bibliographystyle{plain}

\end{document}