Inferring adaptive regulation thresholds and association rules from gene expression data through combinatorial optimization learning

There is a need to design computational methods to support the prediction of gene regulatory networks. Such models should offer both biologically-meaningful and computationally-accurate predictions, which in combination with other techniques may improve large-scale, integrative studies. This paper presents a new machine learning method for the prediction of putative regulatory associations from expression data, which exhibit properties never or only partially addressed by other techniques recently published. The method was tested on a Saccharomyces cerevisiae gene expression dataset. The results were statistically validated and compared with the relationships inferred by two machine learning approaches to gene regulatory network prediction. Furthermore, the resulting predictions were assessed using domain knowledge. The proposed algorithm may be able to accurately predict relevant biological associations between genes. One of the most relevant features of this new method is the prediction of adaptive regulation thresholds for the discretization of gene expression values, which is required prior to the rule association learning process. Moreover, an important advantage consists of its low computational cost to infer association rules. The proposed system may significantly support exploratory, large-scale studies of automated identification of potentially-relevant gene expression associations.     

一种优化的生物数据多层关联规则挖掘算法

关联规则挖掘技术是寻找基因间关系的有效手段,但现有算法未针对高通量生物数据的特点进行优化,而存在着效率低下等缺点。提出的MAGO-FP算法,使用Gene Ontology(GO)的概念分层结构,通过对FP-Growth算法的扩展,具有一定的性能优势。在此基础上,应用该算法分析了一组由S.cerevisiae酵母菌cDNA微阵列芯片产生的实验数据,发现了一些候选关联规则。并针对其中一些重要的关联规则,通过相关文献证实了其真实性,表明该算法在基因表达分析等研究中具有应用价值。     

Gene expression network reconstruction by convex feature selection when incorporating genetic perturbations

Cellular gene expression measurements contain regulatory information that can be used to discover novel network relationships. Here, we present a new algorithm for network reconstruction powered by the adaptive lasso, a theoretically and empirically well-behaved method for selecting the regulatory features of a network. Any algorithms designed for network discovery that make use of directed probabilistic graphs require perturbations, produced by either experiments or naturally occurring genetic variation, to successfully infer unique regulatory relationships from gene expression data. Our approach makes use of appropriately selected cis-expression Quantitative Trait Loci (cis-eQTL), which provide a sufficient set of independent perturbations for maximum network resolution. We compare the performance of our network reconstruction algorithm to four other approaches: the PC-algorithm, QTLnet, the QDG algorithm, and the NEO algorithm, all of which have been used to reconstruct directed networks among phenotypes leveraging QTL. We show that the adaptive lasso can outperform these algorithms for networks of ten genes and ten cis-eQTL, and is competitive with the QDG algorithm for networks with thirty genes and thirty cis-eQTL, with rich topologies and hundreds of samples. Using this novel approach, we identify unique sets of directed relationships in Saccharomyces cerevisiae when analyzing genome-wide gene expression data for an intercross between a wild strain and a lab strain. We recover novel putative network relationships between a tyrosine biosynthesis gene (TYR1), and genes involved in endocytosis (RCY1), the spindle checkpoint (BUB2), sulfonate catabolism (JLP1), and cell-cell communication (PRM7). Our algorithm provides a synthesis of feature selection methods and graphical model theory that has the potential to reveal new directed regulatory relationships from the analysis of population level genetic and gene expression data.     

Mining co-regulated gene profiles for the detection of functional associations in gene expression data

MOTIVATION: Association pattern discovery (APD) methods have been successfully applied to gene expression data. They find groups of co-regulated genes in which the genes are either up- or down-regulated throughout the identified conditions. These methods, however, fail to identify similarly expressed genes whose expressions change between up- and down-regulation from one condition to another. In order to discover these hidden patterns, we propose the concept of mining co-regulated gene profiles. Co-regulated gene profiles contain two gene sets such that genes within the same set behave identically (up or down) while genes from different sets display contrary behavior. To reduce and group the large number of similar resulting patterns, we propose a new similarity measure that can be applied together with hierarchical clustering methods. RESULTS: We tested our proposed method on two well-known yeast microarray data sets. Our implementation mined the data effectively and discovered patterns of co-regulated genes that are hidden to traditional APD methods. The high content of biologically relevant information in these patterns is demonstrated by the significant enrichment of co-regulated genes with similar functions. Our experimental results show that the Mining Attribute Profile (MAP) method is an efficient tool for the analysis of gene expression data and competitive with bi-clustering techniques.     

Inferring gene regulatory relationships by combining target-target pattern recognition and regulator-specific motif examination

Although microarray data have been successfully used for gene clustering and classification, the use of time series microarray data for constructing gene regulatory networks remains a particularly difficult task. The challenge lies in reliably inferring regulatory relationships from datasets that normally possess a large number of genes and a limited number of time points. In addition to the numerical challenge, the enormous complexity and dynamic properties of gene expression regulation also impede the progress of inferring gene regulatory relationships. Based on the accepted model of the relationship between regulator and target genes, we developed a new approach for inferring gene regulatory relationships by combining target-target pattern recognition and examination of regulator-specific binding sites in the promoter regions of putative target genes. Pattern recognition was accomplished in two steps: A first algorithm was used to search for the genes that share expression profile similarities with known target genes (KTGs) of each investigated regulator. The selected genes were further filtered by examining for the presence of regulator-specific binding sites in their promoter regions. As we implemented our approach to 18 yeast regulator genes and their known target genes, we discovered 267 new regulatory relationships, among which 15% are rediscovered, experimentally validated ones. Of the discovered target genes, 36.1% have the same or similar functions to a KTG of the regulator. An even larger number of inferred genes fall in the biological context and regulatory scope of their regulators. Since the regulatory relationships are inferred from pattern recognition between target-target genes, the method we present is especially suitable for inferring gene regulatory relationships in which there is a time delay between the expression of regulating and target genes.     

Modularized learning of genetic interaction networks from biological annotations and mRNA expression data

MOTIVATION: Inferring the genetic interaction mechanism using Bayesian networks has recently drawn increasing attention due to its well-established theoretical foundation and statistical robustness. However, the relative insufficiency of experiments with respect to the number of genes leads to many false positive inferences. RESULTS: We propose a novel method to infer genetic networks by alleviating the shortage of available mRNA expression data with prior knowledge. We call the proposed method 'modularized network learning' (MONET). Firstly, the proposed method divides a whole gene set to overlapped modules considering biological annotations and expression data together. Secondly, it infers a Bayesian network for each module, and integrates the learned subnetworks to a global network. An algorithm that measures a similarity between genes based on hierarchy, specificity and multiplicity of biological annotations is presented. The proposed method draws a global picture of inter-module relationships as well as a detailed look of intra-module interactions. We applied the proposed method to analyze Saccharomyces cerevisiae stress data, and found several hypotheses to suggest putative functions of unclassified genes. We also compared the proposed method with a whole-set-based approach and two expression-based clustering approaches.     

Bayesian learning of sparse gene regulatory networks

Differential equations (DEs) have been the most widespread formalism for gene regulatory network (GRN) modeling, as they offer natural interpretation of biological processes, easy elucidation of gene relationships, and the capability of using efficient parameter estimation methods. However, an important limitation of DEs is their requirement of O(d(2)) parameters where d is the number of genes modeled, which often causes over-parameterization for large d, leading to the over-fitting of data and dense parameter sets that are hard to interpret. This paper presents the first effort to address the over-parameterization problem by applying the sparse Bayesian learning (SBL) method to sparsify the GRN model of DEs. SBL operates on the parsimony principle, with the objective to reduce the number of effective parameters by driving the redundant parameters to zero. The resulting sparse parameter set offers three important advantages for GRN inference: first, the inferred GRNs are more plausible, since the biological counterparts are known to be sparse; second, gene relationships can be more easily elucidated from sparse sets than from dense sets; and third, the solutions become more optimal and consistent, due to the reduction in the volume of solution space. Experiments are conducted on the yeast Saccharomyces cerevisiae time-series gene expression data, in which known regulatory events related to the cell cycle G1/S phase are reliably reproduced.     

Using a State-Space Model and Location Analysis to Infer Time-Delayed Regulatory Networks

Computational gene regulation models provide a means for scientists to draw biological inferences from time-course gene expression data. Based on the state-space approach, we developed a new modeling tool for inferring gene regulatory networks, called time-delayed Gene Regulatory Networks (tdGRNs). tdGRN takes time-delayed regulatory relationships into consideration when developing the model. In addition, a priori biological knowledge from genome-wide location analysis is incorporated into the structure of the gene regulatory network. tdGRN is evaluated on both an artificial dataset and a published gene expression data set. It not only determines regulatory relationships that are known to exist but also uncovers potential new ones. The results indicate that the proposed tool is effective in inferring gene regulatory relationships with time delay. tdGRN is complementary to existing methods for inferring gene regulatory networks. The novel part of the proposed tool is that it is able to infer time-delayed regulatory relationships.     

Cross-Ontology Multi-level Association Rule Mining in the Gene Ontology

The Gene Ontology (GO) has become the internationally accepted standard for representing function, process, and location aspects of gene products. The wealth of GO annotation data provides a valuable source of implicit knowledge of relationships among these aspects. We describe a new method for association rule mining to discover implicit co-occurrence relationships across the GO sub-ontologies at multiple levels of abstraction. Prior work on association rule mining in the GO has concentrated on mining knowledge at a single level of abstraction and/or between terms from the same sub-ontology. We have developed a bottom-up generalization procedure called Cross-Ontology Data Mining-Level by Level (COLL) that takes into account the structure and semantics of the GO, generates generalized transactions from annotation data and mines interesting multi-level cross-ontology association rules. We applied our method on publicly available chicken and mouse GO annotation datasets and mined 5368 and 3959 multi-level cross ontology rules from the two datasets respectively. We show that our approach discovers more and higher quality association rules from the GO as evaluated by biologists in comparison to previously published methods. Biologically interesting rules discovered by our method reveal unknown and surprising knowledge about co-occurring GO terms.     

Inferring genetic regulatory logic from expression data

MOTIVATION: High-throughput molecular genetics methods allow the collection of data about the expression of genes at different time points and under different conditions. The challenge is to infer gene regulatory interactions from these data and to get an insight into the mechanisms of genetic regulation. RESULTS: We propose a model for genetic regulatory interactions, which has a biologically motivated Boolean logic semantics, but is of a probabilistic nature, and is hence able to confront noisy biological processes and data. We propose a method for learning the model from data based on the Bayesian approach and utilizing Gibbs sampling. We tested our method with previously published data of the Saccharomyces cerevisiae cell cycle and found relations between genes consistent with biological knowledge.     

Utilizing logical relationships in genomic data to decipher cellular processes

The wealth of available genomic data has spawned a corresponding interest in computational methods that can impart biological meaning and context to these experiments. Traditional computational methods have drawn relationships between pairs of proteins or genes based on notions of equality or similarity between their patterns of occurrence or behavior. For example, two genes displaying similar variation in expression, over a number of experiments, may be predicted to be functionally related. We have introduced a natural extension of these approaches, instead identifying logical relationships involving triplets of proteins. Triplets provide for various discrete kinds of logic relationships, leading to detailed inferences about biological associations. For instance, a protein C might be encoded within an organism if, and only if, two other proteins A and B are also both encoded within the organism, thus suggesting that gene C is functionally related to genes A and B. The method has been applied fruitfully to both phylogenetic and microarray expression data, and has been used to associate logical combinations of protein activity with disease state phenotypes, revealing previously unknown ternary relationships among proteins, and illustrating the inherent complexities that arise in biological data.     

Reverse engineering and analysis of genome-wide gene regulatory networks from gene expression profiles using high-performance computing

Regulation of gene expression is a carefully regulated phenomenon in the cell. “Reverse-engineering” algorithms try to reconstruct the regulatory interactions among genes from genome-scale measurements of gene expression profiles (microarrays). Mammalian cells express tens of thousands of genes; hence, hundreds of gene expression profiles are necessary in order to have acceptable statistical evidence of interactions between genes. As the number of profiles to be analyzed increases, so do computational costs and memory requirements. In this work, we designed and developed a parallel computing algorithm to reverse-engineer genome-scale gene regulatory networks from thousands of gene expression profiles. The algorithm is based on computing pairwise Mutual Information between each gene-pair. We successfully tested it to reverse engineer the Mus Musculus (mouse) gene regulatory network in liver from gene expression profiles collected from a public repository. A parallel hierarchical clustering algorithm was implemented to discover “communities” within the gene network. Network communities are enriched for genes involved in the same biological functions. The inferred network was used to identify two mitochondrial proteins.