title: Fast randomization of large genomic datasets while preserving alteration counts.
abstract: BACKGROUND
  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.
  
  
  METHODS
  BiRewire is available on BioConductor at http://www.bioconductor.org/packages/2.13/bioc/html/BiRewire.html.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: 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.
authors.forename: Andrea
authors.initials: A
authors.lastname: Gobbi
authors.affiliation: 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 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.
authors.forename: Francesco
authors.initials: F
authors.lastname: Iorio
authors.affiliation: 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.
authors.forename: Kevin J
authors.initials: KJ
authors.lastname: Dawson
authors.affiliation: 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.
authors.forename: David C
authors.initials: DC
authors.lastname: Wedge
authors.affiliation: 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.
authors.forename: David
authors.initials: D
authors.lastname: Tamborero
authors.affiliation: 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.
authors.forename: Ludmil B
authors.initials: LB
authors.lastname: Alexandrov
authors.affiliation: 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.
authors.forename: Nuria
authors.initials: N
authors.lastname: Lopez-Bigas
authors.affiliation: 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.
authors.forename: Mathew J
authors.initials: MJ
authors.lastname: Garnett
authors.affiliation: 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.
authors.forename: Giuseppe
authors.initials: G
authors.lastname: Jurman
authors.affiliation: 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.
authors.forename: Julio
authors.initials: J
authors.lastname: Saez-Rodriguez
mesh_terms: D000465:Algorithms; D023281:Genomics / Q000379:methods*; D006801:Humans; D008390:Markov Chains; D009010:Monte Carlo Method; D009369:Neoplasms / Q000235:genetics; D011897:Random Allocation; D012984:Software