With the increasing availability of gene sets and pathway resources, novel approaches that combine both resources to reconstruct networks from gene sets are of interest. Currently, few computational approaches explore the search space of candidate networks using a parallel search. In particular, search agents employed by evolutionary computational approaches may better escape false peaks compared to previous approaches. It may also be hypothesized that gene sets may model signal transduction events, which refer to linear chains or cascades of reactions starting at the cell membrane and ending at the cell nucleus. These events may be indirectly observed as a set of unordered and overlapping gene sets. Thus, the goal is to reverse engineer the order information within each gene set to reconstruct the underlying source network using prior knowledge to limit the search space. We propose the Gene Set Cultural Algorithm (GSCA) to reconstruct networks from unordered gene sets. We introduce a robust heuristic based on the arborescence of a directed graph that performs well for random topological sort orderings across gene sets simulated for four E. coli networks and five Insilico networks from the DREAM3 and DREAM4 initiatives, respectively. Furthermore, GSCA performs favorably when reconstructing networks from randomly ordered gene sets for the aforementioned networks. Finally, we note that from a set of 23 gene sets discretized from a set of 300 S. cerevisiae expression profiles, GSCA reconstructs a network preserving most of the weak order information found in the KEGG Cell Cycle pathway, which was used as prior knowledge.

MOTIVATION: A plethora of bioinformatics analysis has led to the discovery of numerous gene sets, which can be interpreted as discrete measurements emitted from latent signaling pathways. Their potential to infer signaling pathway structures, however, has not been sufficiently exploited. Existing methods accommodating discrete data do not explicitly consider signal cascading mechanisms that characterize a signaling pathway. Novel computational methods are thus needed to fully utilize gene sets and broaden the scope from focusing only on pairwise interactions to the more general cascading events in the inference of signaling pathway structures. RESULTS: We propose a gene set based simulated annealing (SA) algorithm for the reconstruction of signaling pathway structures. A signaling pathway structure is a directed graph containing up to a few hundred nodes and many overlapping signal cascades, where each cascade represents a chain of molecular interactions from the cell surface to the nucleus. Gene sets in our context refer to discrete sets of genes participating in signal cascades, the basic building blocks of a signaling pathway, with no prior information about gene orderings in the cascades. From a compendium of gene sets related to a pathway, SA aims to search for signal cascades that characterize the optimal signaling pathway structure. In the search process, the extent of overlap among signal cascades is used to measure the optimality of a structure. Throughout, we treat gene sets as random samples from a first-order Markov chain model. We evaluated the performance of SA in three case studies. In the first study conducted on 83 KEGG pathways, SA demonstrated a significantly better performance than Bayesian network methods. Since both SA and Bayesian network methods accommodate discrete data, use a 'search and score' network learning strategy and output a directed network, they can be compared in terms of performance and computational time. In the second study, we compared SA and Bayesian network methods using four benchmark datasets from DREAM. In our final study, we showcased two context-specific signaling pathways activated in breast cancer. AVAILABILITY: Source codes are available from http://dl.dropbox.com/u/16000775/sa_sc.zip.

Reconstruction of signaling pathway structures is essential to decipher complex regulatory relationships in living cells. Existing approaches often rely on unrealistic biological assumptions and do not explicitly consider signal transduction mechanisms. Signal transduction events refer to linear cascades of reactions from cell surface to nucleus and characterize a signaling pathway. We propose a novel approach, Gene Set Gibbs Sampling, to reverse engineer signaling pathway structures from gene sets related to pathways. We hypothesize that signaling pathways are structurally an ensemble of overlapping linear signal transduction events which we encode as Information Flows (IFs). We infer signaling pathway structures from gene sets, referred to as Information Flow Gene Sets (IFGSs), corresponding to these events. Thus, an IFGS only reflects which genes appear in the underlying IF but not their ordering. GSGS offers a Gibbs sampling procedure to reconstruct the underlying signaling pathway structure by sequentially inferring IFs from the overlapping IFGSs related to the pathway. In the proof-of-concept studies, our approach is shown to outperform existing network inference approaches using data generated from benchmark networks in DREAM. We perform a sensitivity analysis to assess the robustness of our approach. Finally, we implement GSGS to reconstruct signaling mechanisms in breast cancer cells.

Estimation of pairwise correlation from incomplete and replicated molecular profiling data is an ubiquitous problem in pattern discovery analysis, such as clustering and networking. However, existing methods solve this problem by ad hoc data imputation, followed by aveGation coefficient type approaches, which might annihilate important patterns present in the molecular profiling data. Moreover, these approaches do not consider and exploit the underlying experimental design information that specifies the replication mechanisms. We develop an Expectation-Maximization (EM) type algorithm to estimate the correlation structure using incomplete and replicated molecular profiling data with a priori known replication mechanism. The approach is sufficiently generalized to be applicable to any known replication mechanism. In case of unknown replication mechanism, it is reduced to the parsimonious model introduced previously. The efficacy of our approach was first evaluated by comprehensively comparing various bivariate and multivariate imputation approaches using simulation studies. Results from real-world data analysis further confirmed the superior performance of the proposed approach to the commonly used approaches, where we assessed the robustness of the method using data sets with up to 30 percent missing values.

Correlation-based pattern discovery from replicated molecular profiling data enables essential data mining tasks, such as discovering biomolecule association networks and functional modules. Unfortunately, the existing approaches are not tailored to analyze replicated measurements, which is further confused by various replication mechanisms. With few exception, existing approaches average or summarize over replicates of diverse magnitude, which might wipe out important patterns of low magnitude and/or cancel out patterns of similar magnitude. The averaging or summarizing procedure, originally targeted for univariate differential expression analysis, has become a nuisance in multivariate correlation-based pattern discovery. Multivariate approaches that treat each replicate individually provide a promising alternative. Here we propose a multivariate parsimonious correlation model for replicated molecular profiling data with blind replication mechanisms, and a constrained (less parsimonious) correlation model explicitly considers the informed replication mechanisms. We derive a generalized formula for correlation-based pattern discovery for both blind and informed replication mechanisms. To promote it's use among the biomedical research community, we develop a correlation-based pattern discovery software with graphical user interface (GUI) for analyzing replicated molecular profiling data.

Estimating the correlation structure of a gene set is an ubiquitous problem in many pattern analyses of replicated molecular profiling data. However, the commonly used Maximum Likelihood Estimates (MLE) approaches, do not automatically accommodate replicated measurements. Often, an ad hoc step of preprocessing e.g. averaging, either weighted, un-weighted or something in between is needed, which might wipe out important patterns of low magnitude and/or cancel out patterns of similar magnitude. We treat each replicate individually as a random variable and design a finite mixture model to estimate an optimal correlation structure from replicated molecular profiling data. Assuming that the measurements are independently, identically distributed (i.i.d.) samples from a mixture of two multivariate normal distributions, one with a constrained set of parameters and the other with an unconstrained parameter structure, we employ an Expectation-Maximization (EM) algorithm to estimate component parameters. We carry out a comparative study, including both simulations and real-world data analysis, to assess the estimation of correlation structure using the proposed model and the constrained model given by the first component of the mixture. The two models were further tested for their performances in clustering real-world data. The mixture model approach is shown to have an overall better performance.