Bayesian Orthogonal Least Squares (BOLS) algorithm for reverse engineering of gene regulatory networks

Abstract

Background: A reverse engineering of gene regulatory network with large number of genes and limited number of experimental data points is a computationally challenging task. In particular, reverse engineering using linear systems is an under-determined and ill conditioned problem, i.e. the amount of microarray data is limited and the solution is very sensitive to noise in the data. Therefore, the reverse engineering of gene regulatory networks with large number of genes and limited number of data points requires rigorous optimization algorithm.

Results: This study presents a novel algorithm for reverse engineering with linear systems. The proposed algorithm is a combination of the orthogonal least squares, second order derivative for network pruning, and Bayesian model comparison. In this study, the entire network is decomposed into a set of small networks that are defined as unit networks. The algorithm provides each unit network with P(D|Hi), which is used as confidence level. The unit network with higher P(D|Hi) has a higher confidence such that the unit network is correctly elucidated. Thus, the proposed algorithm is able to locate true positive interactions using P(D|Hi), which is a unique property of the proposed algorithm. The algorithm is evaluated with synthetic and Saccharomyces cerevisiae expression data using the dynamic Bayesian network. With synthetic data, it is shown that the performance of the algorithm depends on the number of genes, noise level, and the number of data points. With Yeast expression data, it is shown that there is remarkable number of known physical or genetic events among all interactions elucidated by the proposed algorithm. The performance of the algorithm is compared with Sparse Bayesian Learning algorithm using both synthetic and Saccharomyces cerevisiae expression data sets. The comparison experiments show that the algorithm produces sparser solutions with less false positives than Sparse Bayesian Learning algorithm.

Conclusion: From our evaluation experiments, we draw the conclusion as follows: 1) Simulation results show that the algorithm can be used to elucidate gene regulatory networks using limited number of experimental data points. 2) Simulation results also show that the algorithm is able to handle the problem with noisy data. 3) The experiment with Yeast expression data shows that the proposed algorithm reliably elucidates known physical or genetic events. 4) The comparison experiments show that the algorithm more efficiently performs than Sparse Bayesian Learning algorithm with noisy and limited number of data.

Figure 1

The Bayesian Orthogonal Least Squares algorithm could be used as a framework for gene regulatory study including the collecting and modeling of data.

Figure 2

The schematic of unit network. (a) Input unit network consisting of target gene Y_i and all other genes as regulator candidates. (b) Output unit network consisting of target gene Y_i and its most probable regulators.

Figure 3

ROC analysis of BOLS output with K = 100. (a) N = 5 and ε = 0.01, (b) N = 5 and ε = 0.05, (c) N = 5 and ε = 0.1, (d) N = 10 and ε = 0.01, (e) N = 10 and ε = 0.05, (f) N = 10 and ε = 0.1, (g) N = 15 and ε = 0.01, (h) N = 15 and ε = 0.05, (i) N = 15 and ε = 0.1. For all Figures, the x-axis corresponds to the complementary specificity, the y-axis sensitivity.

Figure 4

ROC analysis of BOLS output with N = 10. (a) K = 100 and ε = 0.01, (b) K = 100 and ε = 0.05, (c) K = 100 and ε = 0.1, (d) K = 200 and ε = 0.01, (e) K = 200 and ε = 0.05, (f) K = 200 and ε = 0.1, (g) K = 300 and ε = 0.01, (h) K = 300 and ε = 0.05, (i) K = 300 and ε = 0.1. For all Figures, the x-axis corresponds to the complementary specificity, the y-axis sensitivity.

Figure 5

The changes of performance of BOLS as the network pruning step proceeds. The simulation experiment is done with N = 50, K = 20, and ε = 0.1. In these Figures, we concentrate on an output unit-network that has the highest logP(D|H_i) among all output unit networks. For all Figures, the x-axis corresponds to the number of inferred interactions: as the network pruning proceeds, the number of inferred interactions in unit network decreases. Each y-axis corresponds to (a) logP(D|H_i), (b) the number of errors (FP+FN), (c) the complementary specificity, (d) the sensitivity.

Figure 6

The relationship between the evidence value P(D|H_i) and the number of errors for unit networks, where K = 100, ε = 1.0e-2, and m_max = 4. (a) N = 10, (b) N = 15, (c) N = 20. For all Figures, the x-axis corresponds to log(P(D|H_i)), the y-axis the number of errors

Figure 7

The inferred GRN by both BOLS and SBL are compared with the same expression data used in Table 2. (a) A GRN by BOLS, (b) A GRN by SBL, (c) The inferred interactions both by BOLS and SBL, (d) The inferred interactions only by BOLS, (e) The inferred interactions only by SBL. For all figures, the solid line correspond the inferred interactions which are identified as known physical or genetic interactions from the BioGRID database, and the dashed line the unknown interactions.