Algorithm to identify the optimal perturbation based on the net basin-of-state of perturbed states in Boolean network.

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. Here, the authors investigate the 1 bit perturbation, which falls under the category of structural intervention. The authors' idea is that, if and only if a perturbed state evolves from a desirable attractor to an undesirable attractor or from an undesirable attractor to a desirable attractor, then the size of basin of attractor of a desirable attractor may decrease or increase. In this case, if the authors obtain the net BOS of the perturbed states, they can quickly obtain the optimal 1 bit perturbation by finding the maximum value of perturbation gain. Results from both synthetic and real biological networks show that the proposed algorithm is not only simpler and but also performs better than the previous basin-of-states (BOS)-based algorithm by Hu et al..

Signaling pathway impact analysis by incorporating the importance and specificity of genes (SPIA-IS).

rlying biology of differentially expressed genes and proteins. Although various approaches have been proposed to identify cancer-related pathways, most of them only partially consider the influence of those differentially expressed genes, such as the gene numbers, their perturbation in the signaling transduction, and the interaction between genes. Signaling-pathway impact analysis (SPIA) provides a convenient framework which considers both the classical enrichment analysis and the actual perturbation on a given pathway. In this study, we extended previous proposed SPIA by incorporating the importance and specificity of genes (SPIA-IS). We applied this approach to six datasets for colorectal cancer, lung cancer, and pancreatic cancer. Results from these datasets showed that the proposed SPIA-IS could effectively improve the performance of the original SPIA in identifying cancer-related pathways.

Signalling pathway impact analysis based on the strength of interaction between genes.

Signalling pathway analysis is a popular approach that is used to identify significant cancer-related pathways based on differentially expressed genes (DEGs) from biological experiments. The main advantage of signalling pathway analysis lies in the fact that it assesses both the number of DEGs and the propagation of signal perturbation in signalling pathways. However, this method simplifies the interactions between genes by categorising them only as activation (+1) and suppression (-1), which does not encompass the range of interactions in real pathways, where interaction strength between genes may vary. In this study, the authors used newly developed signalling pathway impact analysis (SPIA) methods, SPIA based on Pearson correlation coefficient (PSPIA), and mutual information (MSPIA), to measure the interaction strength between pairs of genes. In analyses of a colorectal cancer dataset, a lung cancer dataset, and a pancreatic cancer dataset, PSPIA and MSPIA identified more candidate cancer-related pathways than were identified by SPIA. Generally, MSPIA performed better than PSPIA.

An efficient algorithm to identify the optimal one-bit perturbation based on the basin-of-state size of Boolean networks.

Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. In this paper, we investigate the less-studied one-bit perturbation, which falls under the category of structural intervention. Previous works focused on finding the optimal one-bit perturbation to maximally alter the steady-state distribution (SSD) of undesirable states through matrix perturbation theory. However, the application of the SSD is limited to Boolean networks with about ten genes. In 2007, Xiao et al. proposed to search the optimal one-bit perturbation by altering the sizes of the basin of attractions (BOAs). However, their algorithm requires close observation of the state-transition diagram. In this paper, we propose an algorithm that efficiently determines the BOA size after a perturbation. Our idea is that, if we construct the basin of states for all states, then the size of the BOA of perturbed networks can be obtained just by updating the paths of the states whose transitions have been affected. Results from both synthetic and real biological networks show that the proposed algorithm performs better than the exhaustive SSD-based algorithm and can be applied to networks with about 25 genes.

Detecting small attractors of large Boolean networks by function-reduction-based strategy.

Boolean networks (BNs) are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behaviour of systems. A central aim of Boolean-network analysis is to find attractors that correspond to various cellular states, such as cell types or the stage of cell differentiation. This problem is NP-hard and various algorithms have been used to tackle it with considerable success. The idea is that a singleton attractor corresponds to n consistent subsequences in the truth table. To find these subsequences, the authors gradually reduce the entire truth table of Boolean functions by extending a partial gene activity profile (GAP). Not only does this process delete inconsistent subsequences in truth tables, it also directly determines values for some nodes not extended, which means it can abandon the partial GAPs that cannot lead to an attractor as early as possible. The results of simulation show that the proposed algorithm can detect small attractors with length p = 4 in BNs of up to 200 nodes with average indegree K = 2.

Subpathway Analysis based on Signaling-Pathway Impact Analysis of Signaling Pathway.

Pathway analysis is a common approach to gain insight from biological experiments. Signaling-pathway impact analysis (SPIA) is one such method and combines both the classical enrichment analysis and the actual perturbation on a given pathway. Because this method focuses on a single pathway, its resolution generally is not very high because the differentially expressed genes may be enriched in a local region of the pathway. In the present work, to identify cancer-related pathways, we incorporated a recent subpathway analysis method into the SPIA method to form the "sub-SPIA method." The original subpathway analysis uses the k-clique structure to define a subpathway. However, it is not sufficiently flexible to capture subpathways with complex structure and usually results in many overlapping subpathways. We therefore propose using the minimal-spanning-tree structure to find a subpathway. We apply this approach to colorectal cancer and lung cancer datasets, and our results show that sub-SPIA can identify many significant pathways associated with each specific cancer that other methods miss. Based on the entire pathway network in the Kyoto Encyclopedia of Genes and Genomes, we find that the pathways identified by sub-SPIA not only have the largest average degree, but also are more closely connected than those identified by other methods. This result suggests that the abnormality signal propagating through them might be responsible for the specific cancer or disease.

Learning restricted Boolean network model by time-series data.

Restricted Boolean networks are simplified Boolean networks that are required for either negative or positive regulations between genes. Higa et al. (BMC Proc 5:S5, 2011) proposed a three-rule algorithm to infer a restricted Boolean network from time-series data. However, the algorithm suffers from a major drawback, namely, it is very sensitive to noise. In this paper, we systematically analyze the regulatory relationships between genes based on the state switch of the target gene and propose an algorithm with which restricted Boolean networks may be inferred from time-series data. We compare the proposed algorithm with the three-rule algorithm and the best-fit algorithm based on both synthetic networks and a well-studied budding yeast cell cycle network. The performance of the algorithms is evaluated by three distance metrics: the normalized-edge Hamming distance [Formula: see text], the normalized Hamming distance of state transition [Formula: see text], and the steady-state distribution distance µ (ssd). Results show that the proposed algorithm outperforms the others according to both [Formula: see text] and [Formula: see text], whereas its performance according to µ (ssd) is intermediate between best-fit and the three-rule algorithms. Thus, our new algorithm is more appropriate for inferring interactions between genes from time-series data.

Using the minimum description length principle to reduce the rate of false positives of best-fit algorithms.

The inference of gene regulatory networks is a core problem in systems biology. Many inference algorithms have been proposed and all suffer from false positives. In this paper, we use the minimum description length (MDL) principle to reduce the rate of false positives for best-fit algorithms. The performance of these algorithms is evaluated via two metrics: the normalized-edge Hamming distance and the steady-state distribution distance. Results for synthetic networks and a well-studied budding-yeast cell cycle network show that MDL-based filtering is more effective than filtering based on conditional mutual information (CMI). In addition, MDL-based filtering provides better inference than the MDL algorithm itself.