MOTIVATION: It is a challenging problem in systems biology to infer both the network structure and dynamics of a gene regulatory network from steady-state gene expression data. Some methods based on Boolean or differential equation models have been proposed but they were not efficient in inference of large-scale networks. Therefore, it is necessary to develop a method to infer the network structure and dynamics accurately on large-scale networks using steady-state expression. RESULTS: In this study, we propose a novel constrained genetic algorithm-based Boolean network inference (CGA-BNI) method where a Boolean canalyzing update rule scheme was employed to capture coarse-grained dynamics. Given steady-state gene expression data as an input, CGA-BNI identifies a set of path consistency-based constraints by comparing the gene expression level between the wild-type and the mutant experiments. It then searches Boolean networks which satisfy the constraints and induce attractors most similar to steady-state expressions. We devised a heuristic mutation operation for faster convergence and implemented a parallel evaluation routine for execution time reduction. Through extensive simulations on the artificial and the real gene expression datasets, CGA-BNI showed better performance than four other existing methods in terms of both structural and dynamics prediction accuracies. Taken together, CGA-BNI is a promising tool to predict both the structure and the dynamics of a gene regulatory network when a highest accuracy is needed at the cost of sacrificing the execution time. AVAILABILITY AND IMPLEMENTATION: Source code and data are freely available at https://github.com/csclab/CGA-BNI. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: In systems biology, it is challenging to accurately infer a regulatory network from time-series gene expression data, and a variety of methods have been proposed. Most of them were computationally inefficient in inferring very large networks, though, because of the increasing number of candidate regulatory genes. Although a recent approach called GABNI (genetic algorithm-based Boolean network inference) was presented to resolve this problem using a genetic algorithm, there is room for performance improvement because it employed a limited representation model of regulatory functions.In this regard, we devised a novel genetic algorithm combined with a neural network for the Boolean network inference, where a neural network is used to represent the regulatory function instead of an incomplete Boolean truth table used in the GABNI. In addition, our new method extended the range of the time-step lag parameter value between the regulatory and the target genes for more flexible representation of the regulatory function. Extensive simulations with the gene expression datasets of the artificial and real networks were conducted to compare our method with five well-known existing methods including GABNI. Our proposed method significantly outperformed them in terms of both structural and dynamics accuracy. CONCLUSION: Our method can be a promising tool to infer a large-scale Boolean regulatory network from time-series gene expression data. AVAILABILITY AND IMPLEMENTATION: The source code is freely available at https://github.com/kwon-uou/NNBNI. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Motivation: Inferring a gene regulatory network from time-series gene expression data is a fundamental problem in systems biology, and many methods have been proposed. However, most of them were not efficient in inferring regulatory relations involved by a large number of genes because they limited the number of regulatory genes or computed an approximated reliability of multivariate relations. Therefore, an improved method is needed to efficiently search more generalized and scalable regulatory relations. Results: In this study, we propose a genetic algorithm-based Boolean network inference (GABNI) method which can search an optimal Boolean regulatory function of a large number of regulatory genes. For an efficient search, it solves the problem in two stages. GABNI first exploits an existing method, a mutual information-based Boolean network inference (MIBNI), because it can quickly find an optimal solution in a small-scale inference problem. When MIBNI fails to find an optimal solution, a genetic algorithm (GA) is applied to search an optimal set of regulatory genes in a wider solution space. In particular, we modified a typical GA framework to efficiently reduce a search space. We compared GABNI with four well-known inference methods through extensive simulations on both the artificial and the real gene expression datasets. Our results demonstrated that GABNI significantly outperformed them in both structural and dynamics accuracies. Conclusion: The proposed method is an efficient and scalable tool to infer a Boolean network from time-series gene expression data. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Biological networks are composed of molecular components and their interactions represented by nodes and edges, respectively, in a graph model. Based on this model, there were many studies with respect to effects of node-based mutations on the network dynamics, whereas little attention was paid to edgetic mutations so far. RESULTS: In this paper, we defined an edgetic sensitivity measure that quantifies how likely a converging attractor is changed by edge-removal mutations in a Boolean network model. Through extensive simulations based on that measure, we found interesting properties of highly sensitive edges in both random and real signaling networks. First, the sensitive edges in random networks tend to link two end nodes both of which are susceptible to node-knockout mutations. Interestingly, it was analogous to an observation that the sensitive edges in human signaling networks are likely to connect drug-target genes. We further observed that the edgetic sensitivity predicted drug-targets better than the node-based sensitivity. In addition, the sensitive edges showed distinguished structural characteristics such as a lower connectivity, more involving feedback loops and a higher betweenness. Moreover, their gene-ontology enrichments were clearly different from the other edges. We also observed that genes incident to the highly sensitive interactions are more central by forming a considerably large connected component in human signaling networks. Finally, we validated our approach by showing that most sensitive interactions are promising edgetic drug-targets in p53 cancer and T-cell apoptosis networks. Taken together, the edgetic sensitivity is valuable to understand the complex dynamics of signaling networks. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

It has been known that the robust behavior of a cellular signaling network is strongly related to the structural characteristics of the network, such as connectivity, the number of feedback loops, and the number of feed-forward loops. Previous studies proved such relationships through dynamical simulations of various random network models. Most of them, however, focused on robustness against a single node mutation. Considering that complex diseases such as cancer are mostly caused by simultaneous dysfunction of multiple genes, it is needed to investigate the robustness of a network against multiple node mutations. In this paper, we investigated the robustness of a network against multiple node mutations through extensive simulations on the basis of Boolean network models. We found that the robustness against multiple mutations is, in most cases, weaker than the robustness against a single node mutation on average. Moreover, we found that the robustness against multiple mutations is strongly positively correlated with the robustness against single mutation. The difference between the multiple- and single-mutation robustness became larger as the number of mutated nodes increased or the number of nodes that are robust to single-mutation decreased. We further found that a node of relatively large connectivity or being involved with many feedback loops tends to be non-robust against multiple mutations. This finding is supported by the observation that poly-genic disease genes have high connectivity and are involved with a large number of feedback loops than mono-genic disease genes in a human signaling network. Together, our study shows that previous studies for a single node mutation can be extended to understand the network dynamics for multiple node mutations.

MOTIVATION: Many studies have investigated the relationship between structural properties and dynamic behaviors in biological networks. In particular, feedback loop (FBL) and feedforward loop (FFL) structures have received a great deal of attention. One interesting and common property of FBL and FFL structures is their coherency of coupling. However, the role of coherent FFLs in relation to network robustness is not fully known, whereas that of coherent FBLs has been well established. RESULTS: To establish that coherent FFLs are abundant in biological networks, we examined gene regulatory and signaling networks and found that FFLs are ubiquitous, and are in a coherently coupled form. This result was also observed in the species-based signaling networks that are integrated from KEGG database. By using a random Boolean network model, we demonstrated that these coherent FFLs can improve network robustness against update-rule perturbations. In particular, we found that coherent FFLs increase robustness because these structures induce downstream nodes to be robust against update-rule perturbations. Therefore, coherent FFLs can be considered as a design principle of human signaling networks that improve network robustness against update-rule perturbations.

MOTIVATION: In general, diseases are more likely to be comorbid if they share associated genes or molecular interactions in a cellular process. However, there are still a number of pairs of diseases which show relatively high comorbidity but do not share any associated genes or interactions. This observation raises the need for a novel factor which can explain the underlying mechanism of comorbidity. We here consider a feedback loop (FBL) structure ubiquitously found in the human cell signaling network as a key motif to explain the comorbidity phenomenon, since it is well known to have effects on network dynamics. RESULTS: For every pair of diseases, we examined its comorbidity and length of all FBLs involved by the disease-associated genes in the human cell signaling network. We found that there is a negative relationship between comorbidity and length of involved FBLs. This indicates that a disease pair is more likely to comorbid if they are connected with FBLs of shorter length. We additionally showed that such a negative relationship is more obvious when the number of positive involved FBLs is larger than that of negative involved FBLs. Moreover, we observed that the negative relationship between comorbidity and length of involved FBLs holds especially for disease pairs that do not share any disease-associated genes. Finally, we proved all these results through intensive simulations, based on a Boolean network model. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at BioInformatics online.

SUMMARY: NetDS is a novel Cytoscape plugin that conveniently simulates dynamics related to robustness, and examines structural properties with respect to feedforward/feedback loops. It can evaluate how robustly a network sustains a stable state against mutations by employing a Boolean network model. In addition, the plugin can examine all feedforward/feedback loops appearing in a network and determine whether or not a pair of loops is coupled. Random networks can also be generated to evaluate whether or not an interesting finding in real biological networks is significantly random. AVAILABILITY: NetDS is freely available for non-commercial purposes at http://netds.sourceforge.net/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: It has been widely reported that biological networks are robust against perturbations such as mutations. On the contrary, it has also been known that biological networks are often fragile against unexpected mutations. There is a growing interest in these intriguing observations and the underlying design principle that causes such robust but fragile characteristics of biological networks. For relatively small networks, a feedback loop has been considered as an important motif for realizing the robustness. It is still, however, not clear how a number of coupled feedback loops actually affect the robustness of large complex biological networks. In particular, the relationship between fragility and feedback loops has not yet been investigated till now. RESULTS: Through extensive computational experiments, we found that networks with a larger number of positive feedback loops and a smaller number of negative feedback loops are likely to be more robust against perturbations. Moreover, we found that the nodes of a robust network subject to perturbations are mostly involved with a smaller number of feedback loops compared with the other nodes not usually subject to perturbations. This topological characteristic eventually makes the robust network fragile against unexpected mutations at the nodes not previously exposed to perturbations.

MOTIVATION: It is widely accepted that cell signaling networks have been evolved to be robust against perturbations. To investigate the topological characteristics resulting in such robustness, we have examined large-scale signaling networks and found that a number of feedback loops are present mostly in coupled structures. In particular, the coupling was made in a coherent way implying that same types of feedback loops are interlinked together. RESULTS: We have investigated the role of such coherently coupled feedback loops through extensive Boolean network simulations and found that a high proportion of coherent couplings can enhance the robustness of a network against its state perturbations. Moreover, we found that the robustness achieved by coherently coupled feedback loops can be kept evolutionarily stable. All these results imply that the coherent coupling of feedback loops might be a design principle of cell signaling networks devised to achieve the robustness.

BACKGROUND: Many biological networks such as protein-protein interaction networks, signaling networks, and metabolic networks have topological characteristics of a scale-free degree distribution. Preferential attachment has been considered as the most plausible evolutionary growth model to explain this topological property. Although various studies have been undertaken to investigate the structural characteristics of a network obtained using this growth model, its dynamical characteristics have received relatively less attention. RESULTS: In this paper, we focus on the robustness of a network that is acquired during its evolutionary process. Through simulations using Boolean network models, we found that preferential attachment increases the number of coupled feedback loops in the course of network evolution. Whereas, if networks evolve to have more coupled feedback loops rather than following preferential attachment, the resulting networks are more robust than those obtained through preferential attachment, although both of them have similar degree distributions. CONCLUSION: The presented analysis demonstrates that coupled feedback loops may play an important role in network evolution to acquire robustness. The result also provides a hint as to why various biological networks have evolved to contain a number of coupled feedback loops.

BACKGROUND: A number of studies on biological networks have been carried out to unravel the topological characteristics that can explain the functional importance of network nodes. For instance, connectivity, clustering coefficient, and shortest path length were previously proposed for this purpose. However, there is still a pressing need to investigate another topological measure that can better describe the functional importance of network nodes. In this respect, we considered a feedback loop which is ubiquitously found in various biological networks. RESULTS: We discovered that the number of feedback loops (NuFBL) is a crucial measure for evaluating the importance of a network node and verified this through a signal transduction network in the hippocampal CA1 neuron of mice as well as through generalized biological network models represented by Boolean networks. In particular, we observed that the proteins with a larger NuFBL are more likely to be essential and to evolve slowly in the hippocampal CA1 neuronal signal transduction network. Then, from extensive simulations based on the Boolean network models, we proved that a network node with the larger NuFBL is likely to be more important as the mutations of the initial state or the update rule of such a node made the network converge to a different attractor. These results led us to infer that such a strong positive correlation between the NuFBL and the importance of a network node might be an intrinsic principle of biological networks in view of network dynamics. CONCLUSION: The presented analysis on topological characteristics of biological networks showed that the number of feedback loops is positively correlated with the functional importance of network nodes. This result also suggests the existence of unknown feedback loops around functionally important nodes in biological networks.

The properties of symmetric fitness functions are investigated. We show that the search spaces obtained from symmetric functions have the zero-correlation structures between fitness and distance. It is also proven that symmetric functions induce a class of the hardest problems in terms of the epistasis variance and its variants. These analyses suggest that the existing quantitative measures cannot discriminate among symmetric functions, which reveals critical limitations of the measures. To take a closer look at the symmetric functions, additional analyses are performed from other viewpoints including additive separability and boundedness. It is shown that additive separability in a symmetric function is closely related to the symmetry of its subfunctions. This elucidates why most of the well-known symmetric fitness functions are additively inseparable. The properties of two-bounded symmetric functions are investigated and they are utilized in designing an efficient algorithm to check additive separability for the two-bounded functions. Throughout this paper, we heavily use the generalized Walsh transform over multary alphabets. Our results have an independent interest as a nontrivial application of the generalized Walsh analysis.

In this paper, we propose a hybrid neurogenetic system for stock trading. A recurrent neural network (NN) having one hidden layer is used for the prediction model. The input features are generated from a number of technical indicators being used by financial experts. The genetic algorithm (GA) optimizes the NN's weights under a 2-D encoding and crossover. We devised a context-based ensemble method of NNs which dynamically changes on the basis of the test day's context. To reduce the time in processing mass data, we parallelized the GA on a Linux cluster system using message passing interface. We tested the proposed method with 36 companies in NYSE and NASDAQ for 13 years from 1992 to 2004. The neurogenetic hybrid showed notable improvement on the average over the buy-and-hold strategy and the context-based ensemble further improved the results. We also observed that some companies were more predictable than others, which implies that the proposed neurogenetic hybrid can be used for financial portfolio construction.

The properties of symmetric fitness functions are investigated. We show that a well-known encoding scheme inducing symmetric functions has the non-synonymous property and the search spaces obtained from symmetric functions have the zero-correlation structures. The Walsh analysis reveals the properties of symmetric functions related to additive separability, problem difficulty measures and so on. Our results support the claim of other researchers that the search spaces with symmetry induce relatively difficult problems. The results also present some limitations of existing problem difficulty measures for symmetric fitness functions.

Function approximation or regression is the problem of finding a function that best explains the relationship between independent variables and a dependent variable from the observed data. Genetic programming has been considered a promising approach for the problem since it is possible to optimize both the functional form and the coefficients. Genetic programming has been considered a promising approach for function approximation since it is possible to optimize both the functional form and the coefficients. However, it is not easy to find an optimal set of coefficients by using only non-adjustable constant nodes in genetic programming. To overcome the problem, there have been some studies on genetic programming using adjustable parameters in linear or nonlinear models. Although the nonlinear parametric model has a merit over the linear parametric model, there have been few studies on it. In this paper, we propose a nonlinear parametric genetic programming which uses a nonlinear gradient method to estimate parameters. The most notable feature in the proposed genetic programming is that we design a parameter attachment algorithm using as few redundant parameters as possible. It showed a significant performance improvement over the traditional genetic programming approaches on real-world application problems.

In this paper, we propose a neuro-genetic stock prediction system based on financial correlation between companies. A number of input variables are produced from the relatively highly correlated companies. The genetic algorithm selects a set of informative input features among them for a recurrent neural network. It showed notable improvement over not only the buy-and-hold strategy but also the recurrent neural network using only the input variables from the target company.

Feature extraction is a process that extracts salient features from observed variables. It is considered a promising alternative to overcome the problems of weight and structure optimization in artificial neural networks. There were many nonlinear feature extraction methods using neural networks but they still have the same difficulties arisen from the fixed network topology. In this paper, we propose a novel combination of genetic algorithm and feedforward neural networks for nonlinear feature extraction. The genetic algorithm evolves the feature space by utilizing characteristics of hidden neurons. It improved remarkably the performance of neural networks on a number of real world regression and classification problems.