{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T14:44:45Z","timestamp":1782485085316,"version":"3.54.5"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2016,10,12]],"date-time":"2016-10-12T00:00:00Z","timestamp":1476230400000},"content-version":"vor","delay-in-days":333,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: We addressed the problem of inferring gene regulatory network (GRN) from gene expression data of knockout (KO) experiments. This inference is known to be underdetermined and the GRN is not identifiable from data. Past studies have shown that suboptimal design of experiments (DOE) contributes significantly to the identifiability issue of biological networks, including GRNs. However, optimizing DOE has received much less attention than developing methods for GRN inference.<\/jats:p>\n               <jats:p>Results: We developed REDuction of UnCertain Edges (REDUCE) algorithm for finding the optimal gene KO experiment for inferring directed graphs (digraphs) of GRNs. REDUCE employed ensemble inference to define uncertain gene interactions that could not be verified by prior data. The optimal experiment corresponds to the maximum number of uncertain interactions that could be verified by the resulting data. For this purpose, we introduced the concept of edge separatoid which gave a list of nodes (genes) that upon their removal would allow the verification of a particular gene interaction. Finally, we proposed a procedure that iterates over performing KO experiments, ensemble update and optimal DOE. The case studies including the inference of Escherichia coli GRN and DREAM 4\u2009100-gene GRNs, demonstrated the efficacy of the iterative GRN inference. In comparison to systematic KOs, REDUCE could provide much higher information return per gene KO experiment and consequently more accurate GRN estimates.<\/jats:p>\n               <jats:p>Conclusions: REDUCE represents an enabling tool for tackling the underdetermined GRN inference. Along with advances in gene deletion and automation technology, the iterative procedure brings an efficient and fully automated GRN inference closer to reality.<\/jats:p>\n               <jats:p>Availability and implementation: MATLAB and Python scripts of REDUCE are available on www.cabsel.ethz.ch\/tools\/REDUCE.<\/jats:p>\n               <jats:p>Contact: \u00a0rudi.gunawan@chem.ethz.ch<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv672","type":"journal-article","created":{"date-parts":[[2015,11,15]],"date-time":"2015-11-15T01:38:21Z","timestamp":1447551501000},"page":"875-883","source":"Crossref","is-referenced-by-count":32,"title":["Optimal design of gene knockout experiments for gene regulatory network inference"],"prefix":"10.1093","volume":"32","author":[{"given":"S. M. Minhaz","family":"Ud-Dean","sequence":"first","affiliation":[{"name":"1 Institute for Chemical and Bioengineering, ETH Zurich, Zurich, Switzerland and"},{"name":"1 Institute for Chemical and Bioengineering, ETH Zurich, Zurich, Switzerland and"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rudiyanto","family":"Gunawan","sequence":"additional","affiliation":[{"name":"1 Institute for Chemical and Bioengineering, ETH Zurich, Zurich, Switzerland and"},{"name":"1 Institute for Chemical and Bioengineering, ETH Zurich, Zurich, Switzerland and"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,11,14]]},"reference":[{"key":"2023020111545891400_btv672-B1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0201008","article-title":"The transitive reduction of a directed graph","volume":"1","author":"Aho","year":"1972","journal-title":"SIAM J. Comput."},{"key":"2023020111545891400_btv672-B2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert","year":"2002","journal-title":"Rev. Mod. Phys."},{"key":"2023020111545891400_btv672-B3","first-page":"432","article-title":"A theoretical approach to gene network identification","author":"Birget","year":"2012","journal-title":"Information Theory Workshop (ITW)"},{"key":"2023020111545891400_btv672-B4","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-540-27836-8_21","article-title":"Approximating longest directed paths and cycles","volume-title":"Lecture Notes in Computer Science, Automata, Languages and Programming","author":"Bjorklund","year":"2004"},{"key":"2023020111545891400_btv672-B5","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1038\/nature13182","article-title":"A promoter-level mammalian expression atlas","volume":"507","author":"Consortium","year":"2014","journal-title":"Nature"},{"key":"2023020111545891400_btv672-B6","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1039\/C5IB00096C","article-title":"Sub-optimal phenotypes of double-knockout mutants of Escherichia coli depend on the order of gene deletions","volume":"7","author":"Gawand","year":"2015","journal-title":"Integr. Biol."},{"key":"2023020111545891400_btv672-B7","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence","author":"Holland","year":"1992"},{"key":"2023020111545891400_btv672-B8","first-page":"302","article-title":"Discovery of regulatory interactions through perturbation: inference and experimental design","volume":"5","author":"Ideker","year":"2000","journal-title":"Pac. Symp. Biocomput."},{"key":"2023020111545891400_btv672-B9","first-page":"613","article-title":"Estimating high-dimensional directed acyclic graphs with the PC-algorithm","volume":"8","author":"Kalisch","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"2023020111545891400_btv672-B10","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1038\/msb4100174","article-title":"Construction of consecutive deletions of the Escherichia coli chromosome","volume":"3","author":"Kato","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023020111545891400_btv672-B11","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.bpj.2013.11.2960","article-title":"Cutting the wires: modularization of cellular networks for experimental design","volume":"106","author":"Lang","year":"2014","journal-title":"Biophys. J."},{"key":"2023020111545891400_btv672-B12","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1038\/234034a0","article-title":"Distance between sets","volume":"234","author":"Levandowsky","year":"1971","journal-title":"Nature"},{"key":"2023020111545891400_btv672-B13","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1038\/nmeth0410-247","article-title":"Predicting causal effects in large-scale systems from observational data","volume":"7","author":"Maathuis","year":"2010","journal-title":"Nat. Methods"},{"key":"2023020111545891400_btv672-B14","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1038\/nmeth.2016","article-title":"Wisdom of crowds for robust gene network inference","volume":"9","author":"Marbach","year":"2012","journal-title":"Nat. Methods"},{"key":"2023020111545891400_btv672-B15","first-page":"mr7","article-title":"Crowdsourcing network inference: the DREAM predictive signaling network challenge","volume":"4","author":"Prill","year":"2011","journal-title":"Sci. Signal."},{"key":"2023020111545891400_btv672-B16","doi-asserted-by":"crossref","first-page":"2263","DOI":"10.1093\/bioinformatics\/btr373","article-title":"GeneNetWeaver: in silico benchmark generation and performance profiling of network inference methods","volume":"27","author":"Schaffter","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020111545891400_btv672-B17","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/978-3-540-24653-4_11","article-title":"Iteratively inferring gene regulatory networks with virtual knockout experiments","volume-title":"Applications of Evolutionary Computing","author":"Spieth","year":"2004"},{"key":"2023020111545891400_btv672-B18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1186\/1752-0509-1-51","article-title":"Experimental design for efficient identification of gene regulatory networks using sparse Bayesian models","volume":"1","author":"Steinke","year":"2007","journal-title":"BMC Syst. Biol."},{"key":"2023020111545891400_btv672-B19","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1073\/pnas.0406555102","article-title":"Statistical analysis of MPSS measurements: application to the study of LPS-activated macrophage gene expression","volume":"102","author":"Stolovitzky","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020111545891400_btv672-B20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1186\/1752-0509-5-177","article-title":"Inference of complex biological networks: distinguishability issues and optimization-based solutions","volume":"5","author":"Szederk\u00e9nyi","year":"2011","journal-title":"BMC Syst. Biol."},{"key":"2023020111545891400_btv672-B21","doi-asserted-by":"crossref","first-page":"5944","DOI":"10.1073\/pnas.0933416100","article-title":"Reverse engineering gene networks: Integrating genetic perturbations with dynamical modeling","volume":"100","author":"Tegn\u00e9r","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020111545891400_btv672-B22","doi-asserted-by":"crossref","first-page":"e103812","DOI":"10.1371\/journal.pone.0103812","article-title":"Ensemble inference and inferability of gene regulatory networks","volume":"9","author":"Ud-Dean","year":"2014","journal-title":"PLoS One"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/6\/875\/49018265\/bioinformatics_32_6_875.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/6\/875\/49018265\/bioinformatics_32_6_875.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:15:36Z","timestamp":1675289736000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/6\/875\/1744279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,14]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv672","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,3,15]]},"published":{"date-parts":[[2015,11,14]]}}}