{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T12:33:10Z","timestamp":1773664390401,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>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.<\/jats:p><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-13-35","type":"journal-article","created":{"date-parts":[[2012,2,20]],"date-time":"2012-02-20T21:15:42Z","timestamp":1329772542000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Assessing statistical significance in causal graphs"],"prefix":"10.1186","volume":"13","author":[{"given":"Leonid","family":"Chindelevitch","sequence":"first","affiliation":[]},{"given":"Po-Ru","family":"Loh","sequence":"additional","affiliation":[]},{"given":"Ahmed","family":"Enayetallah","sequence":"additional","affiliation":[]},{"given":"Bonnie","family":"Berger","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Ziemek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,20]]},"reference":[{"issue":"2","key":"5077_CR1","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1089\/dia.2005.7.323","volume":"7","author":"J Pollard","year":"2005","unstructured":"Pollard J, Butte AJ, Hoberman S, Joshi M, Levy J, Pappo J: A computational model to define the molecular causes of type 2 diabetes mellitus. Diabetes Technol Ther 2005, 7(2):323\u201336. 10.1089\/dia.2005.7.323","journal-title":"Diabetes Technol Ther"},{"key":"5077_CR2","first-page":"263","volume-title":"Proceedings of RECOMB","author":"YA Kim","year":"2010","unstructured":"Kim YA, Wuchty S, Przytycka TM: Simultaneous Identification of Causal Genes and Dys-Regulated Pathways in Complex Diseases. Proceedings of RECOMB 2010, 263\u2013280."},{"key":"5077_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/jid.2008.179","volume":"129","author":"G Blander","year":"2008","unstructured":"Blander G, Bhimavarapu A, Mammone T, Maes D, Elliston K, Reich C, Matsui MS, Guarente L, Loureiro JJ: SIRT1 Promotes Differentiation of Normal Human Keratinocytes. Journal of Investigative Dermatology 2008, 129: 41\u201349.","journal-title":"Journal of Investigative Dermatology"},{"key":"5077_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1093\/toxsci\/kfp213","volume":"113","author":"D Laifenfeld","year":"2010","unstructured":"Laifenfeld D, Gilchrist A, Drubin D, Jorge M, Eddy SF, Frushour BP, Ladd B, Obert LA, Gosink MM, Cook JC, Criswell K, Somps CJ, Koza-Taylor P, Elliston KO, Lawton MP: The Role of Hypoxia in 2-Butoxyethanol-Induced Hemangiosarcoma. Toxicological Sciences 2010, 113: 254\u2013266. 10.1093\/toxsci\/kfp213","journal-title":"Toxicological Sciences"},{"key":"5077_CR5","unstructured":"Chindelevitch L, Ziemek D, Enayetallah A, Randhawa R, Sidders B, Brockel C, Huang E: Causal reasoning on biological networks: Interpreting transcriptional changes. Bioinformatics, in press."},{"key":"5077_CR6","volume-title":"Statistical Methods for Research Workers","author":"RA Fisher","year":"1970","unstructured":"Fisher RA: Statistical Methods for Research Workers. Oliver and Boyd; 1970."},{"key":"5077_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1186\/1471-2105-10-47","volume":"10","author":"M Ackermann","year":"2009","unstructured":"Ackermann M, Strimmer K: A general modular framework for gene set enrichment analysis. BMC Bioinformatics 2009, 10: 47. 10.1186\/1471-2105-10-47","journal-title":"BMC Bioinformatics"},{"issue":"5795","key":"5077_CR8","doi-asserted-by":"publisher","first-page":"1929","DOI":"10.1126\/science.1132939","volume":"313","author":"J Lamb","year":"2006","unstructured":"Lamb J, Crawford ED, Peck D, Modell JW, Blat IC, Wrobel MJ, Lerner J, Brunet JPP, Subramanian A, Ross KN, Reich M, Hieronymus H, Wei G, Armstrong SA, Haggarty SJ, Clemons PA, Wei R, Carr SA, Lander ES, Golub TR: The Connectivity Map: using gene-expression signatures to connect small molecules, genes, and disease. Science 2006, 313(5795):1929\u20131935. 10.1126\/science.1132939","journal-title":"Science"},{"key":"5077_CR9","first-page":"115","volume":"3","author":"R Taylor","year":"1982","unstructured":"Taylor R: Constrained Switching in Graphs. SIAM Journal of Algorithms and Discrete Mathematics 1982, 3: 115\u2013121.","journal-title":"SIAM Journal of Algorithms and Discrete Mathematics"},{"key":"5077_CR10","volume-title":"Computing Research Repository (CoRR)","author":"AO Stauffer","year":"2005","unstructured":"Stauffer AO, Barbosa VC: A study of the edge-switching Markov-chain method for the generation of random graphs. Computing Research Repository (CoRR) 2005. abs\/cs\/0512105. abs\/cs\/0512105."},{"key":"5077_CR11","first-page":"440","volume-title":"In Proceedings of COCOON","author":"F Viger","year":"2005","unstructured":"Viger F, Latapy M: Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence. In Proceedings of COCOON 2005, 440\u2013449."},{"key":"5077_CR12","first-page":"225","volume":"58","author":"AR Rao","year":"1996","unstructured":"Rao AR, Jana R, Bandyopadhyay S: A Markov Chain Monte Carlo Method for Generating Random (0, 1)-Matrices with Given Marginals. The Indian Journal of Statistics, Series A 1996, 58: 225\u2013242.","journal-title":"The Indian Journal of Statistics, Series A"},{"issue":"4","key":"5077_CR13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G","volume":"14","author":"R Kannan","year":"1999","unstructured":"Kannan R, Tetali P, Vempala S: Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Structures and Algorithms 1999, 14(4):293\u2013308. 10.1002\/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G","journal-title":"Random Structures and Algorithms"},{"key":"5077_CR14","volume-title":"arXiv","author":"R Milo","year":"2003","unstructured":"Milo R, Kashtan N, Itzkovitz S, Newman MEJ, Alon U: On the uniform generation of random graphs with prescribed degree sequences. arXiv 2003. cond-mat.stat-mech:0312028. cond-mat.stat-mech:0312028."},{"key":"5077_CR15","volume-title":"The Electronic Journal of Combinatorics","author":"LP Erd\u00f6s","year":"2010","unstructured":"Erd\u00f6s LP, Mikl\u00f3s I, Toroczkai Z: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. The Electronic Journal of Combinatorics 2010., 17:"},{"key":"5077_CR16","volume-title":"arXiv","author":"C Greenhill","year":"2011","unstructured":"Greenhill C: A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs. arXiv 2011. math.CO:1105.0457. math.CO:1105.0457."},{"issue":"3","key":"5077_CR17","doi-asserted-by":"publisher","first-page":"036117","DOI":"10.1103\/PhysRevE.84.036117","volume":"84","author":"R Albert","year":"2011","unstructured":"Albert R, DasGupta B, Hegde R, Sivanathan G, Gitter A, G\u00fcrsoy G, Paul P, Sontag E: Computationally efficient measure of topological redundancy of biological and social networks. Physical Review E 2011, 84(3):036117.","journal-title":"Physical Review E"},{"issue":"5569","key":"5077_CR18","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1126\/science.1065103","volume":"296","author":"S Maslov","year":"2002","unstructured":"Maslov S, Sneppen K: Specificity and Stability in Topology of Protein Networks. Science 2002, 296(5569):910\u2013913. 10.1126\/science.1065103","journal-title":"Science"},{"issue":"35","key":"5077_CR19","doi-asserted-by":"publisher","first-page":"12763","DOI":"10.1073\/pnas.0806627105","volume":"105","author":"R Singh","year":"2008","unstructured":"Singh R, Xu J, Berger B: Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences of the United States of America 2008, 105(35):12763\u201312768. 10.1073\/pnas.0806627105","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"issue":"7","key":"5077_CR20","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1038\/nmeth0709-476","volume":"6","author":"IM Kaplow","year":"2009","unstructured":"Kaplow IM, Singh R, Friedman A, Bakal C, Perrimon N, Berger B: RNAiCut: automated detection of significant genes from functional genomic screens. Nat Meth 2009, 6(7):476\u2013477. 10.1038\/nmeth0709-476","journal-title":"Nat Meth"},{"key":"5077_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1186\/1471-2164-8-205","volume":"8","author":"C James","year":"2007","unstructured":"James C, Ulici V, Tuckermann J, Underhill T, Beier F: Expression profiling of Dexamethasone-treated primary chondrocytes identifies targets of glucocorticoid signalling in endochondral bone development. BMC Genomics 2007, 8: 205. 10.1186\/1471-2164-8-205","journal-title":"BMC Genomics"},{"issue":"21","key":"5077_CR22","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1101\/gad.934301","volume":"15","author":"E Schipani","year":"2001","unstructured":"Schipani E, Ryan H, Didrickson S, Kobayashi T, Knight M, Johnson R: Hypoxia in cartilage: HIF-1 \u03b1 is essential for chondrocyte growth arrest and survival. Genes & Development 2001, 15(21):2865.","journal-title":"Genes & Development"},{"issue":"8","key":"5077_CR23","doi-asserted-by":"publisher","first-page":"4778","DOI":"10.1074\/jbc.M707729200","volume":"283","author":"J Lafont","year":"2008","unstructured":"Lafont J, Talma S, Hopfgarten C, Murphy C: Hypoxia promotes the differentiated human articular chondrocyte phenotype through SOX9-dependent and-independent pathways. Journal of Biological Chemistry 2008, 283(8):4778.","journal-title":"Journal of Biological Chemistry"},{"key":"5077_CR24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/1471-213X-9-20","volume":"9","author":"T Cameron","year":"2009","unstructured":"Cameron T, Belluoccio D, Farlie P, Brachvogel B, Bateman J: Global comparative transcriptome analysis of cartilage formation in vivo. BMC Developmental Biology 2009, 9: 20. 10.1186\/1471-213X-9-20","journal-title":"BMC Developmental Biology"},{"key":"5077_CR25","volume-title":"Journal of Orthopaedic Research","author":"S Hung","year":"2011","unstructured":"Hung S, Ho J, Shih Y, Lo T, Lee O: Hypoxia promotes proliferation and osteogenic differentiation potentials of human mesenchymal stem cells. Journal of Orthopaedic Research 2011."},{"key":"5077_CR26","doi-asserted-by":"crossref","DOI":"10.1201\/9781439864500","volume-title":"A = B","author":"M Petkov\u0161ek","year":"1996","unstructured":"Petkov\u0161ek M, Wilf H, Zeilberger D: A = B. Wellesley, MA, USA: A K Peters Ltd; 1996."},{"key":"5077_CR27","volume-title":"R: A Language and Environment for Statistical Computing","author":"R Development Core Team","year":"2011","unstructured":"R Development Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria; 2011."},{"key":"5077_CR28","volume-title":"InterJournal","author":"G Csardi","year":"2006","unstructured":"Csardi G, Nepusz T: The igraph software package for complex network research. InterJournal 2006. Complex Systems:1695. Complex Systems:1695."},{"key":"5077_CR29","first-page":"803","volume-title":"Proceedings of FOCS","author":"S Bhamidi","year":"2008","unstructured":"Bhamidi S, Bresler G, Sly A: Mixing Time of Exponential Random Graphs. Proceedings of FOCS 2008, 803\u2013812."},{"issue":"7","key":"5077_CR30","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1089\/cmb.2007.0015","volume":"14","author":"R Albert","year":"2007","unstructured":"Albert R, DasGupta B, Dondi R, Kachalo S, Sontag E, Zelikovsky A, Westbrooks K: A novel method for signal transduction network inference from indirect experimental evidence. Journal of Computational Biology 2007, 14(7):927\u2013949. 10.1089\/cmb.2007.0015","journal-title":"Journal of Computational Biology"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-35.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T02:49:05Z","timestamp":1640832545000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,20]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5077"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-35","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,20]]},"assertion":[{"value":"29 July 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"35"}}