Detecting independent and recurrent copy number aberrations using interval graphs. Academic Article uri icon



  • Humans
  • Neoplasms

MeSH Major

  • Algorithms
  • DNA Copy Number Variations


  • Somatic copy number aberrations SCNAS: are frequent in cancer genomes, but many of these are random, passenger events. A common strategy to distinguish functional aberrations from passengers is to identify those aberrations that are recurrent across multiple samples. However, the extensive variability in the length and position of SCNA: s makes the problem of identifying recurrent aberrations notoriously difficult. We introduce a combinatorial approach to the problem of identifying independent and recurrent SCNA: s, focusing on the key challenging of separating the overlaps in aberrations across individuals into independent events. We derive independent and recurrent SCNA: s as maximal cliques in an interval graph constructed from overlaps between aberrations. We efficiently enumerate all such cliques, and derive a dynamic programming algorithm to find an optimal selection of non-overlapping cliques, resulting in a very fast algorithm, which we call RAIG (Recurrent Aberrations from Interval Graphs). We show that RAIG outperforms other methods on simulated data and also performs well on data from three cancer types from The Cancer Genome Atlas (TCGA). In contrast to existing approaches that employ various heuristics to select independent aberrations, RAIG optimizes a well-defined objective function. We show that this allows RAIG to identify rare aberrations that are likely functional, but are obscured by overlaps with larger passenger aberrations. © The Author 2014. Published by Oxford University Press.

publication date

  • June 15, 2014

has subject area

  • Algorithms
  • DNA Copy Number Variations
  • Humans
  • Neoplasms



  • Journal Article



  • eng

PubMed Central ID

  • PMC4058951

Digital Object Identifier (DOI)

  • 10.1093/bioinformatics/btu276

PubMed ID

  • 24931984

Additional Document Info

start page

  • i195

end page

  • i203


  • 30


  • 12