{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:26:49Z","timestamp":1763663209756},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":772,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Studying combinatorial patterns in cancer genomic datasets has recently emerged as a tool for identifying novel cancer driver networks. Approaches have been devised to quantify, for example, the tendency of a set of genes to be mutated in a \u2018mutually exclusive\u2019 manner. The significance of the proposed metrics is usually evaluated by computing P-values under appropriate null models. To this end, a Monte Carlo method (the switching-algorithm) is used to sample simulated datasets under a null model that preserves patient- and gene-wise mutation rates. In this method, a genomic dataset is represented as a bipartite network, to which Markov chain updates (switching-steps) are applied. These steps modify the network topology, and a minimal number of them must be executed to draw simulated datasets independently under the null model. This number has previously been deducted empirically to be a linear function of the total number of variants, making this process computationally expensive.<\/jats:p><jats:p>Results: We present a novel approximate lower bound for the number of switching-steps, derived analytically. Additionally, we have developed the R package BiRewire, including new efficient implementations of the switching-algorithm. We illustrate the performances of BiRewire by applying it to large real cancer genomics datasets. We report vast reductions in time requirement, with respect to existing implementations\/bounds and equivalent P-value computations. Thus, we propose BiRewire to study statistical properties in genomic datasets, and other data that can be modeled as bipartite networks.<\/jats:p><jats:p>Availability and implementation: BiRewire is available on BioConductor at http:\/\/www.bioconductor.org\/packages\/2.13\/bioc\/html\/BiRewire.html<\/jats:p><jats:p>Contact: \u00a0iorio@ebi.ac.uk<\/jats:p><jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu474","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T11:23:57Z","timestamp":1409052237000},"page":"i617-i623","source":"Crossref","is-referenced-by-count":34,"title":["Fast randomization of large genomic datasets while preserving alteration counts"],"prefix":"10.1093","volume":"30","author":[{"given":"Andrea","family":"Gobbi","sequence":"first","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Francesco","family":"Iorio","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"},{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Kevin J.","family":"Dawson","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"David C.","family":"Wedge","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"David","family":"Tamborero","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Ludmil B.","family":"Alexandrov","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Nuria","family":"Lopez-Bigas","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Mathew J.","family":"Garnett","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Giuseppe","family":"Jurman","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]},{"given":"Julio","family":"Saez-Rodriguez","sequence":"additional","affiliation":[{"name":"1 Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, 2European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, 3Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and 4Universitat Pompeu Fabra, Barcelona 08003, Spain"}]}],"member":"286","published-online":{"date-parts":[[2014,8,22]]},"reference":[{"key":"2023012711543915000_btu474-B1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0378-4371(99)00291-5","article-title":"Mean-field theory for scale-free random networks","volume":"272","author":"Barab\u00e1si","year":"1999","journal-title":"Physica A"},{"key":"2023012711543915000_btu474-B2","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1038\/nature11003","article-title":"The Cancer Cell Line Encyclopedia enables predictive modelling of anticancer drug sensitivity","volume":"483","author":"Barretina","year":"2012","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B3","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1093\/biomet\/76.4.633","article-title":"Generalized montecarlo significance tests","volume":"76","author":"Besag","year":"1989","journal-title":"Biometrika"},{"key":"2023012711543915000_btu474-B4","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1038\/nature08768","article-title":"Signatures of mutation and selection in the cancer genome","volume":"463","author":"Bignell","year":"2010","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B5","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1080\/10618600.1998.10474787","article-title":"General methods for monitoring convergence of iterative simulations","volume":"7","author":"Brooks","year":"1998","journal-title":"J. Comput. Graph. Stat."},{"key":"2023012711543915000_btu474-B6","volume-title":"Linear Recursion and Fibonacci Sequences","author":"Brousseau","year":"1971"},{"key":"2023012711543915000_btu474-B7","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature07385","article-title":"Comprehensive genomic characterization defines human glioblastoma genes and core pathways","volume":"455","author":"Cancer Genome Atlas Research Network","year":"2008","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B8","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1101\/gr.125567.111","article-title":"Mutual exclusivity analysis identifies oncogenic network modules","volume":"22","author":"Ciriello","year":"2012","journal-title":"Genome Res."},{"key":"2023012711543915000_btu474-B9","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.2307\/1936961","article-title":"The assembly of species communities: chance or competition?","volume":"60","author":"Connor","year":"1979","journal-title":"Ecology"},{"key":"2023012711543915000_btu474-B10","first-page":"1695","article-title":"The igraph software package for complex network research","volume":"38","author":"Csardi","year":"2006","journal-title":"Int. J. Complex Syst."},{"key":"2023012711543915000_btu474-B11","doi-asserted-by":"crossref","first-page":"e13180","DOI":"10.1371\/journal.pone.0013180","article-title":"A network of cancer genes with co-occurring and anti-co-occurring mutations","volume":"5","author":"Cui","year":"2010","journal-title":"PLoS One"},{"key":"2023012711543915000_btu474-B12","first-page":"e13180","article-title":"VEGAN, a package of R functions for community ecology","volume":"5","author":"Dixon","year":"2003","journal-title":"J. Veg. Sci."},{"key":"2023012711543915000_btu474-B13","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1038\/nature11005","article-title":"Systematic identification of genomic markers of drug sensitivity in cancer cells","volume":"483","author":"Garnett","year":"2012","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B14","doi-asserted-by":"crossref","first-page":"R80","DOI":"10.1186\/gb-2004-5-10-r80","article-title":"Bioconductor: open software development for computational biology and bioinformatics","volume":"5","author":"Gentleman","year":"2004","journal-title":"Genome Biol."},{"key":"2023012711543915000_btu474-B15","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1890\/0012-9658(2000)081[2606:NMAOSC]2.0.CO;2","article-title":"Null model analysis of species co-occurrence patterns","volume":"81","author":"Gotelli","year":"2000","journal-title":"Ecology"},{"key":"2023012711543915000_btu474-B16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s004420100717","article-title":"Swap and fill algorithms in null model analy-sis: rethinking the knight\u2019s tour","volume":"129","author":"Gotelli","year":"2001","journal-title":"Oecologia"},{"key":"2023012711543915000_btu474-B17","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1038\/nature05610","article-title":"Patterns of somatic mutation in human cancer genomes","volume":"446","author":"Greenman","year":"2007","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B18","volume-title":"Graph Theory and Its Applications","author":"Gross","year":"2006"},{"key":"2023012711543915000_btu474-B19","doi-asserted-by":"crossref","first-page":"2186","DOI":"10.1158\/1535-7163.MCT-10-0022","article-title":"Systematic interpretation of comutated genes in large-scale cancer mutation profiles","volume":"9","author":"Gu","year":"2010","journal-title":"Mol. Cancer Ther."},{"key":"2023012711543915000_btu474-B20","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1016\/j.cell.2011.02.013","article-title":"Hallmarks of cancer: the next generation","volume":"144","author":"Hanahan","year":"2011","journal-title":"Cell"},{"key":"2023012711543915000_btu474-B21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1080\/10618600.1996.10474713","article-title":"R: a language for data analysis and graphics","volume":"5","author":"Ihaka","year":"1996","journal-title":"J. Computat. Graph. Stat."},{"key":"2023012711543915000_btu474-B22","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1038\/nature08987","article-title":"International network of cancer genome projects","volume":"464","author":"International Cancer Genome Consortium et al.","year":"2010","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B23","first-page":"142","article-title":"Etude comparative de la distribution florale dans une portion des Alpes et du Jura","volume":"37","author":"Jaccard","year":"1901","journal-title":"Bulletin de la Socit Vaudoise des Sciences Naturelles"},{"key":"2023012711543915000_btu474-B24","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1080\/01621459.1996.10476672","article-title":"Studying convergence of Markov chain Monte Carlo algorithms using coupled sample paths","volume":"91","author":"Johnson","year":"1996","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012711543915000_btu474-B25","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1890\/03-0101","article-title":"Randomization of presence-absence matrices: comments and new algorithms","volume":"85","author":"Mikl\u00f3s","year":"2004","journal-title":"Ecology"},{"key":"2023012711543915000_btu474-B26","first-page":"86","article-title":"Discovering functional modules by identifying recurrent and mutually exclusive mutational patterns in tumors","volume":"85","author":"Miller","year":"2011","journal-title":"BMC Med. Genomics"},{"key":"2023012711543915000_btu474-B27","article-title":"On the uniform generation of random graphs with prescribed degree sequences","volume-title":"Arxiv preprint cond-mat","author":"Milo","year":"2003"},{"key":"2023012711543915000_btu474-B28","first-page":"91","article-title":"Algorithm AS 159: an efficient method of generating random RxC tables with given row and column totals","volume":"30","author":"Patefield","year":"1981","journal-title":"J. R. Stat. Soc."},{"key":"2023012711543915000_btu474-B29","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF02294444","article-title":"Nonparametric goodness-of-fit tests for the Rasch model","volume":"66","author":"Ponocny","year":"2001","journal-title":"Psychometrika"},{"key":"2023012711543915000_btu474-B30","volume-title":"Probabilistic Models for Some Intelligence and Attainment Tests","author":"Rasch","year":"1993"},{"key":"2023012711543915000_btu474-B31","article-title":"Are we there yet? When to stop a markov chain while generat-ing random graphs","author":"Ray","year":"2012"},{"key":"2023012711543915000_btu474-B32","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4899-0319-8_6","article-title":"Monte Carlo methods in statistical mechanics: foundations and new algorithms Functional Integration","volume":"361","author":"Sokal","year":"1989","journal-title":"NATO ASI Series"},{"key":"2023012711543915000_btu474-B33","doi-asserted-by":"crossref","first-page":"3.1","DOI":"10.1145\/2133803.2330086","article-title":"Constructing and sampling graphs with a prescribed joint degree distribution","volume":"17","author":"Stanton","year":"2012","journal-title":"J. Exp. Algorithmics"},{"key":"2023012711543915000_btu474-B34","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1038\/nature07943","article-title":"The cancer genome","volume":"458","author":"Stratton","year":"2009","journal-title":"Nature"},{"key":"2023012711543915000_btu474-B35","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1038\/ng0407-567a","article-title":"High-throughput oncogene mutation profiling in human cancer","volume":"39","author":"Thomas","year":"2007","journal-title":"Nat. Genetics."},{"key":"2023012711543915000_btu474-B36","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1016\/j.cell.2008.03.021","article-title":"Large-scale mutagenesis in p19ARF-and p53-deficient mice identifies cancer genes and yheir collaborative networks","volume":"133","author":"Uren","year":"2008","journal-title":"Cell"},{"key":"2023012711543915000_btu474-B37","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1101\/gr.120477.111","article-title":"De novo discovery of mutated driver pathways in cancer","volume":"22","author":"Vandin","year":"2012","journal-title":"Genome Res."},{"key":"2023012711543915000_btu474-B38","doi-asserted-by":"crossref","first-page":"1546","DOI":"10.1126\/science.1235122","article-title":"Cancer genome landscapes","volume":"339","author":"Vogelstein","year":"2013","journal-title":"Science"},{"key":"2023012711543915000_btu474-B39","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/BF00379419","article-title":"Methods for detecting non-randomness in species co-occurrences: a contribution","volume":"73","author":"Wilson","year":"1987","journal-title":"Oecologia"},{"key":"2023012711543915000_btu474-B40","doi-asserted-by":"crossref","first-page":"2605","DOI":"10.1096\/fj.08-108985","article-title":"Combinatorial patterns of somatic gene mutations in cancer","volume":"22","author":"Yeang","year":"2008","journal-title":"FASEB J."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i617\/48927732\/bioinformatics_30_17_i617.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i617\/48927732\/bioinformatics_30_17_i617.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T22:43:51Z","timestamp":1717281831000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/17\/i617\/201366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,22]]},"references-count":40,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu474","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,9,1]]},"published":{"date-parts":[[2014,8,22]]}}}