Searching for a source of difference in graphical models

Abstract

We look at a two-sample problem within the framework of decomposable graphical models. When the global hypothesis of equality of two distributions is rejected, the interest is usually in localizing the source of difference. Motivated by the idea that diseases can be seen as system perturbations, and by the need to distinguish between the origin of perturbation and components affected by the perturbation, we introduce the concept of a minimal seed set, and its graphical counterpart a graphical seed set. They intuitively consist of variables driving the difference between the two conditions. We propose a simple testing procedure, linear in the number of nodes, to estimate the graphical seed set from data. We illustrate our approach in the context of gene set analysis, where we show that is possible to zoom in on the origin of perturbation in a gene network.

Introduction

The present work is motivated by the problem of identifying the origin of perturbation in gene regulatory networks. In biological networks, diseases can be modeled as perturbations that affect certain targets, which, once perturbed, propagate the perturbation through network connections [6]. In practice, we often collect and compare observations from healthy individuals and observations from patients after the disease related perturbation has already taken place. On the basis of this comparison, it is of interest to identify the site of original perturbation, i.e., the source of difference, and distinguish it from the elements of the network that were affected through the process of network propagation.

Let $\mathcal{F}=\{P_{\theta };\theta \in \Theta \}$, $\Theta \subset R^d$, be a family, parametrized by $\theta$, of probability distributions for the random vector $X_V$, indexed by a set $V$, $\left|V\right|=p$, with support ${\mathcal{X}}_V$. In what follows, to unburden the notation and when no ambiguity can arise, we adopt the notation of [5] and, allowing for a slight abuse of notation, we write $\theta$ instead of $P_{\theta }$ to denote individual distributions belonging to $\mathcal{F}$. For $A,B\subseteq V$, we will further write ${\theta }_A$ to denote (the parameters of) the marginal distribution of variables in $A$ and, similarly, ${\theta }_{A|B}$ to denote a collection of conditional distributions $\left\{{\theta }_{A\mid X_B=y},y\in {\mathcal{X}}_B\right\}$ indexed by $y$, where $X_B,B\subseteq V$, is a subvector of $X_V$ and ${\mathcal{X}}_B$ is the associated support. Different experimental conditions will be distinguished by use of superscripts.

Consider a random vector $X_V\sim P_{\theta }$. Within the context of two sample problems, the interest is often in testing the null hypothesis of equality of distributions $H_0:{\theta }^{\left(1\right)}={\theta }^{\left(2\right)}$. If that hypothesis is rejected, one usually aims at localizing the source of difference.

A common approach to tackle the question in genomics applications is to focus on the $p$ univariate marginal distributions, see for instance [16] for a particularly popular method choice. Marginally speaking, a variable $X_v$, $v\in V$, can be considered relevant to the aim at hand if its marginal distribution is different in $P_{{\theta }^{\left(1\right)}}$ and $P_{{\theta }^{\left(2\right)}}$.

The (index) set of the relevant variables is then taken to be

$$R=\left\{v\in V:{\theta }_v^{\left(1\right)}\ne {\theta }_v^{\left(2\right)}\right\}.$$

Whether a variable belongs to $R$ depends solely on its marginal distribution.

Although simple and computationally feasible, the marginal approach might fail to point to the true source of difference whenever an interplay between variables plays a role in differentiating the two distributions [10]. In that case, we propose to privilege a conditional perspective and exploit an approach which takes into account the entire $p$-dimensional joint distribution and flags a variable relevant only if the difference in its marginal distribution cannot be explained by the remaining variables. We define the set of conditionally relevant variables $D$ as follows.

Definition 1 Seed Set

Consider ${\theta }^{\left(1\right)},{\theta }^{\left(2\right)}\in \mathcal{F}$. We call the set $D\subseteq V$ the seed set, if the collections of conditional laws ${\theta }_{V\setminus D\mid D}^{\left(1\right)}$ and ${\theta }_{V\setminus D\mid D}^{\left(2\right)}$ coincide. Furthermore, we say that $D$ is a minimal seed set, if no proper subset of it is itself a seed set.

To facilitate the understanding of the above definition, it is helpful to consider that, by employing the factorization $p(x;\theta )=p(x_D;{\theta }_D)p(x_{\bar{D}}\mid x_D;{\theta }_{\bar{D}\mid D})$, where $\bar{D}=V\setminus D$, the likelihood ratio $p(x;{\theta }^{\left(1\right)})/p(x;{\theta }^{\left(2\right)})$ simplifies to $p(x_D;{\theta }_D^{\left(1\right)})/p(x_D;{\theta }_D^{\left(2\right)})$. The likelihood ratio thus depends only on variables in $D$. When comparing the two distributions, the variables outside of $D$ are either irrelevant or redundant and $D$ can be seen as the minimal subset of variables explaining the difference between the two distributions. It should be stressed that there is no relation between $R$ and $D$; in general neither $R\subseteq D$ nor $D\subseteq R$.

In practice, to identify the seed set, $D$ needs to be estimated from data. One could perform a number of tests of equality of conditional distributions, but when $p$ is large, this testing problem becomes extremely challenging, and represents an open area of research, see for instance [25] and references therein. In this paper, we assume that the dependence structure among the $p$ variables in the joint distribution can be well represented by an undirected graph. We then address the problem of identifying $D$ within the framework of graphical models, where we exploit the structural modularity of decomposable graphical models [5], [8]. To this aim, we assume that $\mathcal{F}$ is a strong meta Markov model with respect to a given undirected decomposable graph $G=(V,E)$, where $E\subseteq V\times V$ is a set of edges. Let us denote by $\mathcal{M}\left(G\right)$ a family of distributions satisfying the global Markov property relative to $G$. According to the definition introduced by [5], $\mathcal{F}\subseteq \mathcal{M}\left(G\right)$ is a strong meta Markov model if for any decomposition ($A,B$) of $G$, parameters ${\theta }_A$ and ${\theta }_{B\mid A}$ are variation independent in $\mathcal{F}$ [2, p.26]. In other words, all possible values of ${\theta }_A$ are logically compatible with all possible values of ${\theta }_{B\mid A}$.

Under this assumption, there is a close relationship between the parametric model structure and the underlying graph, and we show that the problem of identifying $D$ can be formulated as the problem of testing equality of lower dimensional conditional distributions induced by the structure of $G$. We further show that the associated test statistics are functions of the quantities pertaining to the lower dimensional marginal distributions. The key advantage is that inference on marginal distributions is significantly less challenging than inference on conditional distributions. Beside the computational gain, we argue that the proposed approach addresses the issue of exploiting information on the structure of dependence in an efficient and elegant way.