{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T06:08:40Z","timestamp":1790662120619,"version":"4.1.0"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1008550","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T00:00:00Z","timestamp":1612915200000}}],"reference-count":45,"publisher":"Public Library of Science (PLoS)","issue":"1","license":[{"start":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T00:00:00Z","timestamp":1611878400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Gulf Coast Consortia","award":["T15 LM007093"],"award-info":[{"award-number":["T15 LM007093"]}]},{"name":"Henry and Emma Meyer Professorship in Molecular Genetics","award":["U54-DA036134"],"award-info":[{"award-number":["U54-DA036134"]}]},{"name":"Henry and Emma Meyer Professorship in Molecular Genetics","award":["U54-DA049098"],"award-info":[{"award-number":["U54-DA049098"]}]},{"name":"Henry and Emma Meyer Professorship in Molecular Genetics","award":["U41-HG009649"],"award-info":[{"award-number":["U41-HG009649"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>We consider the following general family of algorithmic problems that arises in transcriptomics, metabolomics and other fields: given a weighted graph G and a subset of its nodes S, find subsets of S that show significant connectedness within G. A specific solution to this problem may be defined by devising a scoring function, the Maximum Clique problem being a classic example, where S includes all nodes in G and where the score is defined by the size of the largest subset of S fully connected within G. Major practical obstacles for the plethora of algorithms addressing this type of problem include computational efficiency and, particularly for more complex scores which take edge weights into account, the computational cost of permutation testing, a statistical procedure required to obtain a bound on the p-value for a connectedness score. To address these problems, we developed CTD, \u201cConnect the Dots\u201d, a fast algorithm based on data compression that detects highly connected subsets within S. CTD provides information-theoretic upper bounds on p-values when S contains a small fraction of nodes in G without requiring computationally costly permutation testing. We apply the CTD algorithm to interpret multi-metabolite perturbations due to inborn errors of metabolism and multi-transcript perturbations associated with breast cancer in the context of disease-specific Gaussian Markov Random Field networks learned directly from respective molecular profiling data.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1008550","type":"journal-article","created":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T18:44:36Z","timestamp":1611945876000},"page":"e1008550","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":13,"title":["CTD: An information-theoretic algorithm to interpret sets of metabolomic and transcriptomic perturbations in the context of graphical models"],"prefix":"10.1371","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4436-598X","authenticated-orcid":true,"given":"Lillian R.","family":"Thistlethwaite","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Varduhi","family":"Petrosyan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0875-8337","authenticated-orcid":true,"given":"Xiqi","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcus J.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1400-8519","authenticated-orcid":true,"given":"Sarah H.","family":"Elsea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandar","family":"Milosavljevic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"issue":"9","key":"pcbi.1008550.ref001","doi-asserted-by":"crossref","first-page":"1977","DOI":"10.1038\/s41436-019-0442-0","article-title":"Untargeted metabolomic profiling reveals multiple pathway perturbations and new clinical biomarkers in urea cycle disorders","volume":"21","author":"LC Burrage","year":"2019","journal-title":"Genet Med"},{"issue":"10","key":"pcbi.1008550.ref002","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1038\/gim.2017.262","article-title":"A metabolomic map of Zellweger spectrum disorders reveals novel disease biomarkers","volume":"20","author":"MF Wangler","year":"2018","journal-title":"Genet Med"},{"issue":"6","key":"pcbi.1008550.ref003","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1007\/s10545-015-9843-7","article-title":"Untargeted metabolomic analysis for the clinical screening of inborn errors of metabolism","volume":"38","author":"MJ Miller","year":"2015","journal-title":"J Inherit Metab Dis"},{"issue":"10","key":"pcbi.1008550.ref004","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1038\/ng.2764","article-title":"The Cancer Genome Atlas Pan-Cancer analysis project","volume":"45","author":"JN Weinstein","year":"2013","journal-title":"Nat Genet"},{"issue":"7418","key":"pcbi.1008550.ref005","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1038\/nature11412","article-title":"Comprehensive molecular portraits of human breast tumours","volume":"490","author":"CGA Network","year":"2012","journal-title":"Nature"},{"issue":"1","key":"pcbi.1008550.ref006","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/bioinformatics\/bts635","article-title":"STAR: ultrafast universal RNA-seq aligner","volume":"29","author":"A Dobin","year":"2013","journal-title":"Bioinformatics"},{"issue":"3","key":"pcbi.1008550.ref007","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"B Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"pcbi.1008550.ref008","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1186\/1471-2105-12-323","article-title":"RSEM: accurate transcript quantification from RNA-Seq data with or without a reference genome","volume":"12","author":"B Li","year":"2011","journal-title":"BMC Bioinformatics"},{"issue":"9","key":"pcbi.1008550.ref009","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1093\/bioinformatics\/btp120","article-title":"TopHat: discovering splice junctions with RNA-Seq","volume":"25","author":"C Trapnell","year":"2009","journal-title":"Bioinformatics"},{"issue":"10","key":"pcbi.1008550.ref010","doi-asserted-by":"crossref","first-page":"R106","DOI":"10.1186\/gb-2010-11-10-r106","article-title":"Differential expression analysis for sequence count data","volume":"11","author":"S Anders","year":"2010","journal-title":"Genome Biol"},{"issue":"1","key":"pcbi.1008550.ref011","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1093\/bioinformatics\/btp616","article-title":"edgeR: a Bioconductor package for differential expression analysis of digital gene expression data","volume":"26","author":"MD Robinson","year":"2010","journal-title":"Bioinformatics"},{"issue":"9","key":"pcbi.1008550.ref012","doi-asserted-by":"crossref","first-page":"R183","DOI":"10.1186\/gb-2007-8-9-r183","article-title":"The DAVID Gene Functional Classification Tool: a novel biological module-centric algorithm to functionally analyze large gene lists","volume":"8","author":"DW Huang","year":"2007","journal-title":"Genome Biol"},{"issue":"4","key":"pcbi.1008550.ref013","first-page":"407","article-title":"Discovering simple DNA sequences by the algorithmic significance method","volume":"9","author":"A Milosavljevi\u0107","year":"1993","journal-title":"Comput Appl Biosci"},{"issue":"1","key":"pcbi.1008550.ref014","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1093\/nar\/28.1.27","article-title":"KEGG: kyoto encyclopedia of genes and genomes","volume":"28","author":"M Kanehisa","year":"2000","journal-title":"Nucleic Acids Res"},{"issue":"D1","key":"pcbi.1008550.ref015","doi-asserted-by":"crossref","first-page":"D481","DOI":"10.1093\/nar\/gkv1351","article-title":"The Reactome pathway Knowledgebase","volume":"44","author":"A Fabregat","year":"2016","journal-title":"Nucleic Acids Res"},{"issue":"D1","key":"pcbi.1008550.ref016","doi-asserted-by":"crossref","first-page":"D661","DOI":"10.1093\/nar\/gkx1064","article-title":"WikiPathways: a multifaceted pathway database bridging metabolomics to other omics research","volume":"46","author":"DN Slenter","year":"2018","journal-title":"Nucleic Acids Res"},{"key":"pcbi.1008550.ref017","doi-asserted-by":"crossref","first-page":"D480","DOI":"10.1093\/nar\/gkp1002","article-title":"SMPDB: The Small Molecule Pathway Database","volume":"38","author":"A Frolkis","year":"2010","journal-title":"Nucleic Acids Res"},{"issue":"9","key":"pcbi.1008550.ref018","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.tig.2014.07.004","article-title":"Functional and genomic context in pathway analysis of GWAS data","volume":"30","author":"MA Mooney","year":"2014","journal-title":"Trends Genet"},{"issue":"10","key":"pcbi.1008550.ref019","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1038\/nrg3552","article-title":"Integrative approaches for finding modular structure in biological networks","volume":"14","author":"K Mitra","year":"2013","journal-title":"Nat Rev Genet"},{"issue":"6","key":"pcbi.1008550.ref020","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1016\/j.cell.2011.02.016","article-title":"Interactome networks and human disease","volume":"144","author":"M Vidal","year":"2011","journal-title":"Cell"},{"issue":"8","key":"pcbi.1008550.ref021","doi-asserted-by":"crossref","first-page":"980","DOI":"10.1093\/bioinformatics\/btm051","article-title":"Analyzing gene expression data in terms of gene sets: methodological issues","volume":"23","author":"JJ Goeman","year":"2007","journal-title":"Bioinformatics"},{"key":"pcbi.1008550.ref022","volume-title":"Model and Data Engineering: 7 th International Conference, MEDI 2017","author":"M Savic","year":"2017"},{"issue":"4","key":"pcbi.1008550.ref023","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1073\/pnas.0706851105","article-title":"Maps of random walks on complex networks reveal community structure","volume":"105","author":"M Rosvall","year":"2008","journal-title":"Proc Natl Acad Sci U S A"},{"issue":"6","key":"pcbi.1008550.ref024","doi-asserted-by":"crossref","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","article-title":"Finding community structure in very large networks","volume":"70","author":"A Clauset","year":"2004","journal-title":"Phys Rev E Stat Nonlin Soft Matter Phys"},{"key":"pcbi.1008550.ref025","doi-asserted-by":"crossref","first-page":"191","DOI":"10.7155\/jgaa.00124","article-title":"Computing communities in large networks using random walks","author":"P Pons","year":"2006","journal-title":"J Graph Algorithms Appl"},{"key":"pcbi.1008550.ref026","doi-asserted-by":"crossref","first-page":"5491","DOI":"10.2147\/OTT.S142154","article-title":"The crossroads of breast cancer progression: insights into the modulation of major signaling pathways","volume":"10","author":"FJ Velloso","year":"2017","journal-title":"Onco Targets Ther"},{"issue":"43","key":"pcbi.1008550.ref027","doi-asserted-by":"crossref","first-page":"15545","DOI":"10.1073\/pnas.0506580102","article-title":"Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles","volume":"102","author":"A Subramanian","year":"2005","journal-title":"Proc Natl Acad Sci U S A"},{"key":"pcbi.1008550.ref028","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1186\/1752-0509-6-56","article-title":"Centrality-based pathway enrichment: a systematic approach for finding significant pathways dominated by key genes","volume":"6","author":"Z Gu","year":"2012","journal-title":"BMC Syst Biol"},{"issue":"1","key":"pcbi.1008550.ref029","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1093\/bioinformatics\/btn577","article-title":"A novel signaling pathway impact analysis","volume":"25","author":"AL Tarca","year":"2009","journal-title":"Bioinformatics"},{"key":"pcbi.1008550.ref030","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1214\/11-AOAS528","article-title":"More power via graph-structured tests for differential expression of gene networks","author":"L Jacob","year":"2012","journal-title":"Ann Appl Stat"},{"issue":"1","key":"pcbi.1008550.ref031","doi-asserted-by":"crossref","first-page":"e0191154","DOI":"10.1371\/journal.pone.0191154","article-title":"A critical comparison of topology-based pathway analysis methods","volume":"13","author":"I Ihnatova","year":"2018","journal-title":"PLoS One"},{"key":"pcbi.1008550.ref032","article-title":"Network methods for pathway analysis of genomic data","author":"R Braun","year":"2014","journal-title":"arXiv"},{"issue":"5","key":"pcbi.1008550.ref033","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1089\/cmb.2011.0182","article-title":"A topology-based score for pathway enrichment","volume":"19","author":"MA Ibrahim","year":"2012","journal-title":"J Comput Biol"},{"issue":"1","key":"pcbi.1008550.ref034","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nrg2918","article-title":"Network medicine: a network-based approach to human disease","volume":"12","author":"AL Barab\u00e1si","year":"2011","journal-title":"Nat Rev Genet"},{"key":"pcbi.1008550.ref035","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1186\/1471-2105-10-47","article-title":"A general modular framework for gene set enrichment analysis","volume":"10","author":"M Ackermann","year":"2009","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"pcbi.1008550.ref036","doi-asserted-by":"crossref","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","article-title":"Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs","volume":"20","author":"N Kashtan","year":"2004","journal-title":"Bioinformatics"},{"issue":"4","key":"pcbi.1008550.ref037","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"S. Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"pcbi.1008550.ref038","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1186\/1471-2105-10-318","article-title":"Kavosh: a new algorithm for finding network motifs","volume":"10","author":"ZR Kashani","year":"2009","journal-title":"BMC Bioinformatics"},{"issue":"17","key":"pcbi.1008550.ref039","doi-asserted-by":"crossref","first-page":"3572","DOI":"10.1093\/bioinformatics\/bti556","article-title":"MAVisto: a tool for the exploration of network motifs","volume":"21","author":"F Schreiber","year":"2005","journal-title":"Bioinformatics"},{"issue":"3","key":"pcbi.1008550.ref040","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1089\/cmb.2010.0265","article-title":"Algorithms for detecting significantly mutated pathways in cancer","volume":"18","author":"F Vandin","year":"2011","journal-title":"J Comput Biol"},{"issue":"2","key":"pcbi.1008550.ref041","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1038\/ng.3168","article-title":"Pan-cancer network analysis identifies combinations of rare somatic mutations across pathways and protein complexes","volume":"47","author":"MD Leiserson","year":"2015","journal-title":"Nat Genet"},{"key":"pcbi.1008550.ref042","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1752-0509-1-8","article-title":"Identification of functional modules using network topology and high-throughput data","volume":"1","author":"I Ulitsky","year":"2007","journal-title":"BMC Syst Biol"},{"issue":"5","key":"pcbi.1008550.ref043","doi-asserted-by":"crossref","first-page":"e1003054","DOI":"10.1371\/journal.pcbi.1003054","article-title":"Simultaneous identification of multiple driver pathways in cancer","volume":"9","author":"MD Leiserson","year":"2013","journal-title":"PLoS Comput Biol"},{"key":"pcbi.1008550.ref044","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1186\/1471-2164-13-282","article-title":"NetWalker: a contextual network analysis tool for functional genomics","volume":"13","author":"K Komurov","year":"2012","journal-title":"BMC Genomics"},{"issue":"12","key":"pcbi.1008550.ref045","doi-asserted-by":"crossref","first-page":"i237","DOI":"10.1093\/bioinformatics\/btq182","article-title":"Inference of patient-specific pathway activities from multi-dimensional cancer genomics data using PARADIGM","volume":"26","author":"CJ Vaske","year":"2010","journal-title":"Bioinformatics"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1009551","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T00:00:00Z","timestamp":1635120000000}},{"DOI":"10.1371\/journal.pcbi.1008550","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T00:00:00Z","timestamp":1612915200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T22:30:10Z","timestamp":1613082610000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008550"}},"subtitle":[],"editor":[{"given":"Jason A.","family":"Papin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,1,29]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1,29]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1008550","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1008550","asserted-by":"object"}],"correction":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1009551","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,29]]}}}