Learning directed acyclic graphs from large-scale genomics data

Abstract

In this paper, we consider the problem of learning the genetic interaction map, i.e., the topology of a directed acyclic graph (DAG) of genetic interactions from noisy double-knockout (DK) data. Based on a set of well-established biological interaction models, we detect and classify the interactions between genes. We propose a novel linear integer optimization program called the Genetic-Interactions-Detector (GENIE) to identify the complex biological dependencies among genes and to compute the DAG topology that matches the DK measurements best. Furthermore, we extend the GENIE program by incorporating genetic interaction profile (GI-profile) data to further enhance the detection performance. In addition, we propose a sequential scalability technique for large sets of genes under study, in order to provide statistically significant results for real measurement data. Finally, we show via numeric simulations that the GENIE program and the GI-profile data extended GENIE (GI-GENIE) program clearly outperform the conventional techniques and present real data results for our proposed sequential scalability technique.

Keywords: Big data; Discrete optimization; Genetic interaction analysis; Graph learning; Large-scale gene networks; Multiple hypothesis test.

Fig. 1

DAG ${\mathcal{D}}_0$ of 13 genes and root node R

Fig. 2

Possible hierarchical relationship classes between two arbitrary genes i,j of DAG $\mathcal{D}$ according to [2]

Fig. 3

Example SMAP $\mathcal{S}$

Fig. 4

Schematically reduced DAGs ${\mathcal{D}}_1$ to ${\mathcal{D}}_5$ corresponding to Eqs. (5a)–(5e), respectively

Fig. 5

Left: Original DAG ${\mathcal{D}}_a$ with corresponding set of hierarchical relationship classes $A^{{\mathcal{D}}_a}$. Right: Reconstruction ${\widehat{\mathcal{D}}}_a$ of DAG ${\mathcal{D}}_a$ based on $A^{{\mathcal{D}}_a}$

Fig. 6

Example DAG ${\mathcal{D}}_{\mathrm{R}}$ to elucidate the functionality of the RHS of condition E_R of Table 2

Fig. 7

D _ed versus SNR; t _corr=0.6; 200 Monte Carlo runs; λ _d=0.05, λ _c=1, λ _p=0.8

Fig. 8

D _mis versus SNR; t _corr=0.6; 200 Monte Carlo runs; λ _d=0.05, λ _c=1, λ _p=0.8

Fig. 9

Reliability matrix M _G; S=5e ⁴ subsets considered; subset size N _S=10

Fig. 10

Reliability matrix M _GI; S=5e ⁴ subsets considered; subset size N _S=10; λ _d=1e3, λ _c=1, λ _p=0.85