\documentclass[english]{beamer}
%\usetheme{Warsaw}

\usepackage{psfrag}
\usepackage{epsf}
\usepackage{epsfig}


% Setup appearance:
\usetheme{Boadilla}
\usecolortheme{purdue}
\setbeamercovered{transparent}
\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}

\newcommand{\pCoDO}{p_{CoDO}}

\newcommand{\A}{\bs{\mathcal{A}}}
\newcommand{\x}{\bs{x}}
\newcommand{\e}{\bs{e}}
\newcommand{\PI}{\bs{\pi}}
\newcommand{\one}{\bs{1}}
\newcommand{\eg}{{\sl e.g.}}
\newcommand{\ie}{{\sl i.e.}}



\newcommand{\R}{\bs{\mathcal{R}}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\E}{\mathcal{E}}

\newcommand{\Square}{\bs{\mathcal{S}}}
\newcommand{\Overlap}{\bs{\mathcal{O}}}
\newcommand{\Weight}{\bs{\mathcal{W}}}
\newcommand{\w}{\bs{w}}




\usepackage{amstext,amsmath,amssymb,amsfonts}
\usepackage{algorithmic,algorithm}
\usepackage{mathtools,cuted}
\usepackage{subfigure}
\usepackage{url}
\usepackage{listings}


\usepackage{enumitem}
\setenumerate[1]{label=\protect\usebeamerfont{enumerate item}%
        \protect\usebeamercolor[fg]{enumerate item}%
        \insertenumlabel.}
\setitemize{label=\usebeamerfont*{itemize item}%
  \usebeamercolor[fg]{itemize item}
  \usebeamertemplate{itemize item}}        



\DeclareMathOperator*{\argmin}{\arg\!\min}
\DeclareMathOperator*{\argmax}{\arg\!\max}
\newcommand{\bs}[1]{\boldsymbol{#1}}

\newcommand{\Vector}[1]{\bs{#1}}
\DeclareMathAlphabet\mathbfcal{OMS}{cmsy}{b}{n}
\newcommand{\Matrix}[1]{\mathbf{#1}}
\newcommand{\Tensor}[1]{\mathbf{\mathcal{#1}}}

\newcommand{\Graph}[1]{\mathit{\mathbf{\bs{#1}}}}
\newcommand{\Set}[1]{\mathit{#1}}


\newcommand{\diag}{\boldsymbol{diag}}

\newcommand{\Loss}{\bs{\mathcal{L}}}
\newcommand{\Reg}{\bs{\mathcal{R}}}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\newcommand{\Ind}{ \mathds{1} }

\newcommand\distrib{ {\sim} }   % "Distributed as".
\newcommand{\N}{\mathbb{N}}
\newcommand\lintersect{ {\cap} }
\newcommand\intersect{\bigcap}
\newcommand\lunion{ {\cup}}
\newcommand\union{{\bigcup}}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
%\newcommand\min{\mathrm{min}}
%\newcommand\max{\mathrm{max}}


%\newcommand{\Vector}[1]{\bs{#1}}
%\DeclareMathAlphabet\mathbfcal{OMS}{cmsy}{b}{n}
%\newcommand{\Matrix}[1]{\mathbf{#1}}
%\newcommand{\Tensor}[1]{\mathbf{\mathcal{#1}}}

%\newcommand{\Graph}[1]{\mathit{\mathbf{\bs{#1}}}}
%\newcommand{\Set}[1]{\mathit{#1}}


\newcommand{\Bernoulli}{\mathrm{Bernoulli}}
\newcommand{\Binomial}{\mathrm{Binomial}}
\newcommand{\Hypergeometric}{\mathrm{Hypergeometric}}

\newcommand{\var}[1]{#1}
\newcommand{\rvar}[1]{\uppercase{#1}}
\newcommand{\dens}{\delta}



\title[Analytical Modeling] % (optional, use only with long paper titles)
{Role of Analytical and Statistical Modeling in Data Analytics}




\author[A. Grama] % (optional, use only with lots of authors)
{Ananth Grama}

\institute[Purdue] % (optional, but mostly needed)
{
  Center for Science of Information, and \\
  Department of Computer Science\\
  Purdue University \\ \vspace*{1.0in}
  With lots of help from Shahin Mohammadi, Abram Magner, Mehmet Koyuturk.

}

\date[] % (optional, should be abbreviation of conference name)
{July, 2016}



\pgfdeclareimage[height=0.5cm]{university-logo}{figures/purdue}
\logo{\pgfuseimage{university-logo}}


\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

%\beamerdefaultoverlayspecification{<+->}


\begin{document}


\begin{frame}
  \titlepage
\end{frame}



\begin{frame}{Outline}
  \tableofcontents
\end{frame}

\section{Background}

\subsection{Basic Concepts}

\begin{frame}{Basic Concepts}

\begin{itemize}
\item
$p$-Value: the probability of obtaining at least as extreme results given that
the null hypothesis is true. Stated otherwise, this is the probability that
a random selection (null hypothesis) yields an observation as extreme or more.

Example: We have 30 people in this room. All 30 of you are under 40 years of age.
The $p$-value of this observation is the probability that a randomly drawn sample
of 30 people from the general population only contains people who are no more than
40 years old. {\em The lower this probability, the more surprising is the observation.}

\item
Statistical Signifiance: is attained when a $p$-value is less than a
prescribed significance level.

\item
Statistical significance is typically used for hypothesis testing. However, we use
this to estimate the ``surprisingness'' of observations.


\end{itemize}
\end{frame}


\subsection{Motivating Examples}

\begin{frame}{Motivation: Some Examples : Classifiers}

\textbf{Can I predict the Coffee Drinkers -- a classification problem?}


If I build a classifier with 90\% precision and 90\% recall, would you be happy?
\end{frame}

\begin{frame}{Motivation: Some Examples}

\textbf{Can I predict the Coffee Drinkers -- a classification problem?}

If I build a classifier with 90\% precision and 90\% recall, would you be happy?
\vspace*{0.5in}

What if I now told you that 90\% of all people are coffee drinkers -- the Null Hypothesis!!
\end{frame}

\begin{frame}{Motivation: Some Examples}

\textbf{Can I predict the Coffee Drinkers -- a classification problem?}

If I build a classifier with 90\% precision and 90\% recall, would you be happy?
\vspace*{0.2in}

What if I now told you that 90\% of all people are coffee drinkers -- the Null Hypothesis!!
\vspace*{0.2in}

In the context of the null hypothesis, a classifier with 90\% precision and 90\% recall has no
statistical significance at all!!
\end{frame}


\begin{frame}{Motivation: Some Examples: Associations}

\textbf{How can I infer rules of the kind: P(Bread) $\rightarrow$ P(Butter)? That is, people
who buy bread are also likely to buy butter.}
\vspace*{0.2in}

The association rule mining algorithm works in two steps -- in the first step, all
frequent sets are identified, and in the second step, the conditional probability for
these frequent sets is computed to identify association rules.
\vspace*{0.2in}

Frequent sets are themselves computed using downward closure -- all subsets of frequent
subsets must themselves be frequent.

\end{frame}

\begin{frame}{Motivation: Some Examples: Associations}


\begin{itemize}
\item
In reality, it does not work the way it should -- the method mostly identifies things
that are obvious -- nothing interesting. 

\item
This is because frequency is a poor measure of statistical significance (if at all).

\item
Even for the simplest priors (all items purchase probabilities are i.i.d), frequent
sets are not ``statistically significant sets''.
\end{itemize}

\end{frame}

\begin{frame}{Motivation: Some Examples: Clustering}

\begin{center}
\textbf{I run a set of uniformly distributed points through a standard clustering
algorithm, say, $k$-means. What happens?}

I get a set of completely meaningless clusters! Should I be impressed?

How do I find the significance of a given set of clusters under a prior?

\end{center}
\end{frame}


\begin{frame}{Motivation: Some more questions to ponder.}

\begin{itemize}
\item
You run a graph clustering algorithm on facebook and you find a group of 300 people who are
(almost) completely connected. Should you be excited?

\item
70\% of your friends on Facebook are male, 60\% of your friends are computer scientists,
and 80\% of your friends are Indian. Do these numbers (and their overlaps) tell you anything?

\item
75\% of everyone's friends on Facebook live within 50 miles of them. Can I use distance as an
indicator of friendship (topology completion)?

\item
Can I trace the flow of a contagion through a network (its lineage), in the form of a
directed acyclic graph?

\end{itemize}
\end{frame}



\begin{frame}{Motivation: Most probable explanations.}

\begin{itemize}
\item
In each of the questions above, I am looking for ``surprisingness'' of observations. In
other words, I am trying to find observations that minimize the $p$-value.
\item
In yet another class of problems, we can look to maximize the probability, with respect to
a prior:
\begin{itemize}
\item
Given a dynamic network (say the spread of an infection), who was patient 0?
\item
Who was the first person on facebook?
\end{itemize}
\item
In each of these questions, we are looking for the explanation most consistent with our
understanding of driving processes (priors). These maximize probability w.r.t. the prior.
\end{itemize}

\end{frame}

\subsection{Analytical Frameworks}

\begin{frame}{What kinds of answers are we looking for?}

When posed with an optimization problem (or an analytics problem) we can look for different
kinds of answers:
\begin{itemize}
\item
The optimal solution (as defined by a suitable optimization problem). This solution is typically
infeasible at scale, and often, an overkill, because of noise and missing data.
\item
The obvious solution. This solution is the one that you get from most analytics algorithms. However,
this is rarely useful.
\item
The most statistically significant solution. This is similar to the optimal solution. It is generally
infeasible at scale, but if feasible, it is typically the most desirable.
\item
Any solution with high statistical significance. This trades off feasibility and utility. In most
cases, this is the solution of choice.
\item
The most probable solution. Generally computationally infeasible, however, proofs of near-optimality
are feasible.
\end{itemize}


\end{frame}


\begin{frame}{How do we develop solutions?}

\begin{itemize}
\item
Minimize statistical significance explicitly (i.e., use minimum $p$-value as an optimization
criteria). This is generally hard to formulate, and even harder to realize in an efficient
algorithm.
\item
Separate the algorithm from the quantification of $p$-values. Design heuristic algorithms and 
show that the results are statistically significant.
\end{itemize}

\end{frame}


\begin{frame}{Formulating and computing $p$-values?}

\begin{itemize}
\item
A $p$-value for an observation can be formulated in different ways. For example, when formulating
a $p$-value for the facebook dense subgraph example, we can ignore the graph and simply look at the
hypergeometric $p$-value (probability of $k$ successes in $n$ trials, drawn from a sample of $N$ objects
without replacement).
\item
Desirable formulations of $p$-values provide discriminating power.
\item
Defining suitable priors are critical for $p$ values. A prior that is very distant from the data
will lead to very low $p$-values for all observations. This is not useful.
\item
Priors may themselves be non-parametric.
\item
$p$-values may be analytical (often very hard to derive), or empirical (often expensive to compute
because of number of trials required).
\end{itemize}

\end{frame}


\section{Analytics in Action}


\subsection{Statistical Significance of Clusters}

\begin{frame}

\begin{center}

You run a graph clustering algorithm on facebook and you find a group of 300 people who are
(almost) completely connected. Should you be excited?

\end{center}

\end{frame}


\begin{frame}{Analytical Assessment of Statistical Significance of Clusters}

\begin{itemize}

\item{What is the significance of a dense component in a network?}

\item{What is the significance of a conserved component in multiple networks?}

\end{itemize}

\end{frame}

\begin{frame}{Random Graph Models}

\begin{itemize}

\item Interaction networks generally exhibit power-law property (or
exponential, geometric, etc.)
\item Analysis simplified through independence assumption 
\item Independence assumption may cause problems for networks with
arbitrary degree distribution
\item $P(uv \in E) = d_ud_v/|E|$, where $d_u$ is expected degree
of $u$, but generally $d_{\max}^2 > |E|$ for PPI networks

\item Rigorous analysis on $G(n,p)$ model
 \item Extension to piecewise $G(n,p)$ to capture network characteristics
       more accurately
\end{itemize}

\end{frame}

\begin{frame}{Significance of Dense Subgraphs}
\begin{itemize}
\item

A subgraph of $r$ nodes is said to be $\rho$-dense if
$F(r) \geq \rho r^2$, where $F(r)$ is the number of interactions
between these $r$ nodes 

\item{What is the expected size of the largest
$\rho$-dense subgraph in a random graph?} {\item Any
$\rho$-dense subgraph with larger size is
statistically significant!}

\end{itemize}

\end{frame}



\begin{frame}{Significance of Dense Subgraphs}
\begin{itemize}

\item
{$G(n,p)$ model}
\begin{itemize}
\item $n$ nodes, each interaction occurs with probability $p$
\item Simple enough to facilitate rigorous analysis
\item If we let $p=d_{\max}/n$, largest $\rho$-dense subgraph in $G(n,p)$
stochastically dominates that in a graph with arbitrary
degree distribution 
\end{itemize}

\item{Piecewise $G(n,p)$ model}

\begin{itemize}
\item Few nodes with many interacting partners, many nodes with few interacting
partners
\item Captures the basic characteristics of many networks
\item Analysis of $G(n,p)$ model generalizes to this model
\end{itemize}

\end{itemize}

\end{frame}

\begin{frame}{Largest Dense Subgraph}

\begin{itemize}
\item
Theorem:
If $G$ is a random graph with $n$ nodes, where every edge exists
with probability $p$, then
\begin{equation}
~~~~~~~~~~~~~\lim_{n\rightarrow \infty} \frac{R_{\rho}}{\log n}=
\frac{1}{\kappa(p,\rho)}~~~~~~~~~~~~~~~~~~(pr.),
\end{equation}
where
\begin{equation}
\kappa(p,\rho) = \rho \log \frac{\rho}{p} + (1-\rho) \log
\frac{1-\rho}{1-p}.
\end{equation}
More precisely,
\begin{equation}
P(R_{\rho} \geq r_0) \leq  O\left(\frac{\log
n}{n^{1/\kappa(p,\rho)}}\right),
\end{equation}
where
\begin{equation}
r_0 = \frac{\log n -\log\log n + \log \kappa(p,\rho)}
{\kappa(p,\rho)} \label{eq:r0}
\end{equation}
for large $n$.
\end{itemize}

\end{frame}

\begin{frame}{Largest Dense Subgraph}

Plugging in values of $n$, $p$, and setting $\rho = 0.9$, the $p$-value of
a 300 person $\rho$ dense component in facebook is about $10^{-4}$!

\end{frame}


\begin{frame}{Piecewise $G(n,p)$ model}

\begin{itemize}
\item The size of largest dense subgraph is still proportional to
$\log n/ \kappa$ with a constant factor depending on number of hubs
\item
{Model:} \\
\begin{displaymath}
P(uv \in E(G)) = \left\{
\begin{array}{ll}
p_h & \text{if}~u,v\in V_h\\
p_l & \text{if}~u,v\in V_l\\
p_b & \text{if}~u\in V_h, v\in V_l~\text{or}~u\in V_l, v\in V_h
\end{array}
\right.
\end{displaymath}
\item
Result:\\
Let $n_h = |V_h|$. If $n_h=O(1)$, then
$
P(R_n(\rho) \geq r_1) \leq  O\left(\frac{\log n}{n^{1/\kappa(p_l,\rho)}}\right),
$
where
\begin{displaymath}
r_1 = \frac{\log n - \log\log n + 2n_h\log B + \log \kappa(p_l,\rho) - \log e + 1}
{\kappa(p_l,\rho)}
\end{displaymath}
and
$B=\frac{p_bq_l}{p_l}+q_b$,  where $q_b=1-p_b$ and $q_l=1-p_l$.
\end{itemize}

\end{frame}

\begin{frame}{Algorithms Based on Statistical Significance}
\begin{itemize}
\item Identification of topological modules
\item Use statistical significance as a stopping
criterion for graph clustering heuristics

\item Find a minimum-cut bipartitioning of the network
\item If any of the parts is dense enough, record it as a
dense cluster of proteins
\item Else, further partition them recursively

\end{itemize}

\end{frame}

\begin{frame}{{\sc SiDeS} Algorithm}

\begin{psfrags}
\psfrag{p}[c][c]{$p << 1$}
\centerline{\epsfig{file=sides.eps,width=0.8\textwidth}}
\end{psfrags}

{\sc SiDeS} is available at \url{http://www.cs.purdue.edu/pdsl}

\end{frame}


\begin{frame}{Performance of {\sc SiDeS}}
\begin{itemize}
\item{Biological relevance of identified clusters is
assessed with respect to Gene Ontology (GO)}
{\item Estimate the
statistical significance of the enrichment of each GO term
in the cluster
}
\item{Quality of the clusters with respect to GO
annotations}
{
\item
Assume cluster $C$ containing
$n_C$ genes is associated with term $T$ that is attached to $n_T$ genes
and $n_{CT}$ of genes in $C$ are attached to $T$
\item
specificity = $100 \times n_{CT}/{n_C}$
\item
sensitivity = $100 \times n_{CT}/{n_T}$
}

\begin{small}
\begin{center}
\begin{tabular}{lccccccc}
\hline
 & \multicolumn{3}{c}{{\sc SiDeS}} & & \multicolumn{3}{c}{MCODE} \\
\cline{2-4}
\cline{6-8}
 & Min. & Max. & Avg. & & Min. & Max. & Avg. \\
\hline
Specificity (\%) & 43.0 &  100.0 & 91.2 & & 0.0 & 100.0 & 77.8 \\
Sensitivity (\%) & 2.0 &  100.0 & 55.8 & & 0.0 & 100.0 & 47.6 \\
\hline
\end{tabular}
\end{center}
\end{small}
\centerline{Comparison of {\sc SideS} with MCODE}
\end{itemize}

\end{frame}


\begin{frame}{Performance of {\sc SiDeS}}


\vspace{0.75in}
\begin{psfrags}
\begin{small}
%psfrag{-log(Significance)}[b][b]{$-\log$($p$-value)}
\psfrag{Cluster size}[t][t]{Cluster size}
\psfrag{SiDeS}[bc][bc]{{\tiny{\sc SiDeS}}}
\psfrag{MCODE}[tc][tc]{{\tiny{\sc mcode}}}
%\psfrag{Sensitivity (\%)}[t][t]{Sensitivity (\%)}
%psfrag{Specifity(\%)}[b][b]{Specificity (\%)}
\psfrag{0}[c][c]{{\tiny 0}}
\psfrag{10}[c][c]{{\tiny 10}}
\psfrag{20}[c][c]{{\tiny 20}}
\psfrag{30}[c][c]{{\tiny 30}}
\psfrag{40}[c][c]{{\tiny 40}}
\psfrag{50}[c][c]{{\tiny 50}}
\psfrag{60}[c][c]{{\tiny 60}}
\psfrag{70}[c][c]{{\tiny 70}}
\psfrag{80}[c][c]{{\tiny 80}}
\psfrag{90}[c][c]{{\tiny 90}}
\psfrag{100}[c][c]{{\tiny 100}}
\centerline{
  \epsfig{file=size_vs_sig.eps, width=0.4\textwidth}
  \hspace{0.1in}
  \epsfig{file=spec_vs_sens.eps, width=0.4\textwidth}
}
\end{small}
\end{psfrags}

\vspace{0.5in}
\centerline{\hspace{0.03\textwidth}Size vs Significance
\hspace{0.2\textwidth}Sensitivity vs Specifity}

\vspace{0.5in}
\centerline{Correlation \hspace{0.5\textwidth}}

\vspace{0.1in}
\centerline{{\sc SiDeS:} 0.76 \hspace{0.5\textwidth}}
\centerline{MCODE: 0.43 \hspace{0.5\textwidth}}

\end{frame}

\begin{frame}{Performance of {\sc SiDeS}}

\vspace{0.75in}
\begin{psfrags}
\begin{small}
\psfrag{Cluster size}[t][t]{Cluster size}
\psfrag{SiDeS}[bc][bc]{{\tiny{\sc SiDeS}}}
\psfrag{MCODE}[tc][tc]{{\tiny{\sc mcode}}}
%psfrag{Sensitivity (\%)}[b][b]{Sensitivity (\%)}
%psfrag{Specifity (\%)}[b][b]{Specificity (\%)}
\psfrag{0}[c][c]{{\tiny 0}}
\psfrag{10}[c][c]{{\tiny 10}}
\psfrag{20}[c][c]{{\tiny 20}}
\psfrag{30}[c][c]{{\tiny 30}}
\psfrag{40}[c][c]{{\tiny 40}}
\psfrag{50}[c][c]{{\tiny 50}}
\psfrag{60}[c][c]{{\tiny 60}}
\psfrag{70}[c][c]{{\tiny 70}}
\psfrag{80}[c][c]{{\tiny 80}}
\psfrag{90}[c][c]{{\tiny 90}}
\psfrag{100}[c][c]{{\tiny 100}}
\centerline{
  \epsfig{file=size_vs_spec.eps, width=0.4\textwidth}
  \hspace{0.1in}
  \epsfig{file=size_vs_sens.eps, width=0.4\textwidth}
}
\end{small}
\end{psfrags}

\vspace{0.5in}
\centerline{Size vs Specificity
\hspace{0.3\textwidth}Size vs Sensitivity}

\vspace{0.5in}
\centerline{Correlation }

\vspace{0.1in}
\centerline{{\sc SiDeS:} 0.22 \hspace{0.3\textwidth} {\sc SiDeS:} 0.27}
\centerline{MCODE: -0.02 \hspace{0.3\textwidth} MCODE: 0.36}


\end{frame}


\subsection{Statistical Significance of Overlap of Clusters}


\begin{frame}

\begin{center}

70\% of your friends on Facebook are male, 60\% of your friends are computer scientists,
and 80\% of your friends are Indian. Do these numbers (and their overlaps) tell you anything?

\end{center}

\end{frame}



\begin{frame}{Combining Density and Overlap (CoDO) of Clusters in Graphs}

\begin{block}{An overlap is significant if ...}
\begin{enumerate}
\item It is at least as dense as the constituting graphs
\item It is ``large enough"
\end{enumerate}
\end{block}

\end{frame}


\begin{frame}{Combing Density and Overlap (CoDO)}{Formal Statement}

\begin{definition}
\begin{align*}
	\pCoDO
    &= \Pr[|\Set{\hat{A}} \lintersect \Set{\hat{B}}| \geq |\Set{Z}| ~\lintersect~ \delta(\Set{\hat{A}} ~\lintersect~ \Set{\hat{B}}) \geq \delta(\Set{Z})] \nonumber\\
\end{align*}
\end{definition}
where $\Set{Z}$ is the set of vertices in the overlap subgraph and $\delta()$ measures the density of a graph, i.e. $\frac{|E|}{C(|V|, 2)}$.
\end{frame}



\begin{frame}{Combing Density and Overlap (CoDO)}{Expansion}

By conditioning on the size of the overlap, we can get an explicit formula for this 
$p$-value in terms of hypergeometric tails:
\begin{align*}
	\pCoDO 
    &= \sum_{j=|\Set{Z}|}^{\min\{|\hat{A}|, |\hat{B}|\}}
      \Pr\left[|\hat{A}\lintersect \hat{B}| = j\right]
      \cdot \Pr\left[\delta(\hat{A}\lintersect \hat{B}) \geq \delta(\Set{Z}) \big|  |\hat{A} \lintersect \hat{B}| = j \right]
\end{align*}
\end{frame}



\begin{frame}{Combing Density and Overlap (CoDO)}{Example}

\begin{figure}[!h]
\centering
\hfil%
\subfigure[\footnotesize Insignificant Overlap/Insignificant Density\label{fig:inSigOver-inSigDen}]{\includegraphics[width=.35\columnwidth]{figures/inSigOverlap-inSigDensity}}%
\hfil%
\subfigure[\footnotesize Insignificant Overlap/Significant Density\label{fig:inSigOver-SigDen}]{\includegraphics[width=.35\columnwidth]{figures/inSigOverlap-SigDensity}}%
\hfil%
\subfigure[\footnotesize Significant Overlap/Insignificant Density\label{fig:SigOver-inSigDen}]{\includegraphics[width=.35\columnwidth]{figures/SigOverlap-inSigDensity}}%
\hfil%
\subfigure[\footnotesize Significant Overlap/Significant Density\label{fig:SigOver-SigDen}]{\includegraphics[width=.35\columnwidth]{figures/SigOverlap-SigDensity}}%
\end{figure}
\end{frame}




\begin{frame}{Combing Density and Overlap (CoDO)}{Application-- Social networks}
\begin{figure}[!h]
\centering
\hfil%
\subfigure[Facebook\label{fig:FB}]{\includegraphics[width=.3\columnwidth]{figures/facebook}}%
\hfil%
\subfigure[Google+\label{fig:GPlus}]{\includegraphics[width=.3\columnwidth]{figures/gplus}}%
\hfil%
\subfigure[Twitter\label{fig:Twitter}]{\includegraphics[width=.3\columnwidth]{figures/twitter}}%
\end{figure}

\begin{definition}
\small \alert{Ego Net} is the induced subgraph among friends (alters) of a given user (ego)
\end{definition}

\end{frame}


\begin{frame}{Combing Density and Overlap (CoDO)}{Application-- Biological networks}

\begin{center}

\begin{figure}
\includegraphics[width=0.6\columnwidth]{figures/CoDO_annotated}
\end{figure}

Overlap among KEGG pathways is an indicator of \alert{pathway cross-talk}
\end{center}

\end{frame}

\subsection{Clusters and Lineage}

\begin{frame}{Tracking Lineage of Clusters}

        \begin{center}

Say, your favorite clustering algorithm gives you the following clusters:
\vspace*{0.2in}

                \includegraphics[width=1.0in]{Venn2}

\vspace*{0.2in}
Can we say anything about the lineage of these clusters?
        \end{center}

\end{frame}

\begin{frame}{Tracking Lineage of Clusters}

\begin{itemize}
\item
We need to make sure that each of the clusters, x, y, and z are statistically significant
themselves.
\item
We need to make sure that one of the clusters is not contained in the other (statistical
significance of edge cut).
\item
We need to assess the statistical significance of the overlap of the two clusters.
\end{itemize}
\end{frame}


\begin{frame}{Tracking Lineage of Clusters}

\begin{center}

                \includegraphics[height=3.0in]{lineage}

\end{center}

\end{frame}


\begin{frame}{Tracking Lineage of Clusters}

\begin{center}

                \includegraphics[width=4.5in]{ImmuneCells}

\end{center}

\end{frame}









\subsection{Design of (Nonparametric) Priors}


\begin{frame}{Design of (Nonparametric) Priors}

\begin{center}
Constructing suitable background distributions -- the case for non-parametric priors.
\end{center}

Aligning a set of tissue-specific interaction networks to the interactions in yeast
with the goal of identifying the most statistically significant alignments.

\end{frame}




\begin{frame}{Problem statement}

  \begin{columns}[c]
    \column{.3\textwidth}
		\alert{For which tissues is yeast a good model organism?}

    \column{.4\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/tissue_types.jpg}\\	      
    \end{center}
		\tiny{Different human tissues, while inheriting a similar genetic code, exhibit unique anatomical and physiological properties.}
	

    \column{.3\textwidth}
		\alert{What are the shared/ missing functional components in yeast, compared to human tissues?}

	\end{columns}
\end{frame}





\begin{frame}{Random model for tissue-specific networks}
\begin{definition}
\footnotesize
\begin{itemize}
\item \alert{Global human interactome:} All potential interactions between human proteins, represented by graph $G = (V_G, E_G)$
\item \alert{Tissue-specific network(s)}: Vertex-induced subgraph(s) of the Global human interactome,  represented by $G_T = (V_T, E_T)$ with $n_T= |V_T|$, $V_T \subset V_G$, and $E_T \subset E_G$
\item \alert{Universal genes}: Ubiquitously expressed subset of human genes corresponding to houskeeping functions, represented by $V_U \subset V_G$, and $n_U = |V_U|$
\item \alert{Random tissue-specific network(s)}: Vertex-induced subgraphs of $G$, constructed from $V_\mathcal{R} = V_U \cup V_\mathcal{S}$, with $V_\mathcal{S}$ being random set of vertices of size $n_T - n_U$ selected from $V_G \setminus V_U$
\end{itemize}
\end{definition}
\end{frame}




\begin{frame}{Significance of network alignment(s)}
\tiny
\begin{definition}
\begin{itemize}
\item \alert{Original alignment}: $\Weight = \w^T\x$, $\Overlap = \frac{1}{2}\x^T \Square \x$
\item \alert{Monte-Carlo simulation}: Let $\Weight_{\R}$ and $\Overlap_{\R}$ be the random vectors representing the weight and overlap of aligning $k_{\R}$ random tissue-specific networks with yeast
\item \alert{Positive/Negative cases}: $k_P$ is the number of random cases with both $\Weight_{\R} \leq \Weight$ and . $\Overlap_{\R} \leq \Overlap$. $k_N$ is defined as the size of complement set.
\item \alert{p-value} bounds:
\begin{equation*}
\delta_{\R} = \frac{k_P}{k_{\R}} \leq \mbox{alignment p-value} \leq 1-\frac{k_N}{k_{\R}} = \Delta_{\R}
\end{equation*}
\item \alert{Alignment p-value}:
\begin{equation*}
p-value = Prob(\alpha*\Overlap + \beta*\Weight \leq \Overlap\Weight_{\R})
\end{equation*}
\end{itemize}
\end{definition}
\end{frame}






\begin{frame}{Partitioning human genes based on their expression selectivity}

\begin{definition}
\footnotesize
\alert{Selectivity \emph{p}-value}-- Given a cluster of homogenous tissues:
\begin{eqnarray*}
\text{\emph{p}-value}(X = c_n) &=& Prob(c_n \leq X)\nonumber \\
&=& HGT(c_n| N, n, c_N) \nonumber  \\
&=& \sum_{x=c_n}^{min(c_N, n)} \frac{{C(c_N, x)} {C(N-c_N,n-x)}} {{C(N,n)}}
\label{eq:ts_pval}
\end{eqnarray*}
\alert{$N$}: total number of tissues, \alert{$n$}: number of tissues in the cluster, \alert{$c_N$}: number of tissues in which a given gene is expressed, \alert{$c_n$}: number of tissue in the cluster that the given gene is expressed.
\end{definition}
\end{frame}






\begin{frame}{Human-specific or conserved?}
\tiny
\begin{definition}
Classification of human tissue-selective genes:
\begin{itemize}
\item \alert{Conserved}: Subset of tissue-selective genes that are consistently
aligned in the "majority" of aligned tissues in the given group
\item \alert{Human-specific}: Subset of tissue-selective genes that are
consistently unaligned in the "majority" of tissues in the given group
\item \alert{Unclassified}: None of the above
\end{itemize}
\end{definition}

\begin{definition}
Majority voting:

\begin{itemize}
\item \alert{Alignment consistency table}: Yeast partner of each tissue-selective gene in the given cluster of tissues
\item \alert{Consensus rate}: Minimum percentage of tissues (columns) in each row of the alignment consistency table that have to agree to make a decision about conserved/human-specificity
\end{itemize}
\end{definition}
\end{frame}




%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
%						Results and discussion
%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
\begin{frame}{Core genes-- The most conserved subset of housekeeping genes}
	\begin{center}
		\includegraphics[width=\textwidth]{figures/Core_AlignGraph}
	\end{center}
\end{frame}



\begin{frame}{Functional enrichment of HK genes}{Core subset}
\begin{itemize}
\item Ribosome biogenesis
\item Translation
\item Protein targeting
\item RNA splicing
\item mRNA surveillance
\end{itemize}
\end{frame}


\begin{frame}{Functional enrichment of HK genes}{Human-specific subset}
\begin{itemize}
\item Anatomical structure development
\item Paracrine signaling
\item NADH dehydrogenase (mitochondrial Complex I)
\end{itemize}
\end{frame}


\begin{frame}{The most similar tissues to yeast}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|cccc}
Name	&pval lower bound	&overall pval	&pval upper bound	&confidence	\\\hline
Myeloid Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Monocytes	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Dentritic Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
NK Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
T-Helper Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Cytotoxic T-Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
B-Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Endothelial	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Hematopoietic Stem Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
MOLT-4	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
B Lymphoblasts	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
HL-60	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
K-562	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Early Erythroid	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Bronchial Epithelial Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0002	&0.9998	\\
Colorectal Adenocarcinoma	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0004	&0.9996	\\
Daudi	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0009	&0.9991	\\
Testis Seminiferous Tubule	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0012	&0.9988	\\
Smooth Muscle	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0016	&0.9984	\\
Blood (Whole)	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0053	&0.9947	\\
Thymus	&$<$ 1.00e-04	&0.0001	&0.0062	&0.9938	\\
Testis Interstitial	&$<$ 1.00e-04	&0.0004	&0.0086	&0.9914
\end{tabular}
\end{table}
\end{frame}


\begin{frame}{The least similar tissues to yeast}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|cccc}
Name	&pval lower bound	&overall pval	&pval upper bound	&confidence	\\\hline
Trigeminal Ganglion	&0.9947	&0.9994	&1	&0.9947	\\
Superior Cervical Ganglion	&0.9847	&0.9991	&1	&0.9847	\\
Ciliary Ganglion	&0.9407	&0.9813	&0.9964	&0.9443	\\
Atrioventricular Node	&0.8746	&0.9792	&0.9921	&0.8825	\\
Skin	&0.8355	&0.9297	&0.9809	&0.8546	\\
Heart	&0.7934	&0.9585	&0.9815	&0.8119	\\
Appendix	&0.7596	&0.9371	&0.973	&0.7866	\\
Dorsal Root Ganglion	&0.7065	&0.933	&0.9717	&0.7348	\\
Skeletal Muscle	&0.3994	&0.5902	&0.7866	&0.6128	\\
Uterus Corpus	&0.233	&0.7736	&0.8769	&0.3561	\\
Lung	&0.0771	&0.3853	&0.5544	&0.5227	\\
Pons	&0.0674	&0.5201	&0.6983	&0.3691	\\
Salivary Gland	&0.0639	&0.3449	&0.5173	&0.5466	\\
Liver	&0.0600	&0.6857	&0.8519	&0.2081	\\
Ovary	&0.0388	&0.2735	&0.4481	&0.5907	\\
Trachea	&0.0259	&0.2376	&0.4146	&0.6113	\\
Globus Pallidus	&0.0206	&0.2471	&0.4336	&0.587	\\
Cerebellum	&0.0127	&0.1950	&0.3783	&0.6344
\end{tabular}
\end{table}

\end{frame}



\begin{frame}{Tissue-tissue similarity network}
	\begin{center}
		\includegraphics[width=.7\textwidth]{figures/TTSN_groups}
	\end{center}
\end{frame}



%\subsubsection{Partitioning tissue-selective genes}
%\begin{frame}{Tissue-selectivity density function}
%	\begin{center}
%		\includegraphics[width=.7\textwidth]{figures/TS_pdfs}\\
%		\tiny
%		(\textbf{A}) Brain tissues, (\textbf{B}) Blood cells, (\textbf{C}) Ganglion tissues, (\textbf{D}) Testis tissues
%	\end{center}
%\end{frame}
%


\begin{frame}{Blood cells}
\begin{figure}[!ht]
\centering
\subfigure[Conserved] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BloodCG_unique_annotated.pdf}
	\label{figure:blood_unique_CG}
}%
\subfigure[Human-specific] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BloodHS_unique_annotated.pdf}
	\label{figure:blood_unique_HS}
}%
\caption{{\bf Enrichment map of unique blood-selective functions.} }
\label{figure:blood_unique}
\end{figure}
\end{frame}


\begin{frame}{Brain tissues}
\begin{figure}[!ht]
\centering
\subfigure[Conserved] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BrainCG_unique_annotated.pdf}
	\label{figure:brain_unique_CG}
}%
\subfigure[Human-specific] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BrainHS_unique_annotated.pdf}
	\label{figure:brain_unique_HS}
}%
\caption{{\bf Enrichment map of unique brain-selective functions.} }
\label{figure:brain_unique}
\end{figure}
\end{frame}




\begin{frame}{Enriched disease classes}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|lc|lc} 
&Conserved genes & &Human-specific genes&\\
&Disease class& \emph{p}-value&Disease class& \emph{p}-value\\\hline
Blood cells& Cancer& $2.85*10^{-3}$& Immune& $1.88*10^{-9}$\\
&&&Infection& $1.00*10^{-2}$\\\hline
Brain tissues&Psych& $3.59*10^{-4}$&Psych& $5.70*10^{-8}$\\
&Chemdependency& $2.60*10^{-3}$&Neurological& $2.97*10^{-2}$\\
&Pharmacogenomic& $9.74*10^{-2}$&&
\end{tabular}
\label{table:disease_summary}
\end{table}
\end{frame}


\begin{frame}{Comparative analysis of brain-specific pathologies}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{p{0.6\linewidth}|cc}
Disorder& Conserved  genes&Human-specific genes\\\hline
schizophrenia	&0.008573	&8.4905E-06\\
autism	&0.048288	&0.00077448\\
dementia	&0.0014356	&-\\
schizophrenia; schizoaffective disorder; bipolar disorder	&-	&0.0021433\\
myocardial infarct; cholesterol, HDL; triglycerides; atherosclerosis, coronary; macular degeneration; colorectal cancer	&0.0051617	&-\\
epilepsy	&0.071562	&0.0064716\\
seizures	&-	&0.020381\\
bipolar disorder	&0.048288	&0.022016\\
attention deficit disorder conduct disorder oppositional defiant disorder	&0.032444	&0.023865
\end{tabular}
\label{table:disease_brain}
\end{table}
\end{frame}

\section{Some Open Problems}

\begin{frame}{Some Interesting Questions}
\end{frame}

\begin{frame}{Significance of Keywords in Text}
\begin{itemize}
\item
Search engines typically search for keywords, and use proximity of keywords as one of the primary
heuristics for ordering search results.
\item
An alternate (and more rogorous, IMHO) formulation would order documents by the statistical significance
of keyword occurrance.
\item
Given a sequence $<S>$ (along with a generation model for $<S>$, preferably Markovian), what is the
likelihood of observing a given set of keywords $k_1, ..., k_j$ within the shortest subsequence $<S'>$ of
$<S>$ of length $d$ or less.
\item
The lower this $p$-value, the more significant the match (i.e., rank this higher among returned
results).
\end{itemize}

\end{frame}



\begin{frame}{Significance of Snippets in Graphs}
\begin{itemize}
\item
Consider your favorite social network and construct a mapping from node attrubutes to a scalar (the
color of the node). For instance, females, over 30, making more than \$200K are mapped to color Red;
males over 30 with two children are mapped to color Green.

\item
Can we argue the statistical significance
of tight subgraphs that contain prescribed colors -- for instance, do we see overrepresentation of
tight subgraphs containing Red, Green, and Blue (children, perhaps) nodes?

\item
Given a graph $G$ (along with a generation model for $G$), what is the likelihood of observing
a given set of query colors $c_1, ..., c_j$ in a subgraph $G'$ of $G$ of diameter $d$ or less?
\end{itemize}

\end{frame}



\begin{frame}{Arrival Sequence of Nodes in Dynamic Graphs}

\begin{itemize}
\item
For a dynamic network, how can we infer a likely arrival sequence for nodes?

\item
Given a graph $G$ (along with a generation model for $G$), what is the likelihood of observing
the graph $G$ for a given arrival sequence $n_1, n_2, ..., n_k$. How do we determine this arrival
sequence to maximize the probability?

\item
For a preferential attachment model, we can generate a set of precedence constraints. Any
arrival sequence that satisfies all of these precedence constraints is a potential true sequence.

\item
How do we optimize within this (super)exponential space? We have some experimental evidence and
theoretical justification to show that we dont have to!

\end{itemize}

\end{frame}

\begin{frame}{Arrival Sequence of Nodes in Dynamic Graphs}


\begin{figure}
\includegraphics[width=2.0in]{arrival}
\caption{Probability of randomly selected feasible arrival sequences.}
\end{figure}



\end{frame}


\begin{frame}{Some Parting Thoughts}

\begin{itemize}
\item
Significance if an essential aspect of quantifying the usefulness of an observation.
\item
Significance is an essential component of validating observations.
\item
Significance testing is hard; requiring solutions to complex analysis problems.
\item
Maximizing significance should be one of the primary goals of algorithms/ heuristics.
\end{itemize}
\end{frame}


\begin{frame}{Thanks}

Many thanks to the organizers for giving me this opportunity to talk, and to you for
engaging with me!

\end{frame}

\end{document}


\begin{frame}{Motivation}
Global human interactome is a superset of all \alert{possible} physical interactions that can take places in the cell. It does not provide any information as to which one of these interactions do take place in a given \alert{tissue/cell-type context}.
\end{frame}

\subsection{Problem statement}
\begin{frame}{What we have -- What we want}
Available data sources:
\begin{enumerate}
\item A global interactome, which contains the set of \textit{possible} interacting pairs.
\item A tissue-specific measurement of gene/protein activity within each tissue/cell type.
\end{enumerate} 


\begin{block}{Problem}
How can we optimally utilize transcriptional activity of gene products to construct the most informative tissue-specific sub-network?
\end{block}
\end{frame}


\subsection{Previous work}
\begin{frame}{Overview}

\begin{definition}
	\begin{enumerate}
		\item \alert{Node Removal (NR): } Tissue-specific network is generated by removing from the global network proteins that are not expressed in the relevant tissue.
		\item \alert{Edge Reweight (ERW): } It modify the edge weights to reflect the probability that the corresponding interactions take place in the specific tissue.	
		\begin{equation*}
		w_{ij}' = w_{ij}*\alpha^k
		\end{equation*}
		where $0 \leq \alpha \leq 1$ is the re-weighting factor and $k \in \{0, 1, 2\}$ is the number of end-points for the protein-protein interaction that are expressed in the tissue of interest.
	\end{enumerate}

\end{definition}
\end{frame}


\begin{frame}{Problems with Previous Methods}
\begin{itemize}
\item Rely on an ad hoc threshold for identifying expressed genes.
\item Utilize only local topology around each edge, specifically its end-points, to decide about existence/probability of an interaction.
\end{itemize}
\end{frame}

\subsection{Example}
\begin{frame}{Example subnetwork}

\begin{figure}
\includegraphics[width=.80\columnwidth]{figures/ActPro/AgPresenting}
\caption{Example of an upregulated pathway in blood cells-- Antigen processing and presentation}
\end{figure}

\end{frame}




\section{Activity Propagation (ActPro)}
\subsection{Standardizing gene expression profiles}
\begin{frame}{Universal exPression Codes (UPC)}{Computing transcriptional activity of genes}
  \begin{columns}[c]   
    \column{.55\textwidth}
		\begin{itemize}\small
		\item Processes each sample individually
		\item Corrects for platform-specific background noise
		\item Uses a mixture model to estimate whether a gene transcriptional activity
		\item Has been demonstrated that, for tissue samples profiled using both microarrays and RNA-Seq, UPC values can be highly concordant
		\end{itemize}
    \column{.45\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/ActPro/Blood-Liver-Testis}\\
	    \tiny Distribution of transcriptional activities in three tissues with low, medium, and high number of expressed genes
    \end{center}	
	\end{columns}
\end{frame}


\begin{frame}{Universal exPression Codes (UPC)}{Validating tissue-specific markers}
    \begin{center}
		\includegraphics[height=0.75\textheight]{figures/ActPro/markers_comparison}\\
	    \tiny GO enrichment for tissues with high, medium, and low number of markers
    \end{center}	
\end{frame}

\subsection{Computing functional activity of genes}
\begin{frame}{Optimization problem}{Inferring functional activity of genes}
Minimal number of changes that smooths transcriptional activities over adjacent nodes in the network:

\begin{alignat*}{2}
\Vector{x}^* = \argmin_{\Vector{x}} &\bigg\{ (1-\alpha) \Vector{x}\Matrix{L}\Vector{x} +  \alpha \parallel \Vector{x} - \Vector{z}  \parallel_1\bigg\}\nonumber\\
\mbox{Subject to:} & \begin{cases}
	\Vector{1}^{T}\Vector{x} = 1&\\
	0 \leq \Vector{x}
\end{cases}
\end{alignat*}
\begin{itemize}
\item Vector $\Vector{z}$ initial value of transcriptional activities estimated by UPC
\item Matrix $\Matrix{L}$ is the \textit{Laplacian} matrix, defined as $\Matrix{A} - \Matrix{D}$, where $d_{ii}$ is the weighted degree of $i^{th}$ vertex in the global interactome.
\item Parameter $\alpha$ controls the relative importance of regularization
\end{itemize}
\end{frame}



\begin{frame}{Interpretation}{Loss function}
\begin{itemize}
\item The first term defines a \textit{diffusion kernel} that propagates activity of genes through network links.
\item We can expand it as $\sum_{i, j} w_{i, j} (x_i - x_j)^2$, which is the accumulated difference of  values between adjacent nodes scaled by the weight of the edge connecting them.
\item The Laplacian operator $\Matrix{L}$ acts on a given function defined over vertices of a graph, such as $\Vector{x}$, and computes the smoothness of $\Vector{x}$ over adjacent vertices.
\item It can be also computed as $\parallel \Matrix{B}\Vector{x} \parallel_2^2$, where $\Matrix{B}$ is the incident matrix of the graph
\end{itemize}
\end{frame}


\begin{frame}{Interpretation}{Regularizer}
\begin{itemize}
\item  The second term is a \textit{regularizer} which penalizes changes or deviations
\item We can expand it as $\sum_{i} |x_i - z_i|$, where $x_i$ and $z_i$ are the (inferred) \underline{functional} and the \underline{transcriptional} activity of gene $i$, respectively.
\item It enforces sparsity over the vector of differences between \textit{transcriptional} and \textit{functional} activities. 
\end{itemize}

\end{frame}

%\begin{frame}{Implementation}{CVX formulation}
%\begin{itemize}
%
%\end{itemize}
%
%\end{frame}

\subsection{Updating global interactome}
\begin{frame}{Constructing tissue-specific interactome}
\begin{block}{Updating edges}
\begin{equation*}
\hat{\Matrix{A}} = \diag (\Vector{x}^*) * \Matrix{A} * \diag(\Vector{x}^*)
\end{equation*}
\end{block}

\begin{itemize}
\item $\Vector{x}^*$ is the solution of optimization problem\
\item It represents functional activity of genes
\item Functional activities are inferred from the global network context
\item We update each edge according to the functional activity of its end-points
\end{itemize}
\end{frame}




\section{Results}
\subsection{Network statistics}
\begin{frame}{Decomposition of global interactome}

\begin{figure}
\includegraphics[width=.75\columnwidth]{figures/ActPro/decomp}
\end{figure}

Brain-specific network using ERW and ActPro ($\alpha=0.5$) methods
\centering

\end{frame}


\subsection{Predicting known biology}
\begin{frame}{Results}{Predicting tissue-specific interactions in known functional pathways}
\begin{columns}[c]
	\column{0.55\textwidth}
	\begin{center}
		\includegraphics[width=\columnwidth]{figures/ActPro/ESEA_AUC}\\
		\tiny Average performance of different methods in predicting differential interactions
	\end{center}
		
	\centering Edge Set Enrichment Analysis (ESEA)
	
	\column{0.45\textwidth}
	\begin{center}
		\includegraphics[height=0.2\textheight]{figures/ActPro/Fallopian_Tube_ROC.pdf}\\
		\includegraphics[height=0.2\textheight]{figures/ActPro/Cervix_Uteri_ROC.pdf}\\
		\includegraphics[height=0.2\textheight]{figures/ActPro/Vagina_ROC.pdf}\\
		\tiny Tissues with the highest gain of AUC for predicting tissue-specific pathway edges
	\end{center}

\end{columns}
\end{frame}


\begin{frame}{Results}{Compactness of disease-related genes}

\begin{table}\tiny
\centering
\begin{tabular}{l|cccccc}
	&	\textbf{global	}&	\textbf{ActPro\_0.15	}&	\textbf{ActPro\_0.50	}&	\textbf{ActPro\_0.85	}&	\textbf{ERW	}&	\textbf{NR}\\\hline
Alzheimer's disease	&\textbf{4.12E-3}	&6.96E-3	&5.98E-3	&5.44E-3	&5.32E-3	&9.60E-2\\
breast carcinoma	&1.83E-3	&1.11E-3	&8.40E-4	&\textbf{8.30E-4}	&4.09E-3	&8.15E-2\\
chronic lymphocytic leukemia	&8.20E-4	&7.40E-4	&\textbf{4.80E-4}	&5.10E-4	&8.50E-4	&2.94E-2\\
coronary artery disease	&3.95E-1	&1.58E-1	&1.09E-1	&1.03E-1	&1.33E-1	&\textbf{1.93E-2}\\
Crohn's disease	&2.56E-2	&1.93E-2	&1.50E-2	&\textbf{1.44E-2}	&8.54E-2	&4.14E-1\\
metabolic syndrome X	&1.11E-2	&1.09E-2	&\textbf{1.07E-2}	&1.12E-2	&1.02E-1	&7.39E-1\\
Parkinson's disease	&1.59E-2	&1.25E-2	&9.89E-3	&\textbf{9.50E-3}	&1.34E-2	&9.62E-2\\
primary biliary cirrhosis	&\textbf{7.20E-4}	&1.32E-3	&3.16E-3	&3.40E-3	&2.80E-2	&6.86E-1\\
psoriasis	&\textbf{2.10E-4}	&1.10E-3	&1.16E-3	&9.50E-4	&4.67E-3	&3.24E-1\\
rheumatoid arthritis	&1.70E-2	&\textbf{9.28E-3}	&1.06E-2	&1.10E-2	&6.39E-2	&3.61E-1\\
systemic lupus erythematosus	&4.98E-2	&1.19E-2	&7.56E-3	&7.22E-3	&2.55E-3	&\textbf{1.60E-4}\\
type 1 diabetes mellitus	&2.64E-2	&3.01E-2	&\textbf{2.38E-2}	&2.40E-2	&2.64E-1	&9.39E-1\\
type 2 diabetes mellitus	&1.57E-3	&2.90E-4	&2.40E-4	&\textbf{1.80E-4}	&5.60E-4	&7.90E-3\\
vitiligo	&\textbf{1.17E-3}	&2.13E-3	&3.04E-3	&3.54E-3	&1.84E-2	&5.69E-1\\
schizophrenia	&3.47E-1	&2.13E-1	&1.93E-1	&1.84E-1	&1.40E-1	&\textbf{4.10E-2}\\\hline
combined	&1.53E-13	&1.24E-17	&6.62E-19	&\textbf{3.70E-19}	&9.03E-14	&2.43E-03\\
\end{tabular}
\end{table}

\begin{itemize} \small
\item Symmetric random-walk as a measure of distance
\item Empirical \emph{p}-value for each tissue
\item \emph{p}-value combination using Edgington method
\end{itemize}

\begin{center}
$\Rightarrow$ \textit{ActPro} yields more significant compactness for known disease genes
\end{center}
\end{frame}

\subsection{Identifying disease-related pathways}
\begin{frame}{Results}{Identifying novel disease-related pathways}
\begin{columns}[c]
	\column{.45\textwidth}
	\begin{center}	
		\includegraphics[height=.35\textheight]{figures/ActPro/Alzheimer}\\
		\tiny Alzheimer's Disease\\
		\vspace{1em}
		\includegraphics[height=.35\textheight]{figures/ActPro/Parkinson}\\
		\tiny Parkinson's Disease\\
	\end{center}
	\column{0.55\textwidth}
		\begin{itemize}
			\item Prize Collecting Steiner Tree (PCST)
			\begin{equation*} 
				\argmin_{<v, e> \in T} \Big\{  \sum_{e} c_e - \lambda \sum_{v} b_v \Big\}
			\end{equation*}
			\item Solved using known message-passing algorithm
		\end{itemize}
\end{columns}
\end{frame}


\begin{frame}{Questions}

\begin{figure}
\includegraphics[width=.85\textwidth]{figures/questions}
\end{figure}

\alert{PS: I am defending this summer and will be in the job marker for PostDocs.}
\end{frame}

\end{document}


