Data import and preprocessing.

In the sequencing data import step, the genome is divided into fixed length bins of size nucleotides and short read counts in each bin are computed for each sample. Default is 300 nucleotides; a relatively large bin size is used to reduce spatial noise. Each sample is normalized for differences in sequencing depth by making the sum of bin counts constant across the genome. Optionally, a control sample is used to control for local variation in ChIP-seq by subtracting control bin counts from each non-control sample bin count.

After data import, we focus on a pre-defined genomic region , which is a chromosomal interval overlapping with a number of bins. To reduce spatial variation in bins, a median filter with a window of nine bins is applied within . To reduce noise caused by low signal, background level of the region is estimated as percentile in the bin count distribution within and this level is subtracted from all bins in the region. Negative counts are clamped to zero. As a result of preprocessing, we obtain an array of normalized bin counts for each sample.

Pattern matching.

The core of the SPINLONG approach is pattern matching by score optimization. A pattern encodes a hypothesis, such as “transcription of a gene is initiated close to its starting site after stimulus and transcription progresses from 5′ to 3′ direction.” A score indicates how well the bin counts of the current region match the pattern. The user can define the expected spatial arrangements of bin counts in the samples, a scoring scheme and optional constrains for optimization.

Pattern matching is done in the context of a genomic region and the pattern is evaluated against all defined regions, such as all genes in a genome. A pattern divides the bins of each sample into segments, which are non-overlapping sub-intervals of . Each segment is annotated with a label that describes the expected bin count class of the segment. The classes and denote “low” and “high” bin counts, respectively, and (ignored) denotes that the segment does not participate in scoring. Together, segments and their classes describe the expected spatial distribution of bin counts within samples. The user can define the number and classes of segments as well as their constraints, while their lengths are assigned in the optimization step.

Formally, the segments of a pattern are denoted as and their assigned lengths (in nucleotides) as , where . The lengths are assigned by a score-maximizing optimization process. Segment lengths are constrained by structural and user-defined constraints. An example of a structural constraint is the requirement that the segments in a sample must cover all the bins of the sample: , where denotes segments belonging to the specific sample and denotes the length of the current region. Optional user-defined constraints are used to fine tune and guide the optimization process. These constraints include segment length boundaries and global constraints (where ). Global constraints allow defining relationships within and between samples. These allow, for instance, expressing constraints between time points and distinct ChIP targets.

Pattern scoring.

The pattern scoring step evaluates each genomic region against the hypothesis and guides the optimization step. The result of the pattern scoring is the primary outcome of SPINLONG.

Pattern scoring uses assigned lengths () together with bin counts and segment classes to obtain a composite score. Patterns are scored in a two-step fashion, where individual segments are scored first and then combined into a composite score. A general scheme for segment scoring is to assign a score for each segment using the current length and state information (denoted ) maintained by the optimizer. We denote by segment scorer a data structure that is responsible for assigning scores to specific segments and maintains its dynamic state information .

All segments belonging to the same sample are scored with the same scorer, but there may be several independent scorers for independent sets of samples. Samples for distinct markers, such as PolII and H3K4me3, use separate scorers because their data ranges are different and segment scorers assume a common range for all associated samples. Segment score for a segment and scorer index is denoted .

Segment scoring using HMM.

Segment scoring is done using Hidden Markov Models (HMM) [33]. Bin counts are considered as Gaussian observations generated by states of the model. The default is two. The model is trained from all bins assigned to the scorer using the Baum-Welch method. HMM states are ordered based on the expected values of the Gaussian distributions in ascending order. HMM states of each bin are obtained using the Viterbi algorithm. HMM processing is done using JaHMM (http://code.google.com/p/jahmm/). Scorer state is the number of HMM states which are considered as low () class: this allows to use HMMs in the context of binary segment classes. The segment score is the proportion of bins whose HMM state matches the segment class: , where is the number of bins in the segment and is the HMM state of bin .

Composite scores.

Composite pattern scores are obtained from segment scores by interpreting them as fuzzy truth values [34]. We derived four basic composite scoring methods as follows. Composite scores and correspond to logical conjunction and disjunction, respectively. Of these, is generally more relevant for pattern matching: it means that “all segments match their respective class labels”. Between these extremes, includes information from all segment scores into the composite value, which is a desirable feature for guiding the optimization process. Combining and , we obtain that includes a conjunctive component while also taking into account all score values. In addition to these four methods, users can define custom composite score functions using nested min, max and weighted mean functions.

Nonlinear optimization.

Simulated annealing (SA) [23] is used to maximize composite score . Valid solution vectors for SA are that satisfy linear constraints for segment lengths ( is the number of scorers). In the SA step, either the vector or one of is modified. Segment lengths are modified using elementary operation vectors so that , where . Elementary operations are obtained from basis vectors of the linear space corresponding to valid vectors : if satisfies constraints, also does.

Preparation of MCF-7 cells.

The MCF-7 human breast cancer cell line originates from a 69-year old Caucasian woman and is estrogen receptor (ER) positive, progesterone positive (PR) and HER2 negative. Here MCF-7 cells (a clonal isolate kindly provided by Prof. Edison Liu, Jackson Laboratories, Maine, USA) were grown in 15 cm plates to 80% confluency. Plates were then washed 2 times with PBS and overlaid with 20 ml of phenol-red free high glucose DMEM (Gibco) containing 2% charcoal stripped FCS (Sigma). After 24 hours of incubation, the cells were again washed with PBS and fresh media containing 2% charcoal stripped FCS was added. This process was repeated over a three day period to generate cells devoid of estradiol signaling. The time course (10, 20, 40, 80, 160, 320, 640 and 1280 min) was initiated by replacing media with prewarmed media containing 10 nM E2. In addition, an untreated sample was included in the experiment as a zero time point.

ChIP-seq protocols and methods.

For chromatin immunoprecipitation, cells were fixed for 10 minutes at room temperature by the addition of formaldehyde to a final concentration of 1%, after which glycine was added to a concentration of 100 mM. Cells were then washed twice with PBS and collected into 2 ml of lysis buffer (150 mM NaCl, 20 mM Tris pH 8.0, 2 mM EDTA, 1% triton X-100, protease inhibitor [complete EDTA free, Roche, 04 693 132 001], 100 mM PMSF). The lysate was sonicated for 3×30 seconds using a Branson ultrasonicator equipped with a microtip on a power setting of 3 and a duty cycle of 90%. Samples were cooled on ice between rounds of sonication. Alternatively, a Bioruptor sonicator was used (power high, 15 mins total, 30 s on 30 s off; total volume of sample – 1 ml) to fragment chromatin. In either case, the resulting sonicate was centrifuged at 4000×g for 5 minutes, an aliquot of 10% retained for input and the remaining material transferred to a fresh tube.

Four of anti- antibody (HC-20, rabbit polyclonal, Santa Cruz, sc-543), of anti-RNA Polymerase II antibody (AC-055-100, monoclonal, Diagenode, 001), of anti-H3K4me3 antibody (pAb-MEHAHS-024, rabbit polyclonal, Diagenode, HC-0010) and anti-Histone H2A.Z (acetyl K4+K7+K11) antibody (ab18262, sheep polyclonal, Abcam, 659355) were added to the samples, which were then incubated overnight at with rotation. Chromatin antibody complexes were isolated, either by addition of of protein G labeled magnetic beads (Millipore Pureproteome protein G magnetic beads, LSKMAGG10) prewashed in lysis buffer or with protein A/G beads (Santa Cruz). Afterwards, the complexes obtained with protein G magnetic beads were washed three times with lysis buffer, then reverse crosslinked in 0.5 ml 5 M guanidine hydrochloride, 20 mM Hepes, 30% isopropanol, 10 mM EDTA for a minimum of 4 hours at . Recovered DNA was then purified using a Qiaquick spin column and eluted in of 10 mM Tris pH 8.0. Where protein A/G beads were used, the complexes were washed sequentially with three different buffers at : two times with solution of composition 0.1% SDS, 0.1% DOC, 1% Triton, 150 mM NaCl, 1 mM EDTA, 0.5 mM EGTA, 20 mM HEPES pH 7.6, once with the solution as before but with 500 mM NaCl, once with solution of composition 0.25 M LiCl, 0.5% DOC, 0.5% NP-40, 1 mM EDTA, 0.5 mM EGTA, 20 mM HEPES pH 7.6 and two times with 1 mM EDTA, 0.5 mM EGTA, 20 mM HEPES pH 7.6. A control library was generated by sequencing input DNA (non-ChIP genomic DNA). Immunopurified chromatin was eluted with of elution buffer (1% SDS, 0.1 M NaHCO3), incubated at for 4 h in the presence of 200 mM NaCl, isolated using a Qiaquick spin column and eluted in of 10 mM Tris pH 8.0.

To compute the associations between binding peaks and genes, we used an exponential distance model with a score threshold of one and unit intensity for all peaks [35]. Peak detection was done using MACS [20].

RNA-seq protocols.

Total RNA was isolated using Trizol (Invitrogen) according to the manufacturer's recommendations, followed by DNazol treatment (QIAGEN). 100–250 ng total RNA was subjected rRNA depletion with the Ribo-Zero rRNA Removal Kit (Human/Mouse/Rat; cat. no. RZH110424). The rRNA depleted sample was purified by ethanol precipitation. mRNA was fragmented by hydrolysis (5× fragmentation buffer: 200 mM Tris acetate, pH 8.2, 500 mM potassium acetate, and 150 mM magnesium acetate) at for 90 sec and then purified (RNeasy MinElute Cleanup Kit, QIAGEN). cDNA was synthesized using random hexamers using Superscript III Reverse Transcriptase (Invitrogen). ds-cDNA synthesis was performed in second strand buffer (Invitrogen) according to the manufacturer's recommendations and then purified (MinElute Reaction Cleanup Kit, QIAGEN). ds-cDNA was prepared for Illumina sequencing according to the manufacturer's protocols (Illumina). Briefly, ds-cDNA fragments were subject to sequential end repair and adaptor ligation. ds-cDNA fragments were subsequently size selected (approx. 300 base pair [bp]). The adaptor-modified DNA fragments were amplified by limited PCR (14 cycles). Quality control and concentration measurements were made by analysis of the PCR products by electrophoresis (Experion, BioRad) and by fluorometric dye binding using a Qubit fluorometer with the Quant-iT dsDNA HS Assay Kit (Invitrogen, Q32851) respectively. Cluster generation and sequencing-by-synthesis (36 bp) was performed using the Illumina Genome Analyzer IIx (GAIIx) according to standard protocols of the manufacturer (Illumina).

Alignment and preprocessing of sequencing data.

To align all reads, we used the GMS_map software (version 3.2.1) on a Genomatix Mining Station. The reference genome used was human hg19 (NCBI build 37). The software uses a seed-based approach to align reads. Mapping a read to a reference sequence involves two steps. In the first step, seeds for potential mapping positions in the target sequence are identified via a mapping library built of short unique subwords from the reference sequence. In the second step, alignments of the complete sequence read to the previously identified positions in the reference sequence are calculated. Results are ranked by their alignment score. We used the ‘deep’ seed search option allowing for point mutations during seed search. The overall alignment quality threshold was set to 92%, allowing for at most two point mutations. Uniquely and multiply matching reads meeting these thresholds were provided in BED and indexed BAM format.

SPINLONG patterns for identifying PolII activity regions.

To estimate PolII activity start and end sites, we combined the time points 0, 10, 20, 40 and 80 min together into a “pseudo-sample” that contains the maximum of bin counts in these time points. This was done individually for each marker (PolII, H3K4me3 and H2A.Z). These pseudo-samples contain information from all time points but also simplify pattern formulation by including only one (pseudo-) sample for each marker, instead of five samples for individual time points.

All pseudo-samples were divided into three segments with classes (low), (high) and , which correspond to the gene upstream, body and downstream, respectively. We thus obtained nine segments, denoted (PolII), (H3K4me3) and (H2A.Z), where . Based on the assumption that histone markers colocalize with PolII in promoters, histone upstream segments were synchronized with PolII using global constraints and : that is, the leftmost segments in each sample must be identical in length for all valid solutions .

Composite scoring was based on , but takes into account genes for which one or both histone markers are weakly present. The score function is , where is taking only PolII into account, is taking PolII and H3K4me3 into account, and similarly for other components. Offsets of 0.05 and 0.08 were chosen to bias the scorer to use all markers when possible.

SPINLONG patterns for identifying responder genes.

The assumption behind identifying genes whose activity levels are increased after a stimulus is that initially and without stimulation such a gene is transcribed with a low rate and thus there is little PolII activity across the gene. Similarly, we assume that genes whose activity is repressed after a stimulus initially show high PolII activity, which is decreased after a stimulus. For genes that are activated due to a stimulus, the PolII complex binds to the genomic regions at the transcription start site (TSS) of a responder gene. This is indicated by an increased number of reads in the 5′ end of the gene. These assumptions are used to form hypotheses used in SPINLONG.

Identification of estrogen responder genes is divided into identifying induced and repressed genes. For this analysis, PolII data were used at time points 0, 10, 20, 40 and 80 min; in addition, time points 160 and 640 min were used to compute a pseudo-sample (see below). The hypothesis for induced genes is that they show low signal (class ) in 0 time point and a progressively elongating high signal (class ) in later time points that represents a region of PolII binding. The class segment at time point is expected to be approximately two times longer than at time point , since time intervals increase geometrically and PolII elongation is assumed to be constant. This is encoded as a global linear constraint in the pattern, with the relaxation that length at must be at least 1.5 longer than at .

Patterns for induction are named inducedN, where is the time point at which the gene is fully occupied with PolII, i.e., the class segment covers the gene. The pattern induced80 captures long genes that are not completely transcribed at last time point. Repressed genes show similar behavior but with classes and swapped; these patterns are named repressedN.

The segment configuration of each pattern is visible in the result visualizations (Figures 2 and 3 and result WWW site) and in SPINLONG pattern XML files (Supporting Information). Scoring is done using . Genomic regions that are used as the search area are obtained from the predictions of PolII activity regions above, or from pre-defined Ensembl gene regions when the score in the activity prediction analysis is below 0.60. To allow the optimizer to further fine-tune the search area, these regions are extended by 25% in 5′ and 3′ directions and a pseudo-sample containing the maximum bin count of the time points 0, 10, 40, 160 and 640 min is included.

SPINLONG patterns for PolII propagation speed.

Estimation of PolII propagation speed is done using the segment lengths obtained in the identification of estrogen responsive genes above. For the patterns induced10 and repressed10, speed lower bound is estimated as nt/min, where is the length of class PolII segment at 10 minutes. For the patterns induced20 and repressed20, two speed estimates were computed as nt/min and nt/min, where is the length of class segment at 20 minutes. The minimum of these velocities gives the lower bound for the speed estimate. For 40 and 80 minute time points, lower bounds are computed in similar fashion using additionally and .

Survival analysis.

Survival analyses were conducted with the Anduril framework [32]. In all analyses, death from breast cancer was used as the event indicator. For the TCGA cohort [9], patients having ER+, HER2− and either post-menopausal status or age were selected. In addition, 65 healthy tissue samples were used as controls. For each gene, patients were divided into groups having low, high or stable expression. This was done by computing fold changes for each tumor and comparing them to a threshold based on the distribution of the fold changes. That is, let and be expression values for tumors and controls for a specific gene. Then, a median of control samples was computed. Sample-specific fold changes are and their standard deviation is . Now, a tumor was classified into the low (high) group for this gene if () and into the stable group otherwise.

In the Cox regression model for ATAD3B we used TNM tumor stage as a control variable [36]. TNM tumor stage is determined by the size of the tumor (T), lymph node involvement (N) and whether the cancer has metastasized (M). There are five stage categories from which 0 represents non-invasive cancer and IV means an invasive cancer that has metastasized to distant organs. For instance, a stage I tumor is an invasive cancer where the tumor is small () and which has not metastasized. Here we excluded stage 0 and combined subcategories for stage II (IIa and IIb) as well as for stage III (IIIa, IIIb and IIIc). In the Cox model, tumor stage is encoded as stage I = 1, II = 2, III = 3 and IV = 4.

The results published here are in part based upon data generated by The Cancer Genome Atlas pilot project established by the NCI and NHGRI. Information about TCGA and the investigators and institutions who constitute the TCGA research network can be found at http://cancergenome.nih.gov. The TSP study accession number in the database of Genotype and Phenotype (dbGaP) for the TCGA study used here is phs000569.v1.p7.

In the first ATAD3B validation cohort, Miller et al. [30], control samples and HER2 status were not available so patients having ER+ and age were selected. In the second validation cohort, Pawitan et al. [31], ER status or age were not reported so we selected all patients. Normalized microarray values were obtained using RMA [37]. In both cohorts, patients were grouped into “low” and “high” groups based on whether ATAD3B expression in the tumor sample was below or above expression median. A Kaplan-Meier analysis with the log-rank test was conducted based on these groupings for ATAD3B.