{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:42Z","timestamp":1763468082002},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1576,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Inferring the underlying regulatory pathways within a gene interaction network is a fundamental problem in Systems Biology to help understand the complex interactions and the regulation and flow of information within a system-of-interest. Given a weighted gene network and a gene in this network, the goal of an inference algorithm is to identify the potential regulatory pathways passing through this gene.<\/jats:p>\n               <jats:p>Results: In a departure from previous approaches that largely rely on the random walk model, we propose a novel single-source k-shortest paths based algorithm to address this inference problem. An important element of our approach is to explicitly account for and enhance the diversity of paths discovered by our algorithm. The intuition here is that diversity in paths can help enrich different functions and thereby better position one to understand the underlying system-of-interest. Results on the yeast gene network demonstrate the utility of the proposed approach over extant state-of-the-art inference algorithms. Beyond utility, our algorithm achieves a significant speedup over these baselines.<\/jats:p>\n               <jats:p>Availability: All data and codes are freely available upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0srini@cse.ohio-state.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts212","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T14:09:18Z","timestamp":1339423758000},"page":"i49-i58","source":"Crossref","is-referenced-by-count":30,"title":["A single source <i>k<\/i>-shortest paths algorithm to infer regulatory pathways in a gene network"],"prefix":"10.1093","volume":"28","author":[{"given":"Yu-Keng","family":"Shih","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, the Ohio State University, Columbus, OH, USA"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, the Ohio State University, Columbus, OH, USA"}]}],"member":"286","published-online":{"date-parts":[[2012,6,9]]},"reference":[{"key":"2023012512400150600_B1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1038\/75556","article-title":"Gene ontology: tool for the unification of biology","volume":"25","author":"Ashburner","year":"2000","journal-title":"Nat Genet."},{"key":"2023012512400150600_B2","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":"2023012512400150600_B3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1186\/1471-2105-8-335","article-title":"Pathfinder: mining signal transduction pathway segments from protein-protein interaction networks","volume":"8","author":"Bebek","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012512400150600_B4","doi-asserted-by":"crossref","first-page":"e70","DOI":"10.1371\/journal.pcbi.0020070","article-title":"Integrated Assessment and Prediction of Transcription Factor Binding","volume":"2","author":"Beyer","year":"2006","journal-title":"PLoS Comput Biol."},{"key":"2023012512400150600_B5","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1101\/gad.1804609","article-title":"The protein phosphatase 2a functions in the spindle position checkpoint by regulating the checkpoint kinase kin4","volume":"23","author":"Chan","year":"2009","journal-title":"Genes Dev."},{"key":"2023012512400150600_B6","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440222","volume-title":"Random Walks and Electric Networks","author":"Doyle","year":"1984"},{"key":"2023012512400150600_B7","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1186\/1471-2105-8-386","article-title":"Large scale statistical inference of signaling pathways from rnai and microarray data","volume":"8","author":"Froehlich","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012512400150600_B8","first-page":"509","article-title":"Fast top-k simple shortest paths discovery in graphs","author":"Gao","year":"2010","journal-title":"CIKM"},{"key":"2023012512400150600_B9","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1093\/molbev\/msi072","article-title":"Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks","volume":"22","author":"Hahn","year":"2005","journal-title":"Mol. Biol. Evol."},{"key":"2023012512400150600_B10","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","article-title":"Evidence for dynamically organized modularity in the yeast protein--protein interaction network","volume":"430","author":"Han","year":"2004","journal-title":"Nature"},{"key":"2023012512400150600_B11","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1109\/TKDE.2003.1208999","article-title":"Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search","volume":"15","author":"Haveliwala","year":"2003","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2023012512400150600_B12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/1290672.1290682","article-title":"Finding thekshortest simple paths: A new algorithm and its implementation","volume":"3","author":"Hershberger","year":"2007","journal-title":"TALG"},{"key":"2023012512400150600_B13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0092-8674(00)00015-5","article-title":"Functional discovery via a compendium of expression profiles","volume":"102","author":"Hughes","year":"2000","journal-title":"Cell"},{"key":"2023012512400150600_B14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/35075138","article-title":"Lethality and centrality in protein networks","volume":"411","author":"Jeong","year":"2001","journal-title":"Nature"},{"key":"2023012512400150600_B15","doi-asserted-by":"crossref","first-page":"e1207","DOI":"10.1371\/journal.pone.0001207","article-title":"Hubs with network motifs organize modularity dynamically in the protein-protein interaction network of yeast","volume":"2","author":"Jin","year":"2007","journal-title":"PLoS One"},{"key":"2023012512400150600_B16","first-page":"792","article-title":"A continuous query system for dynamic route planning","author":"Malviya","year":"2011","journal-title":"ICDE"},{"key":"2023012512400150600_B17","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nature750","article-title":"Comparative assessment of large-scale data sets of protein\u2013protein interactions","volume":"417","author":"Mering","year":"2002","journal-title":"Nature"},{"key":"2023012512400150600_B18","doi-asserted-by":"crossref","first-page":"e1000350","DOI":"10.1371\/journal.pcbi.1000350","article-title":"Information flow analysis of interactome networks","volume":"5","author":"Missiuro","year":"2009","journal-title":"PLoS Comput Biol"},{"key":"2023012512400150600_B19","first-page":"161","article-title":"Inferring protein\u2013protein interactions using interaction network topologies","volume":"1","author":"Paccanaro","year":"2005","journal-title":"IJCNN"},{"key":"2023012512400150600_B20","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1038\/nature04664","article-title":"Protein phosphatase 2a protects centromeric sister chromatid cohesion during meiosis i","volume":"441","author":"Riedel","year":"2006","journal-title":"Nature"},{"key":"2023012512400150600_B21","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","article-title":"Efficient algorithms for detecting signaling pathways in protein interaction networks","volume":"13","author":"Scott","year":"2006","journal-title":"J Comput. Biol."},{"issue":"(Suppl_1)","key":"2023012512400150600_B22","doi-asserted-by":"crossref","first-page":"D535","DOI":"10.1093\/nar\/gkj109","article-title":"Biogrid: a general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucl. Acids Res."},{"key":"2023012512400150600_B23","doi-asserted-by":"crossref","first-page":"2447","DOI":"10.1093\/bioinformatics\/btp398","article-title":"ITM probe: analyzing information flow in protein networks","volume":"25","author":"Stojmirovi\u00e9","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012512400150600_B24","doi-asserted-by":"crossref","first-page":"2752","DOI":"10.1093\/bioinformatics\/btq511","article-title":"Robust and accurate data enrichment statistics via distribution function of sum of weights","volume":"26","author":"Stojmirovi\u00e9","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012512400150600_B25","article-title":"Information flow in interaction networks II: channels, path lengths and potentials","author":"Stojmirovi\u00e9","year":"2011","journal-title":"ArXiv e-prints"},{"key":"2023012512400150600_B26","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1038\/msb.2008.4","article-title":"eQED: an efficient method for interpreting eqtl associations using protein networks","volume":"4","author":"Suthram","year":"2008","journal-title":"Mol. Syst. Biol."},{"key":"2023012512400150600_B27","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1093\/bioinformatics\/btl234","article-title":"An integrative approach for causal gene identification and gene regulatory pathway inference","volume":"22","author":"Tu","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012512400150600_B28","doi-asserted-by":"crossref","first-page":"e1000274","DOI":"10.1371\/journal.pcbi.1000274","article-title":"A factor graph nested effects model to identify networks from genetic perturbations","volume":"5","author":"Vaske","year":"2009","journal-title":"PLoS Comput Biol"},{"key":"2023012512400150600_B29","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1186\/1752-0509-3-112","article-title":"Spectral affinity in protein networks","volume":"3","author":"Voevodski","year":"2009","journal-title":"BMC Syst. Biol."},{"key":"2023012512400150600_B30","doi-asserted-by":"crossref","first-page":"1570","DOI":"10.1074\/jbc.M008694200","article-title":"Carboxymethylation of the pp2a catalytic subunit insaccharomyces cerevisiae is required for efficient interaction with the b-type subunits cdc55p and rts1p","volume":"276","author":"Wei","year":"2001","journal-title":"J. Biol. Chem."},{"key":"2023012512400150600_B31","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","article-title":"Finding thekshortest loopless paths in a network","volume":"17","author":"Yen","year":"1971","journal-title":"Management Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i49\/48884575\/bioinformatics_28_12_i49.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i49\/48884575\/bioinformatics_28_12_i49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T16:43:12Z","timestamp":1674664992000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/12\/i49\/268145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,9]]},"references-count":31,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts212","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,6,15]]},"published":{"date-parts":[[2012,6,9]]}}}