Cookies on this website
We use cookies to ensure that we give you the best experience on our website. If you click 'Continue' we'll assume that you are happy to receive all cookies and you won't see this message again. Click 'Find out more' for information on how to change your cookie settings.

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 'mutually exclusive' 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. 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. AVAILABILITY AND IMPLEMENTATION:BiRewire is available on BioConductor at SUPPLEMENTARY INFORMATION:Supplementary data are available at Bioinformatics online.

Original publication




Journal article


Bioinformatics (Oxford, England)

Publication Date





i617 - i623


Fondazione Bruno Kessler, I-38100 Povo (Trento), Italy, European Molecular Biology Laboratory, European Bioinformatics Institute, Cambridge CB10 1SD, UK, Wellcome Trust Sanger Institute, Cambridge CB10 1SD, UK and Universitat Pompeu Fabra, Barcelona 08003, Spain.


Humans, Neoplasms, Monte Carlo Method, Markov Chains, Random Allocation, Genomics, Algorithms, Software