GAT: a simulation framework for testing the association of genomic intervals

1A common question in genomic analysis is whether two sets of genomic intervals, for example, ChIP-seq peaks and gene annotation classes, overlap significantly more than expected by chance alone. Interval overlap is easy to compute, but the significance can be computed analytically only for trivial situations. Hence, significance is usually estimated by simulation under some null model. This model must account for genome organization; a model that assumes independent and uniform placement of both interval sets is almost always inappropriate when testing for association with gene annotations because gene density strongly correlates with G + C content, and datasets of interest often also show G + C biases.

2Here, we introduce Genomic Association Test (GAT), a tool for computing the significance of overlap between multiple sets of genomic intervals. GAT permits the restriction of the analysis to parts of a genome relevant to the experiment and accounts for chromosomal and isochore biases. Additional genomic features can be controlled for by providing additional segmentation files.

3GAT’s approach was developed originally to test for the association of non-coding transcripts with other genomic elements, but has since been applied to a variety of problems, including: Conservation of non-coding transcription between human and mouse;Enrichment of histone marks and evolutionarily conserved genomic regions within non-coding transcripts;Functional prediction of non-coding transcripts via their neighboring genes; andEnrichment of ChIP-Seq binding events within signatures of open chromatin or disease-associated intervals.

4Conservation of non-coding transcription between human and mouse;

5Enrichment of histone marks and evolutionarily conserved genomic regions within non-coding transcripts;

6Functional prediction of non-coding transcripts via their neighboring genes; and

7Enrichment of ChIP-Seq binding events within signatures of open chromatin or disease-associated intervals.

8GAT's re-implementation delivers to the scientific community the extended functionality of the methods.

9GAT is controlled from the command line. It requires at least three bed-formatted files that delimit genomic intervals (tuples of chromosome, start and end). The principal output of GAT is a table listing significant overlaps.

10Example: does a set of transcription factor binding site intervals from a ChIP-Seq experiment overlaps more than expected by chance with a set of DNaseI-hypersensitive sites? To perform this analysis, GAT requires three files: A bed-formatted file with the intervals from the ChIP-Seq experiment (Segments S). Several experiments can be supplied as multiple files or as a single file with multiple tracks.A bed-formatted file with DNaseI-hypersensitive sites (Annotations A). These could be obtained directly from the UCSC Genome Browser (Rosenbloom et al., 2012). Several annotations from, for example, multiple cell lines can be supplied as multiple files or as a single file with multiple tracks.A bed-formatted file with the workspace (W). The workspace defines the sequence that is accessible for the simulation. The simplest workspace contains the full genome assembly. In this example, the analysis should be restricted to only repeat-free regions, as only these are reliably mappable by short read data and thus could contain ChIP-Seq intervals. Again, appropriate bed-formatted files are available from the UCSC Genome Browser.

11A bed-formatted file with the intervals from the ChIP-Seq experiment (Segments S). Several experiments can be supplied as multiple files or as a single file with multiple tracks.

12A bed-formatted file with DNaseI-hypersensitive sites (Annotations A). These could be obtained directly from the UCSC Genome Browser (Rosenbloom et al., 2012). Several annotations from, for example, multiple cell lines can be supplied as multiple files or as a single file with multiple tracks.

13A bed-formatted file with the workspace (W). The workspace defines the sequence that is accessible for the simulation. The simplest workspace contains the full genome assembly. In this example, the analysis should be restricted to only repeat-free regions, as only these are reliably mappable by short read data and thus could contain ChIP-Seq intervals. Again, appropriate bed-formatted files are available from the UCSC Genome Browser.

14By default, the randomization procedure accounts for differences among chromosomes; for example, the X chromosome contains many sequence features that are atypical of autosomes. In addition to chromosome identity, local genomic G + C content is another common confounding factor. For example, G + C content might cause experimental biases in sequencing and hybridization protocols, while it is also a correlate of gene density. To correct for G + C content, an optional bed-formatted file with the isochore structure of the genome can be supplied. GAT will then normalize by isochore and by chromosome. Here, isochores are discretized, for example, the genome is partitioned into windows falling into eight bins of different regional G + C content.

15In the aforementioned example, GAT will compute the overlap of ChIP-Seq binding events and DNaseI-hypersensitive sites. GAT will also estimate if the overlap is larger or smaller than expected by chance and will provide an empirical P-value of the statistical significance. If multiple ChIP-Seq experiments or multiple annotations have been submitted, GAT will compute the overlap for each combination of experiment and annotation and will estimate its significance. Storey's q-value or the Benjamini–Hochberg method is used to control for multiple testing using a False discovery rate (FDR) procedure.

16GAT is a python script (http://python.org) requiring only common and freely available numerical and scientific libraries. The memory and time-critical parts are implemented in cython (http://cython.org). It requires two collections of genomic intervals: Segments (S) and Annotations (A). Each collection can contain one or more lists of genomic intervals (S1, S2, …, Sm; A1, A2, …, An). Intervals within a list of genomic intervals are required to be non-overlapping, and any overlapping intervals within S or A are merged prior to analysis. In addition, GAT requires a Workspace W describing the part of the genome accessible to the simulation. The analysis proceeds as follows. For each pair of interval lists Sx and Ay (x ∈ {1, …, m}, y ∈{1, …, n}), GAT computes the overlap between the intervals in Sx and Ay within workspace W: observed = |Sx∩ Ay∩ W|. |Here,| is the overlap operator and defaults to the number of nucleotides overlapping, but other operators (such as the number of segments) can be used. GAT subsequently creates randomly placed intervals in the genome with the same size distribution of Sx within the workspace W. See below for simulation details. The overlap between each simulated set and Ay is recorded. The average over all simulations represents the expected overlap. GAT reports the fold enrichment as the ratio of observed and expected overlap and associates an empirical P-value with it. GAT’s runtime and memory usage scale linearly with the number of simulations and the number and size of the genomic interval sets S, A and W.

17The sampling method creates a list R of randomly placed intervals from an interval list Sx within a workspace W. The sampling is done on a per-chromosome basis. For each chromosome c, randomly placed intervals are created by a two-step procedure: Select an interval size from the empirical interval size distribution Sx,c.Select a position within the workspace Wc.

18Select an interval size from the empirical interval size distribution Sx,c.

19Select a position within the workspace Wc.

20Sampled intervals are added to Rc until exactly the same number of nucleotides are in Rc as are in Sx,c. For reasons of performance, intervals are initially sampled without checking for overlap. Overlaps and overshoot are subsequently resolved in an iterative procedure once the sampled number of nucleotides approximates the target number.

21The current sampling protocol is restricted to non-overlapping single segment intervals. Although amenable to many genomic features, it notably leaves discontinuous genomic segments, such as transcripts, untreated.

22Isochores are defined within GAT as chromosomal segments within a workspace. For each isochore i, the workspace W is subdivided into a workspace Wi = W ∩ Ii. The sampling is performed separately for each Wi and samples combined at the end. Isochores are thus treated in an equivalent manner to chromosomes. Isochores can be defined by G + C content, but can reflect any segmentation of the genome, such as chromatin marks.

23GAT provides critical functionality for genomic analyses. By using standard BED files, it may be used alongside major data resources, such as the UCSC Genome Browser and Galaxy. GAT can be used in a similar context to GREAT and other tools, but can address a more diverse range of questions because of its simulation approach that takes into account both segment and annotation size distributions.

24Funding: UK Medical Research Council.

25Conflict of Interest: none declared.