{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T03:41:24Z","timestamp":1767843684388,"version":"3.49.0"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T00:00:00Z","timestamp":1475452800000},"content-version":"vor","delay-in-days":845,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Major disorders, such as leukemia, have been shown to alter the transcription of genes. Understanding how gene regulation is affected by such aberrations is of utmost importance. One promising strategy toward this objective is to compute whether signals can reach to the transcription factors through the transcription regulatory network (TRN). Due to the uncertainty of the regulatory interactions, this is a #P-complete problem and thus solving it for very large TRNs remains to be a challenge.<\/jats:p>\n               <jats:p>Results: We develop a novel and scalable method to compute the probability that a signal originating at any given set of source genes can arrive at any given set of target genes (i.e., transcription factors) when the topology of the underlying signaling network is uncertain. Our method tackles this problem for large networks while providing a provably accurate result. Our method follows a divide-and-conquer strategy. We break down the given network into a sequence of non-overlapping subnetworks such that reachability can be computed autonomously and sequentially on each subnetwork. We represent each interaction using a small polynomial. The product of these polynomials express different scenarios when a signal can or cannot reach to target genes from the source genes. We introduce polynomial collapsing operators for each subnetwork. These operators reduce the size of the resulting polynomial and thus the computational complexity dramatically. We show that our method scales to entire human regulatory networks in only seconds, while the existing methods fail beyond a few tens of genes and interactions. We demonstrate that our method can successfully characterize key reachability characteristics of the entire transcriptions regulatory networks of patients affected by eight different subtypes of leukemia, as well as those from healthy control samples.<\/jats:p>\n               <jats:p>Availability: All the datasets and code used in this article are available at bioinformatics.cise.ufl.edu\/PReach\/scalable.htm.<\/jats:p>\n               <jats:p>Contact: \u00a0atodor@cise.ufl.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu262","type":"journal-article","created":{"date-parts":[[2014,6,16]],"date-time":"2014-06-16T21:55:09Z","timestamp":1402955709000},"page":"i96-i104","source":"Crossref","is-referenced-by-count":5,"title":["Large scale analysis of signal reachability"],"prefix":"10.1093","volume":"30","author":[{"given":"Andrei","family":"Todor","sequence":"first","affiliation":[{"name":"CISE Department, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haitham","family":"Gabr","sequence":"additional","affiliation":[{"name":"CISE Department, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alin","family":"Dobra","sequence":"additional","affiliation":[{"name":"CISE Department, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[{"name":"CISE Department, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,6,11]]},"reference":[{"key":"2023012711102620400_btu262-B1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0026-2714(75)90461-8","article-title":"Reliability evaluation: a comparative study of different techniques","volume":"14","author":"Aggarwal","year":"1975","journal-title":"Microelectron. Reliab."},{"key":"2023012711102620400_btu262-B2","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1198\/016214501753381814","article-title":"Analysis of data from viral DNA microchips","volume":"96","author":"Amaratunga","year":"2001","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012711102620400_btu262-B3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/ng765","article-title":"MLL translocations specify a distinct gene expression profile that distinguishes a unique leukemia","volume":"30","author":"Armstrong","year":"2002","journal-title":"Nat. Genet."},{"key":"2023012711102620400_btu262-B4","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1038\/nbt924","article-title":"Gaining confidence in high-throughput protein interaction networks","volume":"22","author":"Bader","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"2023012711102620400_btu262-B5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"2023012711102620400_btu262-B6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1023\/A:1022484229443","article-title":"Non-stanley bounds for network reliability","volume":"5","author":"Brown","year":"1996","journal-title":"Journal of Algebraic Combinatorics"},{"key":"2023012711102620400_btu262-B7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/B978-0-12-381262-9.00005-7","article-title":"Proteins move! Protein dynamics and long-range allostery in cell signaling","volume":"83","author":"Bu","year":"2011","journal-title":"Adv. Protein Chem. Struct. Biol."},{"key":"2023012711102620400_btu262-B8","doi-asserted-by":"crossref","first-page":"D532","DOI":"10.1093\/nar\/gkp983","article-title":"MINT, the Molecular INTeraction database: 2009 update","volume":"38","author":"Ceol","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012711102620400_btu262-B9","first-page":"140","article-title":"Assessment of the reliability of protein-protein interactions and protein function prediction","author":"Deng","year":"2003","journal-title":"Pac. Symp. Biocomp."},{"key":"2023012711102620400_btu262-B10","article-title":"Characterization of probabilistic signaling networks through signal propagation","volume-title":"CISE Technical Report REP-2013-567","author":"Gabr","year":"2013"},{"key":"2023012711102620400_btu262-B11","doi-asserted-by":"crossref","DOI":"10.1145\/2506583.2506586","article-title":"PReach: reachability in probabilistic signaling networks","author":"Gabr","year":"2013","journal-title":"ACM-BCB"},{"key":"2023012711102620400_btu262-B12","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1038\/nature11245","article-title":"Architecture of the human regulatory network derived from ENCODE data","volume":"489","author":"Gerstein","year":"2012","journal-title":"Nature"},{"key":"2023012711102620400_btu262-B13","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1186\/1471-2105-13-250","article-title":"HIDEN: hierarchical decomposition of regulatory networks","volume":"13","author":"Gulsoy","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012711102620400_btu262-B14","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1038\/ng.2532","article-title":"The genomic landscape of hypodiploid acute lymphoblastic leukemia","volume":"45","author":"Holmfeldt","year":"2013","journal-title":"Nat. Genet."},{"key":"2023012711102620400_btu262-B15","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-642-17493-3_19","article-title":"The exponential time complexity of computing the probability that a graph is connected","volume":"6478","author":"Husfeldt","year":"2010","journal-title":"International Symposium on Parameterized and Exact Computation"},{"key":"2023012711102620400_btu262-B16","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1109\/TR.1981.5221152","article-title":"System-reliability evaluation techniques for complex\/large systems \u2013 a review","volume":"R-30","author":"Hwang","year":"1981","journal-title":"IEEE Trans. Reliab."},{"key":"2023012711102620400_btu262-B17","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1038\/35036627","article-title":"The large-scale organization of metabolic networks","volume":"407","author":"Jeong","year":"2000","journal-title":"Nature"},{"key":"2023012711102620400_btu262-B18","doi-asserted-by":"crossref","first-page":"12955","DOI":"10.1073\/pnas.0704138104","article-title":"The molecular basis of eukariotic transcription","volume":"104","author":"Kornberg","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711102620400_btu262-B19","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-1-59745-418-6_11","article-title":"Gene expression profiling of leukemia stem cells","volume":"538","author":"Krivtsov","year":"2009","journal-title":"Methods Mol. Biol."},{"key":"2023012711102620400_btu262-B20","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1038\/ni.2615","article-title":"The transcriptional architecture of early human hematopoiesis identifies multilevel control of lymphoid commitment","volume":"14","author":"Laurenti","year":"2013","journal-title":"Nat. Immunol."},{"key":"2023012711102620400_btu262-B21","first-page":"430","article-title":"Frequencies of ETV6-RUNX1 fusion and hyperdiploidy in pediatric acute lymphoblastic leukemia are lower in far east than west","volume":"55","author":"Liang","year":"2010","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711102620400_btu262-B22","first-page":"492","article-title":"Switching Akt: from survival signaling to deadly response","volume":"31","author":"Los","year":"2009","journal-title":"Bio Essays"},{"key":"2023012711102620400_btu262-B23","first-page":"51","article-title":"RNA regulation of epigenetic processes","volume":"31","author":"Mattick","year":"2009","journal-title":"Bio Essays"},{"key":"2023012711102620400_btu262-B24","doi-asserted-by":"crossref","first-page":"3004","DOI":"10.1038\/sj.onc.1202746","article-title":"Prochownic. MYC oncogenes and human neoplastic disease","volume":"18","author":"Nesbit","year":"1999","journal-title":"Oncogene"},{"key":"2023012711102620400_btu262-B25","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0378-1119(96)00184-9","article-title":"Structure and partial genomic sequence of the human E2F1 gene","volume":"173","author":"Neuman","year":"1996","journal-title":"Gene"},{"key":"2023012711102620400_btu262-B26","doi-asserted-by":"crossref","first-page":"i359","DOI":"10.1093\/bioinformatics\/btm170","article-title":"SPINE: a framework for signaling-regulatory pathway inference from cause-effect experiments","volume":"23","author":"Ourfali","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012711102620400_btu262-B27","doi-asserted-by":"crossref","first-page":"21719","DOI":"10.1073\/pnas.1006981107","article-title":"Genetic landscape of high hyperdiploid childhood acute lymphoblastic leukemia","volume":"107","author":"Paulsson","year":"2010","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711102620400_btu262-B28","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","article-title":"The complexity of counting cuts and of computing the probability that a graph is connected","volume":"12","author":"Provan","year":"1983","journal-title":"SIAM J. Comput."},{"key":"2023012711102620400_btu262-B29","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2002","journal-title":"PNAS"},{"key":"2023012711102620400_btu262-B30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/1471-2105-7-199","article-title":"QPath: a method for querying pathways in a protein-protein interaction network","volume":"7","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012711102620400_btu262-B31","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1186\/1471-2105-7-360","article-title":"A direct comparison of protein interaction confidence assignment schemes","volume":"7","author":"Suthram","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012711102620400_btu262-B32","doi-asserted-by":"crossref","first-page":"D561","DOI":"10.1093\/nar\/gkq973","article-title":"The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored","volume":"39","author":"Szklarczyk","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012711102620400_btu262-B33","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1056\/NEJMoa055229","article-title":"Dasatinib in imatinib-resistant Philadelphia chromosome-positive leukemias","volume":"354","author":"Talpaz","year":"2006","journal-title":"N. Engl. J. Med."},{"key":"2023012711102620400_btu262-B34","article-title":"Uncertain interactions affect degree distribution of biological networks","author":"Todor","year":"2012","journal-title":"BIBM"},{"key":"2023012711102620400_btu262-B35","first-page":"109","article-title":"Probabilistic biological network alignment","volume":"10","author":"Todor","year":"2013","journal-title":"TCBB"},{"key":"2023012711102620400_btu262-B36","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1056\/NEJMoa040465","article-title":"Prognostically useful gene-expression profiles in acute myeloid leukemia","volume":"350","author":"Valk","year":"2004","journal-title":"N. Engl. J. Med."},{"key":"2023012711102620400_btu262-B37","volume-title":"A Course in Combinatorics","author":"van Lint","year":"1992"},{"key":"2023012711102620400_btu262-B38","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein-protein interactions","volume":"417","author":"von Mering","year":"2002","journal-title":"Nature"},{"key":"2023012711102620400_btu262-B39","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/nar\/30.1.303","article-title":"DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions","volume":"30","author":"Xenarios","year":"2002","journal-title":"Nucleic Acids Res"},{"key":"2023012711102620400_btu262-B40","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1002\/pmic.200300636","article-title":"Functional and topological characterization of protein interaction networks","volume":"4","author":"Yook","year":"2004","journal-title":"Proteomics"},{"key":"2023012711102620400_btu262-B41","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1038\/nature10725","article-title":"The genetic basis of early T-cell precursor acute lymphoblastic leukaemia","volume":"481","author":"Zhang","year":"2012","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/12\/i96\/48925217\/bioinformatics_30_12_i96.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/12\/i96\/48925217\/bioinformatics_30_12_i96.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:50:09Z","timestamp":1674820209000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/12\/i96\/383457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,11]]},"references-count":41,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu262","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,6,15]]},"published":{"date-parts":[[2014,6,11]]}}}