Reverse engineering gene regulatory network from microarray data using linear time-variant model.

BACKGROUND: Gene regulatory network is an abstract mapping of gene regulations in living cells that can help to predict the system behavior of living organisms. Such prediction capability can potentially lead to the development of improved diagnostic tests and therapeutics. DNA microarrays, which measure the expression level of thousands of genes in parallel, constitute the numeric seed for the inference of gene regulatory networks. In this paper, we have proposed a new approach for inferring gene regulatory networks from time-series gene expression data using linear time-variant model. Here, Self-Adaptive Differential Evolution, a versatile and robust Evolutionary Algorithm, is used as the learning paradigm. RESULTS: To assess the potency of the proposed work, a well known nonlinear synthetic network has been used. The reconstruction method has inferred this synthetic network topology and the associated regulatory parameters with high accuracy from both the noise-free and noisy time-series data. For validation purposes, the proposed approach is also applied to the simulated expression dataset of cAMP oscillations in Dictyostelium discoideum and has proved it's strength in finding the correct regulations. The strength of this work has also been verified by analyzing the real expression dataset of SOS DNA repair system in Escherichia coli and it has succeeded in finding more correct and reasonable regulations as compared to various existing works. CONCLUSION: By the proposed approach, the gene interaction networks have been inferred in an efficient manner from both the synthetic, simulated cAMP oscillation expression data and real expression data. The computational time of this approach is also considerably smaller, which makes it to be more suitable for larger network reconstruction. Thus the proposed approach can serve as an initiate for the future researches regarding the associated area.

Inferring gene regulatory networks using differential evolution with local search heuristics.

We present a memetic algorithm for evolving the structure of biomolecular interactions and inferring the effective kinetic parameters from the time series data of gene expression using the decoupled Ssystem formalism. We propose an Information Criteria based fitness evaluation for gene network model selection instead of the conventional Mean Squared Error (MSE) based fitness evaluation. A hill-climbing local-search method has been incorporated in our evolutionary algorithm for efficiently attaining the skeletal architecture which is most frequently observed in biological networks. The suitability of the method is tested in gene circuit reconstruction experiments, varying the network dimension and/or characteristics, the amount of gene expression data used for inference and the noise level present in expression profiles. The reconstruction method inferred the network topology and the regulatory parameters with high accuracy. Nevertheless, the performance is limited to the amount of expression data used and the noise level present in the data. The proposed fitness function has been found more suitable for identifying correct network topology and for estimating the accurate parameter values compared to the existing ones. Finally, we applied the methodology for analyzing the cell-cycle gene expression data of budding yeast and reconstructed the network of some key regulators.

MetaClustering: discovery of the different sample clusterings in gene expression data.

Clustering of the samples is a standard procedure for the analysis of gene expression data, for instance to discover cancer subtypes. However, more than one biologically meaningful clustering can exist, depending on the genes chosen. We propose here to group the genes in function of the clustering of the samples they fit. This allows to determine directly the different clusterings of the samples present in the data. As a clustering is a structure, genes belonging to the same group are functions of the same structure. Hence, the determination of groups of genes which support the same clustering could also be viewed as the detection of non-linearly linked genes. MetaClustering was applied successfully to simulated data. It also recovered the known clustering of real cancer data, which was impossible using the complete set of genes. Finally, it clustered together cell-cycle genes, showing its ability to group genes related in a non-linear way.

Pulse Detecting Genetic Circuit - A New Design Approach.

A robust cellular counter could enable synthetic biologists to design complex circuits with diverse behaviors. The existing synthetic-biological counters, responsive to the beginning of the pulse, are sensitive to the pulse duration. Here we present a pulse detecting circuit that responds only at the falling edge of a pulse-analogous to negative edge triggered electric circuits. As biological events do not follow precise timing, use of such a pulse detector would enable the design of robust asynchronous counters which can count the completion of events. This transcription-based pulse detecting circuit depends on the interaction of two co-expressed lambdoid phage-derived proteins: the first is unstable and inhibits the regulatory activity of the second, stable protein. At the end of the pulse the unstable inhibitor protein disappears from the cell and the second protein triggers the recording of the event completion. Using stochastic simulation we showed that the proposed design can detect the completion of the pulse irrespective to the pulse duration. In our simulation we also showed that fusing the pulse detector with a phage lambda memory element we can construct a counter which can be extended to count larger numbers. The proposed design principle is a new control mechanism for synthetic biology which can be integrated in different circuits for identifying the completion of an event.

Reverse engineering genetic networks using evolutionary computation.

This paper proposes an improved evolutionary method for constructing the underlying network structure and inferring effective kinetic parameters from the time series data of gene expression using decoupled S-system formalism. We employed Trigonometric Differential Evolution (TDE) as the optimization engine of our algorithm for capturing the dynamics in gene expression data. A more effective fitness function for attaining the sparse structure, which is the hallmark of biological networks, has been applied. Experiments on artificial genetic network show the power of the algorithm in constructing the network structure and predicting the regulatory parameters. The method is used to evaluate interactions between genes in the SOS signaling pathway in Escherichia coli using gene expression data.

Gene selection for classification of cancers using probabilistic model building genetic algorithm.

Recently, DNA microarray-based gene expression profiles have been used to correlate the clinical behavior of cancers with the differential gene expression levels in cancerous and normal tissues. To this end, after selection of some predictive genes based on signal-to-noise (S2N) ratio, unsupervised learning like clustering and supervised learning like k-nearest neighbor (k NN) classifier are widely used. Instead of S2N ratio, adaptive searches like Probabilistic Model Building Genetic Algorithm (PMBGA) can be applied for selection of a smaller size gene subset that would classify patient samples more accurately. In this paper, we propose a new PMBGA-based method for identification of informative genes from microarray data. By applying our proposed method to classification of three microarray data sets of binary and multi-type tumors, we demonstrate that the gene subsets selected with our technique yield better classification accuracy.

Evolving robust gene regulatory networks.

Design and implementation of robust network modules is essential for construction of complex biological systems through hierarchical assembly of 'parts' and 'devices'. The robustness of gene regulatory networks (GRNs) is ascribed chiefly to the underlying topology. The automatic designing capability of GRN topology that can exhibit robust behavior can dramatically change the current practice in synthetic biology. A recent study shows that Darwinian evolution can gradually develop higher topological robustness. Subsequently, this work presents an evolutionary algorithm that simulates natural evolution in silico, for identifying network topologies that are robust to perturbations. We present a Monte Carlo based method for quantifying topological robustness and designed a fitness approximation approach for efficient calculation of topological robustness which is computationally very intensive. The proposed framework was verified using two classic GRN behaviors: oscillation and bistability, although the framework is generalized for evolving other types of responses. The algorithm identified robust GRN architectures which were verified using different analysis and comparison. Analysis of the results also shed light on the relationship among robustness, cooperativity and complexity. This study also shows that nature has already evolved very robust architectures for its crucial systems; hence simulation of this natural process can be very valuable for designing robust biological systems.

Inference of gene regulatory networks by means of dynamic differential Bayesian networks and nonparametric regression.

We propose a dynamic differential Bayesian networks (DDBNs) and nonparametric regression model. This model is an extended model of traditional dynamic Bayesian networks (DBNs), which can incorporate temporal information in a natural way and directly handle real-valued data obtained from microarrays without any transformation. In addition, it can cope with differential information between gene expression levels, without any loss to the traditional advantage, i.e., the capability of estimating non-linear relationships between genes. We apply DDBNs to analyze simulated data and real data, i.e., Saccharomyces cerevisiae cell cycle gene expression data. We have confirmed the effectiveness of our approach in the sense that some edges have been successfully detected only by DDBNs, not by DBNs.

Construction of genetic network using evolutionary algorithm and combined fitness function.

This paper proposes a method to capture the dynamics in gene expression data using S-system formalism and construct genetic network models. Our purposed method exploits the probabilistic heuristic search and divide-and-conquer approach to estimate the network structure. In evaluating the network structure, we attempt a primitive integration of other knowledge to the statistical criterion. The Z-score is used to analyze the robust and significant parameters from stochastic search results. We evaluated the proposed method on artificially generated data and E.coli mRNA expression data.

Layout search of a gene regulatory network for 3-D visualization.

In recent years, base sequences have been increasingly unscrambled through attempts represented by the human genome project. Accordingly, the estimation of the genetic network has been accelerated. However, no definitive method has become available for drawing a large effective graph. This paper proposes a method which allows for coping with an increase in the number of nodes by laying out genes on planes of several layers and then overlapping these planes. This layout involves an optimization problem which requires maximizing the fitness function. To demonstrate the effectiveness of our approach, we show some graphs using actual data on 82 genes and 552 genes. We also describe how to lay out nodes by means of stochastic searches, e.g., stochastic hill-climbing and incremental methods. The experimental results show the superiority and usefulness of two search methods in comparison with the simple random search.

Inference of Euler angles for single particle analysis by using Genetic Algorithms.

Single particle analysis is one of the methods for structural studies of protein and macromolecules developed in image analysis on electron microscopy. Reconstructing 3D structure from microscope images is not an easy analysis because of the low resolution of images and lack of the directional information of images in 3D structure. To improve the resolution, different projections are aligned, classified and averaged. Inferring the orientations of these images is so difficult that the task of reconstructing 3D structures depends upon the experience of researchers. But recently, a method to reconstruct 3D structures is automatically devised. In this paper, we propose a new method for determining Euler angles of projections by applying Genetic Algorithms (i.e., GAs). We empirically show that the proposed approach has improved the previous one in terms of computational time and acquired precision.

Polynomial harmonic GMDH learning networks for time series modeling.

This paper presents a constructive approach to neural network modeling of polynomial harmonic functions. This is an approach to growing higher-order networks like these build by the multilayer GMDH algorithm using activation polynomials. Two contributions for enhancement of the neural network learning are offered: (1) extending the expressive power of the network representation with another compositional scheme for combining polynomial terms and harmonics obtained analytically from the data; (2) space improving the higher-order network performance with a backpropagation algorithm for further gradient descent learning of the weights, initialized by least squares fitting during the growing phase. Empirical results show that the polynomial harmonic version phGMDH outperforms the previous GMDH, a Neurofuzzy GMDH and traditional MLP neural networks on time series modeling tasks. Applying next backpropagation training helps to achieve superior polynomial network performances.

Inference of Euler angles for single-particle analysis by means of evolutionary algorithms.

Single-particle analysis is one of the methods for structural studies of protein and macromolecules; it requires advanced image analysis of electron micrographics. Reconstructing three-dimensional (3D) structure from microscope images is not an easy analysis because of the low image resolution of images and lack of the directional information of images in 3D structure. To improve the resolution, different projections are aligned, classified, and averaged. Inferring the orientations of these images is so difficult that the task of reconstructing 3D structures depends upon the experience of researchers. But recently, a method to reconstruct 3D structures was automatically devised. In this paper, we propose a new method for determining Euler angles of projections by applying genetic algorithms. We empirically show that the proposed approach has improved the previous one in terms of computational time and acquired precision.

Genetic programming of polynomial harmonic networks using the discrete Fourier transform.

This paper presents a genetic programming system that evolves polynomial harmonic networks. These are multilayer feed-forward neural networks with polynomial activation functions. The novel hybrids assume that harmonics with non-multiple frequencies may enter as inputs the activation polynomials. The harmonics with non-multiple, irregular frequencies are derived analytically using the discrete Fourier transform. The polynomial harmonic networks have tree-structured topology which makes them especially suitable for evolutionary structural search. Empirical results show that this hybrid genetic programming system outperforms an evolutionary system manipulating polynomials, the traditional Koza-style genetic programming, and the harmonic GMDH network algorithm on processing time series.

Prediction of cancer class with majority voting genetic programming classifier using gene expression data.

In order to get a better understanding of different types of cancers and to find the possible biomarkers for diseases, recently, many researchers are analyzing the gene expression data using various machine learning techniques. However, due to a very small number of training samples compared to the huge number of genes and class imbalance, most of these methods suffer from overfitting. In this paper, we present a majority voting genetic programming classifier (MVGPC) for the classification of microarray data. Instead of a single rule or a single set of rules, we evolve multiple rules with genetic programming (GP) and then apply those rules to test samples to determine their labels with majority voting technique. By performing experiments on four different public cancer data sets, including multiclass data sets, we have found that the test accuracies of MVGPC are better than those of other methods, including AdaBoost with GP. Moreover, some of the more frequently occurring genes in the classification rules are known to be associated with the types of cancers being studied in this paper.