indicating that Ty elements populating the RM genome are Ty2 only. Of these 10 Ty2 elements found in RM, 3 were located at the same place in BY, 6 were located elsewhere in RM (leading to 6 deletions (insertions) in BY (RM)) and 1 replaced a Ty1 element of BY. Other annotations and data used Conserved Regulatory Sites (CRS) [35] were downloaded from (http:// fraenkel.mit.edu/improved_map/p001_c3.gff). Conserved Non-Coding Sites were obtained from the UCSC website (http://genome.ucsc. edu/), using data from table phastConsElements for track MostCon- served, and were then defined as the intersection between conserved regions and non-coding regions. Gene expression values of Brem et al. [20] were downloaded from NCBI GEO site (http://www. ncbi.nlm.nih.gov/sites/entrez?db = gds, dataset GSE1990). Regions where nucleosome(s) were remodeled upon heat-shock were ex- tracted from whole-genome nucleosome maps of Shivaswamy et al. [26] filtered for nucleosomes of normalized score ,0.2. They were defined as chunks of at least 145 consecutive nucleotides (average size of a nucleosome) covered by a nucleosome in only one condition (unstressed or heat-shock). Using our BY atlas of nucleosome positions (see below), 147 nucleosomes (,0.2%) were then said to be remodeled if they lied entirely within a remodeled region. Microarray analysis The 25 bp array probes were mapped on BY and RM genomes using MUMmer. For each strain, we kept only probes that had unique perfect match on the genome (2,801,885 probes for BY and 2,570,638 probes for RM, overlap: 2,491,913 probes). For nucleosome mapping (see below) we used only the 3 array replicates per strain. Since informative probe sets differed between the two strains, normalization was done separately for each strain and a log2 transformation of probe signals was applied before normalization [55]. For SNEP identification (see below), only the subset of RM probes that can be mapped within 63 bp of the corresponding probe in BY was kept to insure that at every positions the same probe is used between the two strains. In addition, since any DNA polymorphism would bias hybridization efficiency, we discarded probes containing at least one BY/RM polymorphism, keeping a final core set of 2,356,676 probes. Then the full dataset (18 arrays) was log2-transformed and quantile- normalized all together using only this set of probes with dual perfect match. Nucleosome mapping We positioned nucleosomes in each strain separately using only the 3 dedicated replicates per strain. We then implemented a custom version of the Hidden Markov Model devised by Yuan et al. [25]. Our HMM implementation was similar to the one used by Lee et al. [24], except than we did not train the HMM on specific regions but used sliding windows as in Yuan et al. in order to remove unpredictable trends in the hybridization signal. Thus, independent run of the HMM were successively applied in window of 1 kb (i.e. ,250 probes) all along the genome. The model parameters and posteriors of all windows containing a fixed probe were then averaged and used for a global computation of both state probabilities and most-likely states (among well- positioned nucleosome, fuzzy nucleosome and linker). As we used only probes with unique and perfect matches and that regions with high SNP density between BY and RM can lead locally to low probe coverage in RM, we also allowed the HMM to deal with missing data. State probabilities and most-likely states of ‘‘missing probes’’ were computed in the same way than for observed probes, taking advantage of neighboring observed information. Single Nucleosome Epi-Polymorphisms Nucleosome alignment The most-likely nucleosome occupancy profiles of the two strains (as obtained from the Viterbi algorithm on each chromosome) were aligned according to the genome alignments. The BY genome was the reference and the positions of RM nucleosomes on this reference were obtained from the coordinates of RM nucleosomal sequence fragments on the BY genome. Once RM nucleosomes were ‘‘mapped’’ on BY, we used a dynamic algorithm to align RM and BY nucleosomes. The algorithm works chromosome-by-chromosome as follows: 1) 2) 3) Assumption: two nucleosomes are said to be ‘‘unambiguously aligned’’ if the distance between their midpoints is lower than half of their average size. Initiation: find all unambiguously aligned nucleosomes along the chromosome. Recursion: between two consecutive unambiguously aligned nucleosomes: i) if there is no unaligned nucleosome in the interval, then go to the next unambiguously aligned nucleosome. ii) else: a) b) c) Align nucleosomes by minimizing physical distance between aligned pairs. The remaining nucleosome(s) are considered as insertion(s) (if they are BY nucleosomes) or dele- tion(s) (if they are RM nucleosomes). Go to the next unambiguously aligned nucleosome. More stringent assumptions can be used to define ‘‘unambig- uously aligned’’ nucleosomes without significant changes on the final results (data not shown). This strategy aligned 64,294 nucleosomes between the two strains, i.e. ,95% of RM nucleosomes. Finally, in order to evaluate locally the quality of our alignment, for each pair of aligned nucleosomes we computed their likelihood as L(aligned) = Bn.Rn where Bn and Rn are the probabilities that the corresponding probes belong to a nucleo- some in BY and RM, respectively. Similarly, we computed the likelihood for insertion and deletion of a nucleosome (with respect to BY) as L(insertion) = Bn*Rl and L(deletion) = Bl*Rn where Bl and Rl are the probabilities that the corresponding probes belong to a linker in BY and RM, respectively. Within each strain, the probability of each state (nucleosome or linker) was derived from probe-level posterior probabilities (as estimated by our HMM, and merging fuzzy and well-positioned nucleosome states into a single class) averaged over probes covering the target region. Promoter clustering To generate Figure 1B and 1C, we first divided the +/2300 bp region around the TSS of each transcript into 60 bins of equal size (10 bp). We then computed the average nucleosome occupancy in each bin by averaging the posterior probabilities to be a nucleosome (output by our HMM and summing posteriors from well-positioned and fuzzy nucleosomal states) of the probes within the bin. We then applied K-means clustering (with kmeans function implemented in the base package of R) using the Euclidean distance metric and 25 repetitions for each number of cluster tested (1, = K, = 10). Visual inspection together with standard clustering validity measures (e.g. ratio of variance within clusters and variance between clusters) were used to choose the optimal number of clusters (K = 6). PLoS Genetics | www.plosgenetics.org 10 April 2010 | Volume 6 | Issue 4 | e1000913