Assessing statistical significance in causal graphs
Open Access
- 20 February 2012
- journal article
- research article
- Published by Springer Science and Business Media LLC in BMC Bioinformatics
- Vol. 13 (1), 35
- https://doi.org/10.1186/1471-2105-13-35
Abstract
Background: Causal graphs are an increasingly popular tool for the analysis of biological datasets. In particular, signed causal graphs--directed graphs whose edges additionally have a sign denoting upregulation or downregulation--can be used to model regulatory networks within a cell. Such models allow prediction of downstream effects of regulation of biological entities; conversely, they also enable inference of causative agents behind observed expression changes. However, due to their complex nature, signed causal graph models present special challenges with respect to assessing statistical significance. In this paper we frame and solve two fundamental computational problems that arise in practice when computing appropriate null distributions for hypothesis testing.Results: First, we show how to compute a p-value for agreement between observed and model-predicted classifications of gene transcripts as upregulated, downregulated, or neither. Specifically, how likely are the classifications to agree to the same extent under the null distribution of the observed classification being randomized? This problem, which we call "Ternary Dot Product Distribution" owing to its mathematical form, can be viewed as a generalization of Fisher's exact test to ternary variables. We present two computationally efficient algorithms for computing the Ternary Dot Product Distribution and investigate its combinatorial structure analytically and numerically to establish computational complexity bounds.Second, we develop an algorithm for efficiently performing random sampling of causal graphs. This enables p-value computation under a different, equally important null distribution obtained by randomizing the graph topology but keeping fixed its basic structure: connectedness and the positive and negative in- and out-degrees of each vertex. We provide an algorithm for sampling a graph from this distribution uniformly at random. We also highlight theoretical challenges unique to signed causal graphs; previous work on graph randomization has studied undirected graphs and directed but unsigned graphs.Conclusion: We present algorithmic solutions to two statistical significance questions necessary to apply the causal graph methodology, a powerful tool for biological network analysis. The algorithms we present are both fast and provably correct. Our work may be of independent interest in non-biological contexts as well, as it generalizes mathematical results that have been studied extensively in other fields.Keywords
This publication has 23 references indexed in Scilit:
- Causal reasoning on biological networks: interpreting transcriptional changesBioinformatics, 2012
- The Role of Hypoxia in 2-Butoxyethanol–Induced HemangiosarcomaToxicological Sciences, 2009
- RNAiCut: automated detection of significant genes from functional genomic screensNature Methods, 2009
- Global comparative transcriptome analysis of cartilage formation in vivoBMC Developmental Biology, 2009
- A general modular framework for gene set enrichment analysisBMC Bioinformatics, 2009
- SIRT1 Promotes Differentiation of Normal Human KeratinocytesJournal of Investigative Dermatology, 2009
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences of the United States of America, 2008
- Expression profiling of Dexamethasone-treated primary chondrocytes identifies targets of glucocorticoid signalling in endochondral bone developmentBMC Genomics, 2007
- The Connectivity Map: Using Gene-Expression Signatures to Connect Small Molecules, Genes, and DiseaseScience, 2006
- A Computational Model to Define the Molecular Causes of Type 2 Diabetes MellitusDiabetes Technology & Therapeutics, 2005