BACKGROUND
in the nucleus, genomic dna exists in the form of chromatin, which is tightly packaged and organized into higher-level structures required for proper genome function  <cit> .
chromatin conformation is highly dynamic and modified by several biological processes such as dna replication, repair and transcription.
the three-dimensional chromatin organization itself was recently found to play an important role in transcription regulation  <cit>  and can be used to define chromatin signatures  <cit> .
for example, it was shown that elements that lie far apart in the one-dimensional genomic sequence or on different chromosomes could functionally interact through physical contacts  <cit> .
one such example is the 100-kb imprinted igf2/h <dig> locus on human chromosome  <dig> where there exists an imprinting control region  located between the igf <dig> gene and its enhancer sequence.
on the maternal allele, ctcf  is able to bind the unmethylated icr and subsequently forms multiple long-range looping contacts along the locus that block gene-enhancer interaction.
however, the paternal icr is methylated and cannot be bound by ctcf, thus allowing the igf <dig> gene and its enhancer sequence to interact through a long-range loop, thereby regulating expression to only the paternal allele  <cit> .
such long-range interactions have been found throughout metazoan genomes where thus far many of them appear to correlate well with the transcriptional state of target genes  <cit> .
although we still do not know how many types of contacts exist or how the majority of them are regulated, it is now clear that spatial transcriptional control is an important mechanism of gene regulation.
thus, mapping of physical contacts within  and between  chromosomes will be essential to fully understand gene regulation.
several techniques are now available to examine chromatin structure at high-resolution, such as damid  <cit> , and more recent approaches including chromosome conformation capture   <cit> , circular chromosome conformation capture   <cit> , chromosome conformation capture carbon copy   <cit> , chromatin interaction analysis with paired-end tag sequencing   <cit> , the technology developed by duan et al.
<cit> , and hi-c  <cit> .
these techniques combine various high-throughput approaches, such as microarrays and next-generation sequencing, and produce large datasets.
in the case of 5c and hi-c, the measurements obtained consist of pairwise interaction frequency values that are proportional to the proximity of the chromatin fragments in the nuclear space in vivo.
these data broadly define the three-dimensional conformation of chromatin.
it is important to note that these assays are not performed on a single cell, but rather a population of cells, and these data thereby represent population-average measurements of the degree of interaction between chromatin fragments that require tailored bioinformatics tools for interpretation.
in this paper, we propose a computational approach to robustly infer ensembles of chromatin conformations that are supported by a given 5c or hi-c dataset.
these three-dimensional models of chromatin conformation can be analyzed to determine robust structural properties.
recently, several approaches have been proposed to model chromatin 3d conformation from interaction frequency  data.
in previous work  <cit> , we developed a program called 5c3d that first translates if values into physical distance estimates and then uses a gradient descent approach to find the 3d conformation with the best fit to the observed data based on a simple misfit objective function.
bau et al.
<cit>  proposed 3d models of the α-globin locus based on 5c data.
they formulate an optimization problem where pairwise interactions are modeled with springs whose equilibrium length depends on the observed if values, subject to certain constraints based on the structure of the 30-nm fiber.
they then use the integrative modeling platform  to produce a set of possible conformations that satisfy the constraints while maximizing the fit to the if data.
duan et al.
<cit>  proceed similarly to obtain a model of the budding yeast chromatin conformation based on data obtained using a modification of the 4c technology coupled with high-throughput sequencing.
they first convert observed interaction frequencies to euclidean distances and then seek the chromatin conformation that minimizes the same measure of misfit as 5c3d, with the addition of a set of clash avoidance constraints, and a few biologically-motivated constraints based on prior knowledge about the yeast genome organization.
the constrained optimization problem is solved using an optimization package to produce the best fitting structure.
a very similar approach is used by tanizawa et al.
<cit>  to model the genome of fission yeast.
of all these approaches, 5c3d is the only one we are aware of that comes with stand-alone software.
although these approaches differ slightly in the manner in which if data is translated into distance constraints, the set of additional constraints included in the model, and the way the resulting system of equations is solved, they all have the merit of turning a set of noisy if measurements into a more interpretable read out.
by integrating o noisy if measurements into o predictions about the 3d location of each fragment, they also potentially produce an output that is more reliable than any of the individual if measurements it is based on.
however, these approaches suffer from two significant drawbacks.
first, the objective function  is debatable, as, among other things, it assumes that each if measurement is equally reliable.
second, the structures obtained come with no guarantee of representativity or reliable measure of uncertainty.
acknowledging this limitation, baú et al.
<cit>  proposed a heuristic approach to generate sets of candidate structures.
however, because none of these approaches are based on a probabilistic model integrating an if noise model, the set of sampled structures may not be representative of the true  set of possible structures.
even though the approach used by baú et al.
produces an ensemble of solutions, the absence of an underlying probabilistic model prevents the calculation of confidence intervals on specific structural properties  and do not identify statistically significant conformational features.
in this paper, we introduce mcmc5c, a computational probabilistic modeling approach for inferring chromatin three-dimensional structure from 5c or hi-c experiments.
our approach is based on a formal probabilistic model of interaction frequencies and their link with physical distance and uses a markov chain monte carlo sampling procedure to produce an ensemble of candidate conformations for a given 5c dataset.
unlike gradient descent approaches, mcmc5c allows  a proper sampling of the structure state space.
this set of structures can be used to obtain posterior distributions over specific structural properties, contrast structural properties of chromatin under different conditions, or determine the existence of multiple model subclasses that fit the experimental data.
markov chain monte carlo approaches have been widely applied to numerous computational and biological problems, such as the prediction of rna structure  <cit>  or protein structure  <cit> , phylogenetic inference  <cit> , and sequence alignment  <cit> .
our particular application shares some resemblance with the problem of inferring protein structure from nuclear magnetic resonance  data, which measures distances between hydrogen atoms in a molecule  <cit> .
although existing software for nmr-based protein structure prediction are not applicable to our problem because they are tightly based on specifics of nmr data and amino acid structures, mcmc approaches are commonly used to produce robust ensembles of candidate structures based on noisy distance data.
the rest of this paper is structured as follows.
after a brief introduction to the 5c and hi-c technologies, we introduce a probabilistic model of the link between 5c or hi-c data and 3d chromatin conformation.
we then describe a mcmc-based algorithm that quickly produces an ensemble of structures, and then show how key features of the chromatin structure can be robustly estimated.
our approach is used for the analysis of three 5c datasets generated for the region of human chromosome  <dig> containing the hoxa gene cluster in both undifferentiated myelomonocytes and differentiated macrophages, revealing key changes in chromatin conformation.
we also show that the mcmc5c program can be applied to hi-c data by generating a three-dimensional model of human chromosome  <dig> at a  <dig> mb resolution from previously published data  <cit> .
summary of chromosome conformation capture carbon copy  and hi-c technologies
to perform a 5c experiment, a 3c library is first generated.
3c library preparation has been described in detail elsewhere  <cit> .
briefly, 3c libraries are produced by chemically fixing cells with formaldehyde to lock protein-protein and protein-dna interactions in vivo .
a restriction enzyme is then used to digest the chromatin at specific sites across the genome.
samples are next diluted before the ligation step, such that ligation products are more likely to occur between dna molecules bound together by protein complexes.
the libraries are finally purified by proteinase k digestion and phenol-chloroform extraction.
resulting 3c libraries thus contain the entire genome's worth of unique ligation products whose relative levels are inversely correlated to the three-dimensional distance in vivo between restriction fragments in vivo.
5c quantifies 3c ligation products using a modified ligation-mediated amplification  approach, which has also been described in detail elsewhere  <cit> .
briefly, 3c ligation products are detected with specially designed 5c primers that are complementary to the region of interest and lie immediately upstream of the predicted 3c ligation junctions.
taq dna ligase is then added to specifically ligate 5c primers at the junction of 3c products.
lma reactions can be performed at high level of multiplexing such that hundreds of primers could potentially be used in a single experiment to measure thousands of predicted chromatin contacts simultaneously.
universal tail sequences, located at the end of 5c primers, are then used to amplify and fluorescently label the library of synthetic 5c ligation products in a single pcr step.
the labeled products are finally hybridized to custom microarrays for quantification.
conversion of microarray fluorescence intensities data obtained from a 5c experiment to interaction frequencies  data can be performed using the ifcalculator program as described in  <cit> .
briefly, ifcalculator starts by excluding probes with intensity signals close to background and then combines the background-subtracted intensities of the remaining probes for the same fragment pair to obtain if values and their standard deviations.
hi-c data is generated in a similar manner to 5c data and was first described in lieberman-aiden et al.
<cit> .
the technique includes additional steps of biotin fill-in and shearing before pull-down and paired-end sequencing.
hi-c can thereby be performed on a genome-wide scale and obviates the need for designing specific probes for each predicted pairwise junction.
its main drawback is the depth of sequencing required to obtain a good resolution at the if level.
although these assays are typically performed on diploid cells, the intra-chromosomal contacts found by both the 5c and hi-c technologies can be treated as occurring within one homolog, as it has been previously shown that homologous copies of each chromosome occupy distinct nuclear positioning  <cit> .
methods
in this section, we describe a probabilistic model of 5c/hi-c interaction frequency data and the link between that data and the underlying chromatin 3d conformation.
we then describe a markov chain monte carlo  approach to generate a representative sample of structures based on the experimental 5c if data.
modeling chromatin conformations and 5c/hi-c data
we model a chromosome  as a continuous piece-wise linear curve in 3d, where restriction site i is located at position s = , sy, sz).
the set of fragment end positions s = s, s,...,s, where n is the number of restriction sites considered, constitutes the conformation of the genomic region.
in order to remain as general as possible and avoid introducing biases, we place no constraint on s. however, we discuss below how various types of priors or constraints could be used.
pairs of fragments that are spatially close to each other generate large if values while pairs of fragments that are spatially far from each other generate small if values.
we assume that the theoretical interaction frequency between fragment i and j, denoted if, is inversely correlated with the distance between the two fragments in the 3d conformation: if = f ), where ds  is the euclidean distance between restriction sites i and j in s, and fis an appropriately chosen function of the form
f)∝1∕dsα,
for some value of α. the choice of the value of α is discussed in results.
our experimental data consists of a set of observed pairwise interaction frequencies if^, measured by hybridization to a microarray or by sequencing.
because of noise in the measurements, if^ may not equal if.
instead, we assume that if^ is a random variable whose distribution depends on if.
in the case of 5c data, we assume that the noise is independently and normally distributed, with a fragment pair specific standard deviation σ obtained from the data using ifcalculator, as described in  <cit> .
then,
pr=n;if,σ2),
where n  is the normal density function.
hi-c data is generated in a similar manner as 5c data, with the main difference being that ligation products are quantified by sequencing rather than hybridization.
the observed read count r for fragment pair , which is the quantity analogous to if in 5c experiments, is assumed to be dependent on the physical distance ds in the same manner as in 5c experiments.
although hi-c read counts are not accompanied by noise estimates, they can be modeled by a binomial probability distribution, as suggested by duan et al.
<cit> , with p ~ r/∑a,b r, which we approximate, for computational efficiency reasons, using a normal distribution with variance equal to the mean plus a small constant:
pr=n;r,r+κ).
the role of κ, which we set to  <dig>  is to avoid having small read counts being assigned too low a variance.
the observed data if^ defines a posterior distribution over the set of possible conformations of the chromatin: pr= pr⋅ pr∕pr.
since there are no constraints imposed on the structure space and the probability of the observed data  is constant with respect to s, we get pr=ζ⋅ pr, for some constant ζ, and thus
pr=ζ⋅∏i,j pr.
this defines the posterior probability distribution over the space of structures, conditional on the observed if data.
a gradient descent approach, similar to that presented in 5c3d by  <cit> , could be used to identify locally optimal structures.
however, there are often several different structures that fit the data almost equally well, so a probabilistic sampling approach that produces an ensemble of possible structures is advantageous.
sampling conformations from the posterior distribution
the markov chain monte carlo  algorithm is a method used to sample from a complex distribution , resulting in an ensemble of solutions x <dig>  x <dig> ..., xn  <cit> .
sampling from the posterior distribution consists of selecting an ensemble of conformations, where each conformation is selected with probability equal to its posterior probability.
this is in contrast with maximum likelihood approaches, that seek to identify the  structure s* with the highest likelihood given the observed data.
usually the structure with the highest likelihood in our ensemble is a good approximation to s*, but the ensemble allows a much deeper understanding of the structure of the solution space.
this sampling is performed using the metropolis-hastings algorithm  <cit> .
a random structure r <dig> is initially chosen to seed the process , where each point is placed randomly in a cube of side length 10⋅avg).
we then iterate the following procedure.
the current structure rt is randomly perturbed  to obtain a new structure rt′.
the posterior probability of the two structures are then compared.
if pr> pr, the perturbation is retained and we set rt+1=rt′.
otherwise, we retain rt+1=rt′ with probability pr/pr, but set rt+ <dig> = rt otherwise.
torrie and valleau  <cit>  showed that for values of t sufficiently large, pr= pr and thus that the structures sampled are representative of the true posterior distribution.
the period required for the markov process to mix, known as the burn-in period, depends on the problem size and the type of perturbation performed.
the choice of the type of random perturbation to be performed can have a major impact on the length of the burn-in period.
perturbations must allow a quick and complete exploration of the conformation space, while only modifying the current conformation in a local manner.
in addition, it is beneficial if the likelihoods of the new and old structures can be computed and compared quickly.
in the context of protein structure prediction, the most commonly used approach is to randomly modify one of the bond angles between consecutive amino acids.
although this approach is in principle applicable to our type of data, it would yield poor results, as a large number of pairwise distances would be significantly modified by any angular change.
instead, we elected to perturb structures by randomly choosing one point s along the structure and moving it by a vector v→ randomly chosen within a sphere of radius r .
clearly this type of perturbation allows the exploration of the full structure space from any starting configuration.
the likelihood of the resulting structure is then quickly obtained from that of the old by updating the terms corresponding to the pairs of points involving i.
assessing mixing
during the first iterations of the mcmc sampling process, called the burn-in phase, structures r <dig> ...,rk are highly dependent on r <dig>  the initial structure, and do not represent a proper sample in our conditional probability distribution.
it is critical to be able to determine at what point m the markov process has mixed, i.e.
for what value of m is rm essentially independent of r <dig>  after mixing, i.e.
for k ≥ m, any sample rk is representative of the target distribution.
furthermore, for δ sufficiently large, samples rk and rk + δ are independent.
several approaches exist to determine when a markov chain has mixed, and what value of δ is suitable.
the standard approach is to compare the probability distributions over the state space obtained from parallel runs started from different initial conformations, and keep sampling until the two become indistinguishable.
because our state space is continuous and high-dimensional , no structure is actually ever sampled more than once, making this approach unusable.
a literature search did not yield a ready-made solution for assessing the convergence of mcmc for structural inference, so we generalize the standard approach as follows.
we run two independent chains r and r' in parallel, from independently chosen initial conformations r <dig> and r0′.
after k iterations, we say that mixing is achieved if the samples rk={rk∕ <dig> r11k∕ <dig> ...,rk} and rk′={rk∕2′,r11k∕20′,...,rk′} cannot be distinguished from each other.
specifically, the average pairwise structural distances  among structures in rk is compared to the average pairwise distances between pairs of conformations from rk×rk′.
if the two means are within 10% of each other, we conclude that mixing is achieved and start collecting samples every δ = k/ <dig> iterations: x <dig> = rk, x <dig> = rk + δ, x <dig> = rk + 2·δ,...,xn = rk + ·δ.
this not only ensures that mixing has occurred, but also that subsequent samples, taken every δ iterations, are essentially independent.
clustering of structure ensemble
the set of structures x <dig>  x <dig> ..., xn sampled by the mcmc5c program is representative of the distribution of structures that fit the observed interaction frequency data.
in several cases, it can be useful to cluster structures from this ensemble based on their similarity, for example to identify subfamilies of structures whose properties can be assessed and contrasted.
in addition, when ensembles from parallel runs are obtained, mixing can be assessed by verifying whether structures from each run cluster together  or not.
finally, ensembles from mcmc runs executed on different datasets can reveal similarly/dissimilarity between chromatin conformations under different conditions.
we first define a measure of distance between two structures and then use hierarchical clustering   <cit>  to identify groups of similar structures.
a measure of similarity between structures that is commonly used in the area of protein and rna structure prediction is the root-mean squared deviation , which requires first aligning  the two structures being compared, and then summing the square of the distances between corresponding points along the structure  <cit> .
although applicable to our structures, we prefer a simpler approach that has the advantage of not requiring an alignment of the structures  while being more flexible in the type of geometric similarities it can capture.
we first define the n × n intra-structure distance matrix ds as the matrix of geometric euclidean distances between each pair of points i, j in structure s: the distance dist between structures s and t is then:
dist=∑i.j-dt) <dig>
note that two structures that are mirror images of each other will have distance zero.
indeed, such structures cannot be distinguished based on 5c/hi-c data.
the structures from an ensemble x <dig>  x <dig> ..., xn are clustered by first computing dist for all  <dig> ≤ i ≤ j ≤ n and then using ward hierarchical clustering  <cit> .
this clustering is used to determine the existence and number of structure subfamilies and the members of each subfamily.
visualization is accomplished with both a hierarchical tree dendrogram and a heatmap representation.
visual inspection is performed to determine the tree height cutoff and number of subfamilies and for each subfamily the member structure with the highest posterior probability is chosen as the representative structure for that cluster.
choosing the maximum likelihood structure from each cluster as representative and assigning it a weight proportional to the number of the structures in its cluster allows focusing on a small number of representative structures.
identification of reliable substructures
the ensemble of structures generated by the mcmc5c program will typically contain substructures that are highly constrained by the if^ data and are thus present in the vast majority of structures, and others that are highly variable.
knowing what aspects of the reported structure are reliable is critical to guide downstream experimental validation.
while this can sometimes be done by visual inspection of the superimposition of the structures from the sample, a more automated approach is usually desirable.
this can be achieved by identifying a subset of k fragments whose pairwise distances are best conserved across the structures in the ensemble.
to this end, we first compute the standard deviation s of the intra-structure pairwise distance for each pair of points i and j, across all samples from the ensemble.
we then identify the set of k fragments with the smallest total pairwise standard deviation using a greedy algorithm.
measuring structural properties
one of the key advantages of a sampling approach, compared to non-probabilistic or maximum likelihood approaches, is its ability to estimate the distribution of various structural properties, and thus to report both averages and confidence intervals for the selected properties.
this is particularly useful when aspects of the conformation of chromatin remain poorly determined by the data; a researcher needs to know to what extent a particular structural property of interest is observed in just a single solution  or present in all  possible structures.
to this end, mcmc5c allows the easy estimation of the distribution of various structural properties.
here, we focus on three properties of interest , that are evaluated for every position i along the region of interest .
local density at position i along the sequence is the number of dna bases located within a sphere of radius r centered at position i. the local base density can be decomposed into two terms: compaction and looping.
compaction measures the number of dna bases located within the sphere and consecutive to position i, whereas looping counts the number of bases inside the sphere but outside the portion containing i.
RESULTS
5c datasets
our modeling approaches were applied to three sets of 5c data studying the chromatin structure of the hoxa cluster .
the first pair of experiments  studies the conformation of the hoxa cluster during thp- <dig> cell differentiation from myelomonocyte to macrophage.
5c libraries were produced in both the undifferentiated myelomonocyte state and in the differentiated macrophage state ).
for the third set of experiments , 5c data was generated for the same genomic region in a mll-enl fusion cell line  that expresses a different mll-fusion protein than the thp- <dig> cell line and induces aberrant over-expression of the 5' hoxa genes  <cit> .
in both datasets, the genomic region analyzed spans  <dig> kb and contains  <dig> protein coding genes.
the region contains  <dig> restriction sites for the bglii restriction enzyme, which was used for the experiment.
each 5c library was hybridized onto a custom array with a set of probes corresponding to every potential pair of fragments .
the set of probe intensities were normalized using corresponding gene desert regions as previously described in fraser et al.
<cit>  and analyzed using the ifcalculator program  <cit>  to perform outlier detection and obtain interaction frequency and standard deviation estimates for every fragment pair considered.
although nearby sites along the sequence have elevated interaction frequencies, ifs between pairs of fragments located more than  <dig> kb are generally close to background levels, with several notable exceptions likely resulting from chromatin looping .
choice of distance-to-if transformation
although it is clear that pairwise interaction frequencies are inversely correlated with the physical distance between any pair of fragments in the chromatin conformation  <cit> , there is no consensus on how if depends on physical distance.
duan et al.
<cit>  perform distance-to-if conversions by first considering only short-range interactions  and obtaining physical distances for these pairs based on polymer models.
a given long-range if value is then mapped to the polymer-based distance that is the most likely to have resulted in that value.
the resulting conversion approximately follows d ∝ 1/if.
mateos-langerak et al.
<cit>  also suggest a relationship of the form d ∝ ifα.
bau et al.
<cit>  convert their if via a linear transformation of the if's z-score.
tanizawa et al.
<cit>  relate if to physical distance by using a loess regression on a set of physical distances measured by 3d-fish, but do not report the parameters of this regression.
the extent to which the function mapping if values to physical distance depends on the specific experimental protocol remains unclear.
in the absence of independent structural measurements for the hoxa cluster, we argue that the most accurate model is the one that is best able to predict unseen pairwise interaction frequencies.
for each of a set of possible values of α in d = c/ifα, a leave-one-out cross-validation  experiment was performed, excluding in turn the interaction frequency measurement of each pair of points, n, inferring a maximum-likelihood structure from the remaining data points, and comparing the left-out if value to the theoretical if value given the distance between fragments i and j in the obtained structure.
specifically, let s;α* be the maximum likelihood structure found by mcmc5c on a data sets consisting of the if values for all fragments pairs except , when using value α to transform physical distance to interaction frequencies.
we then define
mse=1n∑;α*−α−if) <dig>
mixing and convergence
the convergence of the mcmc sampling procedure was tested on all datasets, but for simplicity we focus on those obtained on the hb- <dig> 5c data set.
we first studied how long a burn-in phase is required before parallel runs converge to a similar conformation distribution .
figure  <dig> shows that mixing is achieved after approximately  <dig> ×  <dig> iterations, which requires less than  <dig> seconds of running time.
passed this point, structures sampled every  <dig> steps from the two parallel runs are undistinguishable from each other and sample structures from the same distribution.
<dig> structures were sampled after burn-in from each of the two runs.
the two ensembles of structures were then combined and the  <dig> structures were clustered based on their structural similarity .
we observe that structures from the two runs are interleaved in the clustering, confirming that both runs are correctly sampling from the same posterior distribution.
analysis of the two thp- <dig> 5c datasets produced similar results, and runs of a larger number of parallel mcmc chains confirm that they all sample similar structures.
additional file  <dig> compares the likelihood of the structures sampled by mcmc5c to those found by several runs of the gradient descent program 5c3d, started from different initial structures.
although both approaches succeed at identifying credible structures, we observe that the structures found by 5c3d generally have lower likelihoods than those sampled by mcmc5c - indeed, the misfit function optimized by 5c3d is not equivalent to the likelihood function, which explains the slight decrease in likelihoods observed for many 5c3d runs past a certain number of iterations.
importantly, the five 5c3d runs converge to three different solutions, hinting that this type of approach is subject to getting stuck in local optima.
accuracy of structure predictions on simulated data
having shown proper mixing of the sampling process, we then asked whether the structures produced faithfully correspond to the true structure.
in the absence of external experimental data at the appropriate resolution, we used simulated data.
starting from a known "true" structure, we generated the corresponding simulated if data , and assess our ability to recover the initial structure.
using the hb- <dig> 5c dataset, we sampled the structure with the highest posterior probability using mcmc5c.
this structure was then used as a ''gold standard'' from which simulated noisy if data was generated, based on the noise model described above.
four parallel runs of mcmc5c were then performed  on the simulated dataset and the structures with the highest posterior probability structure from each run were aligned to the original gold standard structure .
clearly, mcmc5c was able to sample structures from the posterior distribution defined by the interaction frequency data by recovering structures that closely match the gold standard from which the simulated interaction frequency dataset was generated.these results suggest that the sampling approach succeeds at finding the correct structure, at least under the assumption that the if data is generated from the pairwise distances using our model.
interestingly, the set of four maximum likelihood structures found by the four parallel mcmc5c runs actually contained topological mirror-images of otherwise nearly identical structures.
these ''enantiomer'' structures have equal probability given our model of if data and the structures were mirrored as required before the superimposition shown in figure  <dig> was performed.
clustering of conformational ensemble
upon analysis of the mixing between two parallel mcmc5c runs on the hb- <dig> 5c dataset, we observed two distinct clusters in the heatmap  that correspond to two subclasses of structures, each of which is sampled from both of the two parallel runs  and red  labels at the top of the heatmap).
the clusters obtained are robust to changes in the clustering algorithm: the cluster membership determined by the hierarchical ward clustering algorithm agrees at 85% with that obtained by the k-means algorithm, which operates in structure space rather than based on a distance matrix, suggesting that the two main clusters are indeed distinct and well separated.
we note that we do not necessarily expect these two clusters to reflect two different chromatin conformations present in the population of cells used to generate the 3c library.
instead, they represent two possible conformations for the population-wide average conformation.
the posterior probability of each class can be estimated as the fraction of the samples belonging to it.
the two largest clusters, whose structures mainly differ in the position of the loop in the region lying between the hoxa <dig> and hoxa <dig> genes, account for 42% and 58% of the structures sampled .
this finding illustrates one of the benefits of mcmc5c over 5c3d by demonstrating the ability to discover different subclasses of structures that fit the experimental data almost equally well.
analysis of hoxa conformational ensembles
while visualization is a powerful analysis approach, chromatin regions whose structure is well supported by the 5c data are better identified by our reliable subset identification algorithm, which identifies, from a given ensemble of structures, the subset of fragments whose spatial relationship varies the least within the ensemble.
the subset of fragments that are the most conserved across the ensemble of structures  are found to lie within the central core region of the structures.
these fragments are spatially close to each other and may be involved in looping contacts that are important for the maintenance of the chromatin structure and are therefore highly conserved.
these results are observed in the ensembles of structures for both of the cellular states, whereby the most conserved substructures are found to lie within the regions corresponding to the strongest contact points.
estimation of structural properties
a powerful use of mcmc5c is in the discovery of structural properties that are strongly supported by the 5c data.
this allows researchers to formulate solid hypotheses while avoiding relying on properties that may only be present in a handful of possible structures.
it is straightforward for researchers to implement new modules in mcmc5c that will evaluate the structural properties of their choice.
here, we utilize this functionality to assess and contrast the degree of looping  and base density  along the hoxa cluster, in undifferentiated and differentiated thp- <dig> cells.
the mean base density value and its standard deviation across the ensemble of structures are reported in figure  <dig>  we previously showed that expression of hox genes located at the 5' end of the hoxa cluster undergo repression upon terminal differentiation in fraser et al.
<cit> .
this region includes the hoxa <dig> and hoxa <dig> genes that have been shown to be oncogenic and are induced by the aberrant expression of the mll-af <dig> translocation protein present in the thp- <dig> cell line  <cit> .
analysis of the local base density reveals a significant increase in base density corresponding to the region of the hoxa cluster containing the genes that are repressed upon differentiation.
further analysis of the base looping measure  reveals the creation of a looping contact in this same region upon differentiation and repression of gene expression.
these observations fit with previous findings that repressed genes reside in condensed heterochromatin and suggest a model of gene repression during differentiation that involves the formation of a looping contact that serves to close the chromatin structure of the hoxa cluster to aid in repressing  of the genes located in that region, and warrants further investigation.
finally, we note that without the help of the base density confidence intervals obtained from our structure ensemble, it would have been tempting to interpret many of the apparently large differences between mean base densities as potentially biologically meaningful.
however, those differences are not statistically significant, as the corresponding confidence intervals, whose size are quite variable along the sequence, overlap in these regions.
analysis of a hi-c dataset
to demonstrate the applicability of our method to other datasets, we chose to model the long arm of human chromosome  <dig>  from hi-c data published by lieberman-aiden et al.
<cit>  at a 1mb resolution .
we generated an ensemble of  <dig> structures sampled over  <dig> ×  <dig> iterations.
figure  <dig>  shows the maximum-likelihood structure found .
lieberman-aiden et al.
<cit>  proposed the existence of two physically disjoint compartments, whereby compartment a was found to correlate with open and actively transcribed chromatin, while compartment b was found to be more densely packed and repressed.
the authors designed four 3d-fish probes  that lie consecutively along chromosome  <dig> but alternate between compartments  and showed that the non-consecutive regions of the chromosome that belong to the same compartment appear to be physically closer than those that do not  <cit> .
our results using mcmc5c weakly supports this hypothesis, with the 3d-fish probes l <dig> and l <dig> indeed being in close proximity.
importantly, we used an ensemble of  <dig> structures to estimate the distribution of predicted euclidean distances between each pair of probes and found an excellent linear correlation with the physical distances measured by lieberman-aiden et al.
<cit>  using 3d-fish .
this suggests not only that our model may be physically realistic, at least at a broad level, but also that the if-to-distance transformation used is appropriate.
implementation and running time
the mcmc5c program is implemented in java and is available at http://dostielab.biochem.mcgill.ca.
the program takes the experimental interaction frequency data  and the restriction enzyme genomic cut sites as input and produces an ensemble of structures as pdb files as output.
individual runs were performed on a  <dig>  ghz intel core  <dig> duo machine with  <dig> gb of ram, while simultaneous parallel runs were performed on a cluster comprised of  <dig> apple dual-processor  <dig> -ghz compute-node g5s .
execution time increases with the number n of fragments in the structure.
each mcmc iteration runs in time o, as only the fragment pairs involving the fragment that was moved need updating.
however execution time is mostly driven by the time to mixing, which not only depends on the size of the structure but also on how "unique" the solution is; a situation where the pool of likely structures is very small will lead to faster mixing than one where the set of possible solutions is much larger and involves many very different structures.
each of our 5c data sets consisted of  <dig> fragments, yielding between  <dig> and  <dig> interaction frequency measurements .
mixing was achieved in approximately  <dig>  ×  <dig> iterations for each data set, which took ~ <dig> seconds.
ensembles of  <dig> structures were then obtained by running the chain for approximately two hours.
for the analysis of the hi-c data from human chromosome  <dig>  which consists of  <dig> fragments and  <dig> if pairs, mixing was achieved after  <dig> ×  <dig> iterations  and  <dig> structures were obtained in approximately  <dig>  hours.
however, our attempts to use mcmc5c on the full hi-c dataset from lieberman-aiden et al.
<cit> , consisting of data from all  <dig> human chromosomes, failed to achieve mixing after  <dig> hours of execution.
CONCLUSIONS
the role of high-level chromatin conformation in regulating gene expression is now well accepted, although only a few loci have been studied in detail  <cit> .
chromosome conformation capture-based technologies  offer the ability to measure properties of the high-level chromatin organization by measuring the interaction frequency between genomic fragments.
the resolution and accuracy of these techniques is rapidly improving, and, with the use of next generation sequencing, their throughput is increasing while their cost is decreasing.
for these reasons, these technologies are increasingly popular.
whereas the technological advances allow increasingly complex assays to be performed, few computational and statistical tools exist to analyze the data resulting from such experiments, although good approaches exist to help design the experiments  <cit>  or handle and visualize their output  <cit> .
we previously developed the 5c3d program, which aims at producing the best-fitting conformation for a given dataset.
similar optimization-based approaches have also been used to model the structure of the yeast genome  <cit> , and the α-globin locus  <cit> .
however, the absence of statistical or bayesian approaches make it impossible to assess the reliability of the predicted conformation.
downstream analyses are thus limited to qualitative observations that may or may not be reliable.
in this paper, we introduce a probabilistic framework to address this problem.
by sampling from the posterior probability distribution over conformations, mcmc5c produces an ensemble of different structures that are possible given the data and can find subclasses of structures that fit the data equally well.
overlaying these conformations in a visualization tool such as pymol  <cit>  readily allows the identification of reliable and less reliable aspects of the conformation.
using ensembles allows the discovery of subclasses of structures and the estimation of structural properties, together with their distribution, which allows the user to focus on statistically sound properties or differences between datasets.
although we acknowledge that more refined probabilistic models of 5c and hi-c data will eventually be required to improve the accuracy of the structure predictions, those will be easily accommodated with mcmc5c.
none of the existing computational approaches to model 3d chromatin structures make use of advanced physical models of dna and chromatin, although the approach of duan et al.
<cit>  uses a simple polymer physics model to transform interaction frequency, while tanizawa et al.
<cit>  include simple sets of constraints derived from polymer physics.
the methodology described in this paper attempts to model chromatin without specifying any type of hard constraints on the predicted structure, although such constraints could easily be included if desired.
our probabilistic framework also allows for the easy integration of structure priors based on free energy.
although excellent models of polymers exist , it is unclear to what extent these models are informative at the scale we are considering .
a number of interesting directions should be investigated in the future.
time to mixing remains the main obstacle to running mcmc5c on very large datasets such as the whole-genome hi-c dataset of lieberman-aiden et al.
<cit> .
we are currently working on considering other types of structural perturbations for the mcmc sampling, such as modifying the torsion of a given fragment or the angle between two fragments, or a combination of several types of perturbation.
these advances should allow for more rapid sampling from the structure space, thereby aiding in the discovery of alternative conformations belonging to small subclusters of structures.
to conclude, we believe that probabilistic tools like mcmc5c are essential for the reliable analysis of data from the 3c-derived techniques such as 5c and hi-c. by integrating complex, high-dimensional and noisy datasets into an easy to interpret ensemble of three-dimensional conformations, mcmc5c allows researchers to reliably interpret the result of their assay and contrast conformations under different conditions.
uris
mcmc5c is available at http://dostielab.biochem.mcgill.ca.
detailed protocols, 3c and 5c support information  can also be found at this location.
authors' contributions
mb and mr designed the computational analysis methods that mr implemented.
jf and maf generated the 5c datasets with jd's supervision.
all authors discussed the results.
mr drafted the manuscript and all authors read, edited, and approved the final manuscript.
mr, jd, and mb wrote the manuscript.
supplementary material
additional file 1
compaction profile of the hoxa region for thp- <dig> undifferentiated and differentiated cell states.
compaction profile of the hoxa cluster for both the undifferentiated  and differentiated  thp- <dig> cell states.
the average interaction frequency value diminishes with increasing linear genomic distance between the fragment pair, but strong contacts can be seen to exist between fragments at distances over 10-kb apart.
click here for file
additional file 2
hb- <dig> likelihoods of mcmc5c and 5c3d structures.
likelihood of the structures produced by mcmc5c and by several runs of 5c3d, as a function of the number of iterations .
5c3d very quickly converges to locally optimal structures that are slightly sub-optimal, and different runs converge to different solutions.
click here for file
additional file 3
hb- <dig> structure alignment movie.
a quicktime movie of the hb- <dig> ''gold-standard'' structure aligned with the best structures from the four parallel mcmc5c runs on the simulated data.
the reference structure is annotated with the transcription start sites for the hoxa genes.
click here for file
additional file 4
hb- <dig> ensemble.
a zip file containing the ensemble of pdb structures generated by mcmc5c from the hb- <dig> 5c dataset.
click here for file
additional file 5
5c hoxa cluster undifferentiated movie.
a quicktime movie of the human hoxa cluster in the undifferentiated state as determined by mcmc5c from 5c data.
click here for file
additional file 6
5c hoxa cluster differentiated movie.
a quicktime movie of the human hoxa cluster in the differentiated state as determined by mcmc5c from 5c data.
click here for file
additional file 7
thp- <dig> undifferentiated ensemble.
a zip file containing the ensemble of pdb structures generated by mcmc5c from the thp- <dig> undifferentiated 5c dataset.
click here for file
additional file 8
thp- <dig> differentiated ensemble.
a zip file containing the ensemble of pdb structures generated by mcmc5c from the thp- <dig> differentiated 5c dataset.
click here for file
additional file 9
most reliable subset of fragments.
maximum likelihood structures found by mcmc5c from the undifferentiated and differentiated thp- <dig> datasets .
the hoxa gene transcription start sites are annotated on each of the structures.
the most reliable fragment subset of size ten for each of the structures is indicated by shaded white circles.
for both undifferentiated  and differentiated  states, the most reliable subset of fragments is concentrated at the center of the structure.
click here for file
additional file 10
base looping analysis of undifferentiated and differentiated thp- <dig> cells.
analysis of base looping comparing the undifferentiated  and differentiated  cell states.
an ensemble of one hundred structures generated by mcmc5c was used for each state.
the base looping measure was calculated with a sphere of radius one  every tenth base.
the error bars report the standard deviation.
click here for file
additional file 11
hi-c human chromosome  <dig> movie.
a quicktime movie of the hi-c human chromosome  <dig> structure as determined by mcmc5c from previously published data  <cit> .
click here for file
acknowledgements
we would like to thank jérôme waldispühl for his useful input, as well mathieu lavalée-adam and pablo cingolani for stimulating discussions and feedback.
funding: this work is funded in part by a discovery grant from the national sciences and engineering research council of canada  to mb, and grants from the canadian institutes of health research , and the canadian cancer society research institute  to jd.
mr is supported by nserc.
jf is supported by funds from the fonds de la recherche en santé du québec  and cihr.
maf is supported by a ccsri fellowship.
jd is a cihr new investigator and frsq research scholar.

 in the nucleus, genomic dna exists in the form of chromatin, which is tightly packaged and organized into higher-level structures required for proper genome function. chromatin conformation is highly dynamic and modified by several biological processes such as dna replication, repair and transcription. the three-dimensional chromatin organization itself was recently found to play an important role in transcription regulation and can be used to define chromatin signatures. for example, it was shown that elements that lie far apart in the one-dimensional genomic sequence or on different chromosomes could functionally interact through physical contacts. one such example is the 100-kb imprinted igf2/h locus on human chromosome where there exists an imprinting control region located between the igf gene and its enhancer sequence. on the maternal allele, ctcf is able to bind the unmethylated icr and subsequently forms multiple long-range looping contacts along the locus that block gene-enhancer interaction. however, the paternal icr is methylated and cannot be bound by ctcf, thus allowing the igf gene and its enhancer sequence to interact through a long-range loop, thereby regulating expression to only the paternal allele. such long-range interactions have been found throughout metazoan genomes where thus far many of them appear to correlate well with the transcriptional state of target genes. although we still do not know how many types of contacts exist or how the majority of them are regulated, it is now clear that spatial transcriptional control is an important mechanism of gene regulation. thus, mapping of physical contacts within and between chromosomes will be essential to fully understand gene regulation. several techniques are now available to examine chromatin structure at high-resolution, such as damid, and more recent approaches including chromosome conformation capture, circular chromosome conformation capture, chromosome conformation capture carbon copy, chromatin interaction analysis with paired-end tag sequencing, the technology developed by duan et al., and hi-c. these techniques combine various high-throughput approaches, such as microarrays and next-generation sequencing, and produce large datasets. in the case of 5c and hi-c, the measurements obtained consist of pairwise interaction frequency values that are proportional to the proximity of the chromatin fragments in the nuclear space in vivo. these data broadly define the three-dimensional conformation of chromatin. it is important to note that these assays are not performed on a single cell, but rather a population of cells, and these data thereby represent population-average measurements of the degree of interaction between chromatin fragments that require tailored bioinformatics tools for interpretation. in this paper, we propose a computational approach to robustly infer ensembles of chromatin conformations that are supported by a given 5c or hi-c dataset. these three-dimensional models of chromatin conformation can be analyzed to determine robust structural properties. recently, several approaches have been proposed to model chromatin 3d conformation from interaction frequency data. in previous work, we developed a program called 5c3d that first translates if values into physical distance estimates and then uses a gradient descent approach to find the 3d conformation with the best fit to the observed data based on a simple misfit objective function. bau et al. proposed 3d models of the α-globin locus based on 5c data. they formulate an optimization problem where pairwise interactions are modeled with springs whose equilibrium length depends on the observed if values, subject to certain constraints based on the structure of the 30-nm fiber. they then use the integrative modeling platform to produce a set of possible conformations that satisfy the constraints while maximizing the fit to the if data. duan et al. proceed similarly to obtain a model of the budding yeast chromatin conformation based on data obtained using a modification of the 4c technology coupled with high-throughput sequencing. they first convert observed interaction frequencies to euclidean distances and then seek the chromatin conformation that minimizes the same measure of misfit as 5c3d, with the addition of a set of clash avoidance constraints, and a few biologically-motivated constraints based on prior knowledge about the yeast genome organization. the constrained optimization problem is solved using an optimization package to produce the best fitting structure. a very similar approach is used by tanizawa et al. to model the genome of fission yeast. of all these approaches, 5c3d is the only one we are aware of that comes with stand-alone software. although these approaches differ slightly in the manner in which if data is translated into distance constraints, the set of additional constraints included in the model, and the way the resulting system of equations is solved, they all have the merit of turning a set of noisy if measurements into a more interpretable read out. by integrating o noisy if measurements into o predictions about the 3d location of each fragment, they also potentially produce an output that is more reliable than any of the individual if measurements it is based on. however, these approaches suffer from two significant drawbacks. first, the objective function is debatable, as, among other things, it assumes that each if measurement is equally reliable. second, the structures obtained come with no guarantee of representativity or reliable measure of uncertainty. acknowledging this limitation, baú et al. proposed a heuristic approach to generate sets of candidate structures. however, because none of these approaches are based on a probabilistic model integrating an if noise model, the set of sampled structures may not be representative of the true set of possible structures. even though the approach used by baú et al. produces an ensemble of solutions, the absence of an underlying probabilistic model prevents the calculation of confidence intervals on specific structural properties and do not identify statistically significant conformational features. in this paper, we introduce mcmc5c, a computational probabilistic modeling approach for inferring chromatin three-dimensional structure from 5c or hi-c experiments. our approach is based on a formal probabilistic model of interaction frequencies and their link with physical distance and uses a markov chain monte carlo sampling procedure to produce an ensemble of candidate conformations for a given 5c dataset. unlike gradient descent approaches, mcmc5c allows a proper sampling of the structure state space. this set of structures can be used to obtain posterior distributions over specific structural properties, contrast structural properties of chromatin under different conditions, or determine the existence of multiple model subclasses that fit the experimental data. markov chain monte carlo approaches have been widely applied to numerous computational and biological problems, such as the prediction of rna structure or protein structure, phylogenetic inference, and sequence alignment. our particular application shares some resemblance with the problem of inferring protein structure from nuclear magnetic resonance data, which measures distances between hydrogen atoms in a molecule. although existing software for nmr-based protein structure prediction are not applicable to our problem because they are tightly based on specifics of nmr data and amino acid structures, mcmc approaches are commonly used to produce robust ensembles of candidate structures based on noisy distance data. the rest of this paper is structured as follows. after a brief introduction to the 5c and hi-c technologies, we introduce a probabilistic model of the link between 5c or hi-c data and 3d chromatin conformation. we then describe a mcmc-based algorithm that quickly produces an ensemble of structures, and then show how key features of the chromatin structure can be robustly estimated. our approach is used for the analysis of three 5c datasets generated for the region of human chromosome containing the hoxa gene cluster in both undifferentiated myelomonocytes and differentiated macrophages, revealing key changes in chromatin conformation. we also show that the mcmc5c program can be applied to hi-c data by generating a three-dimensional model of human chromosome at a mb resolution from previously published data. summary of chromosome conformation capture carbon copy and hi-c technologies to perform a 5c experiment, a 3c library is first generated. 3c library preparation has been described in detail elsewhere. briefly, 3c libraries are produced by chemically fixing cells with formaldehyde to lock protein-protein and protein-dna interactions in vivo. a restriction enzyme is then used to digest the chromatin at specific sites across the genome. samples are next diluted before the ligation step, such that ligation products are more likely to occur between dna molecules bound together by protein complexes. the libraries are finally purified by proteinase k digestion and phenol-chloroform extraction. resulting 3c libraries thus contain the entire genome's worth of unique ligation products whose relative levels are inversely correlated to the three-dimensional distance in vivo between restriction fragments in vivo. 5c quantifies 3c ligation products using a modified ligation-mediated amplification approach, which has also been described in detail elsewhere. briefly, 3c ligation products are detected with specially designed 5c primers that are complementary to the region of interest and lie immediately upstream of the predicted 3c ligation junctions. taq dna ligase is then added to specifically ligate 5c primers at the junction of 3c products. lma reactions can be performed at high level of multiplexing such that hundreds of primers could potentially be used in a single experiment to measure thousands of predicted chromatin contacts simultaneously. universal tail sequences, located at the end of 5c primers, are then used to amplify and fluorescently label the library of synthetic 5c ligation products in a single pcr step. the labeled products are finally hybridized to custom microarrays for quantification. conversion of microarray fluorescence intensities data obtained from a 5c experiment to interaction frequencies data can be performed using the ifcalculator program as described in. briefly, ifcalculator starts by excluding probes with intensity signals close to background and then combines the background-subtracted intensities of the remaining probes for the same fragment pair to obtain if values and their standard deviations. hi-c data is generated in a similar manner to 5c data and was first described in lieberman-aiden et al.. the technique includes additional steps of biotin fill-in and shearing before pull-down and paired-end sequencing. hi-c can thereby be performed on a genome-wide scale and obviates the need for designing specific probes for each predicted pairwise junction. its main drawback is the depth of sequencing required to obtain a good resolution at the if level. although these assays are typically performed on diploid cells, the intra-chromosomal contacts found by both the 5c and hi-c technologies can be treated as occurring within one homolog, as it has been previously shown that homologous copies of each chromosome occupy distinct nuclear positioning. methods in this section, we describe a probabilistic model of 5c/hi-c interaction frequency data and the link between that data and the underlying chromatin 3d conformation. we then describe a markov chain monte carlo approach to generate a representative sample of structures based on the experimental 5c if data. modeling chromatin conformations and 5c/hi-c data we model a chromosome as a continuous piece-wise linear curve in 3d, where restriction site i is located at position s =, sy, sz). the set of fragment end positions s = s, s,...,s, where n is the number of restriction sites considered, constitutes the conformation of the genomic region. in order to remain as general as possible and avoid introducing biases, we place no constraint on s. however, we discuss below how various types of priors or constraints could be used. pairs of fragments that are spatially close to each other generate large if values while pairs of fragments that are spatially far from each other generate small if values. we assume that the theoretical interaction frequency between fragment i and j, denoted if, is inversely correlated with the distance between the two fragments in the 3d conformation: if = f ), where ds is the euclidean distance between restriction sites i and j in s, and fis an appropriately chosen function of the form f)∝1∕dsα, for some value of α. the choice of the value of α is discussed in results. our experimental data consists of a set of observed pairwise interaction frequencies if^, measured by hybridization to a microarray or by sequencing. because of noise in the measurements, if^ may not equal if. instead, we assume that if^ is a random variable whose distribution depends on if. in the case of 5c data, we assume that the noise is independently and normally distributed, with a fragment pair specific standard deviation σ obtained from the data using ifcalculator, as described in. then, pr=n;if,σ2), where n is the normal density function. hi-c data is generated in a similar manner as 5c data, with the main difference being that ligation products are quantified by sequencing rather than hybridization. the observed read count r for fragment pair, which is the quantity analogous to if in 5c experiments, is assumed to be dependent on the physical distance ds in the same manner as in 5c experiments. although hi-c read counts are not accompanied by noise estimates, they can be modeled by a binomial probability distribution, as suggested by duan et al., with p ~ r/∑a,b r, which we approximate, for computational efficiency reasons, using a normal distribution with variance equal to the mean plus a small constant: pr=n;r,r+κ). the role of κ, which we set to is to avoid having small read counts being assigned too low a variance. the observed data if^ defines a posterior distribution over the set of possible conformations of the chromatin: pr= pr⋅ pr∕pr. since there are no constraints imposed on the structure space and the probability of the observed data is constant with respect to s, we get pr=ζ⋅ pr, for some constant ζ, and thus pr=ζ⋅∏i,j pr. this defines the posterior probability distribution over the space of structures, conditional on the observed if data. a gradient descent approach, similar to that presented in 5c3d by, could be used to identify locally optimal structures. however, there are often several different structures that fit the data almost equally well, so a probabilistic sampling approach that produces an ensemble of possible structures is advantageous. sampling conformations from the posterior distribution the markov chain monte carlo algorithm is a method used to sample from a complex distribution, resulting in an ensemble of solutions x x..., xn. sampling from the posterior distribution consists of selecting an ensemble of conformations, where each conformation is selected with probability equal to its posterior probability. this is in contrast with maximum likelihood approaches, that seek to identify the structure s* with the highest likelihood given the observed data. usually the structure with the highest likelihood in our ensemble is a good approximation to s*, but the ensemble allows a much deeper understanding of the structure of the solution space. this sampling is performed using the metropolis-hastings algorithm. a random structure r is initially chosen to seed the process, where each point is placed randomly in a cube of side length 10⋅avg). we then iterate the following procedure. the current structure rt is randomly perturbed to obtain a new structure rt′. the posterior probability of the two structures are then compared. if pr> pr, the perturbation is retained and we set rt+1=rt′. otherwise, we retain rt+1=rt′ with probability pr/pr, but set rt+ = rt otherwise. torrie and valleau showed that for values of t sufficiently large, pr= pr and thus that the structures sampled are representative of the true posterior distribution. the period required for the markov process to mix, known as the burn-in period, depends on the problem size and the type of perturbation performed. the choice of the type of random perturbation to be performed can have a major impact on the length of the burn-in period. perturbations must allow a quick and complete exploration of the conformation space, while only modifying the current conformation in a local manner. in addition, it is beneficial if the likelihoods of the new and old structures can be computed and compared quickly. in the context of protein structure prediction, the most commonly used approach is to randomly modify one of the bond angles between consecutive amino acids. although this approach is in principle applicable to our type of data, it would yield poor results, as a large number of pairwise distances would be significantly modified by any angular change. instead, we elected to perturb structures by randomly choosing one point s along the structure and moving it by a vector v→ randomly chosen within a sphere of radius r. clearly this type of perturbation allows the exploration of the full structure space from any starting configuration. the likelihood of the resulting structure is then quickly obtained from that of the old by updating the terms corresponding to the pairs of points involving i. assessing mixing during the first iterations of the mcmc sampling process, called the burn-in phase, structures r...,rk are highly dependent on r the initial structure, and do not represent a proper sample in our conditional probability distribution. it is critical to be able to determine at what point m the markov process has mixed, i.e. for what value of m is rm essentially independent of r after mixing, i.e. for k ≥ m, any sample rk is representative of the target distribution. furthermore, for δ sufficiently large, samples rk and rk + δ are independent. several approaches exist to determine when a markov chain has mixed, and what value of δ is suitable. the standard approach is to compare the probability distributions over the state space obtained from parallel runs started from different initial conformations, and keep sampling until the two become indistinguishable. because our state space is continuous and high-dimensional, no structure is actually ever sampled more than once, making this approach unusable. a literature search did not yield a ready-made solution for assessing the convergence of mcmc for structural inference, so we generalize the standard approach as follows. we run two independent chains r and r' in parallel, from independently chosen initial conformations r and r0′. after k iterations, we say that mixing is achieved if the samples rk={rk∕ r11k∕...,rk} and rk′={rk∕2′,r11k∕20′,...,rk′} cannot be distinguished from each other. specifically, the average pairwise structural distances among structures in rk is compared to the average pairwise distances between pairs of conformations from rk×rk′. if the two means are within 10% of each other, we conclude that mixing is achieved and start collecting samples every δ = k/ iterations: x = rk, x = rk + δ, x = rk + 2·δ,...,xn = rk + ·δ. this not only ensures that mixing has occurred, but also that subsequent samples, taken every δ iterations, are essentially independent. clustering of structure ensemble the set of structures x x..., xn sampled by the mcmc5c program is representative of the distribution of structures that fit the observed interaction frequency data. in several cases, it can be useful to cluster structures from this ensemble based on their similarity, for example to identify subfamilies of structures whose properties can be assessed and contrasted. in addition, when ensembles from parallel runs are obtained, mixing can be assessed by verifying whether structures from each run cluster together or not. finally, ensembles from mcmc runs executed on different datasets can reveal similarly/dissimilarity between chromatin conformations under different conditions. we first define a measure of distance between two structures and then use hierarchical clustering to identify groups of similar structures. a measure of similarity between structures that is commonly used in the area of protein and rna structure prediction is the root-mean squared deviation, which requires first aligning the two structures being compared, and then summing the square of the distances between corresponding points along the structure. although applicable to our structures, we prefer a simpler approach that has the advantage of not requiring an alignment of the structures while being more flexible in the type of geometric similarities it can capture. we first define the n × n intra-structure distance matrix ds as the matrix of geometric euclidean distances between each pair of points i, j in structure s: the distance dist between structures s and t is then: dist=∑i.j-dt) note that two structures that are mirror images of each other will have distance zero. indeed, such structures cannot be distinguished based on 5c/hi-c data. the structures from an ensemble x x..., xn are clustered by first computing dist for all ≤ i ≤ j ≤ n and then using ward hierarchical clustering. this clustering is used to determine the existence and number of structure subfamilies and the members of each subfamily. visualization is accomplished with both a hierarchical tree dendrogram and a heatmap representation. visual inspection is performed to determine the tree height cutoff and number of subfamilies and for each subfamily the member structure with the highest posterior probability is chosen as the representative structure for that cluster. choosing the maximum likelihood structure from each cluster as representative and assigning it a weight proportional to the number of the structures in its cluster allows focusing on a small number of representative structures. identification of reliable substructures the ensemble of structures generated by the mcmc5c program will typically contain substructures that are highly constrained by the if^ data and are thus present in the vast majority of structures, and others that are highly variable. knowing what aspects of the reported structure are reliable is critical to guide downstream experimental validation. while this can sometimes be done by visual inspection of the superimposition of the structures from the sample, a more automated approach is usually desirable. this can be achieved by identifying a subset of k fragments whose pairwise distances are best conserved across the structures in the ensemble. to this end, we first compute the standard deviation s of the intra-structure pairwise distance for each pair of points i and j, across all samples from the ensemble. we then identify the set of k fragments with the smallest total pairwise standard deviation using a greedy algorithm. measuring structural properties one of the key advantages of a sampling approach, compared to non-probabilistic or maximum likelihood approaches, is its ability to estimate the distribution of various structural properties, and thus to report both averages and confidence intervals for the selected properties. this is particularly useful when aspects of the conformation of chromatin remain poorly determined by the data; a researcher needs to know to what extent a particular structural property of interest is observed in just a single solution or present in all possible structures. to this end, mcmc5c allows the easy estimation of the distribution of various structural properties. here, we focus on three properties of interest, that are evaluated for every position i along the region of interest. local density at position i along the sequence is the number of dna bases located within a sphere of radius r centered at position i. the local base density can be decomposed into two terms: compaction and looping. compaction measures the number of dna bases located within the sphere and consecutive to position i, whereas looping counts the number of bases inside the sphere but outside the portion containing i.  5c datasets our modeling approaches were applied to three sets of 5c data studying the chromatin structure of the hoxa cluster. the first pair of experiments studies the conformation of the hoxa cluster during thp- cell differentiation from myelomonocyte to macrophage. 5c libraries were produced in both the undifferentiated myelomonocyte state and in the differentiated macrophage state ). for the third set of experiments, 5c data was generated for the same genomic region in a mll-enl fusion cell line that expresses a different mll-fusion protein than the thp- cell line and induces aberrant over-expression of the 5' hoxa genes. in both datasets, the genomic region analyzed spans kb and contains protein coding genes. the region contains restriction sites for the bglii restriction enzyme, which was used for the experiment. each 5c library was hybridized onto a custom array with a set of probes corresponding to every potential pair of fragments. the set of probe intensities were normalized using corresponding gene desert regions as previously described in fraser et al. and analyzed using the ifcalculator program to perform outlier detection and obtain interaction frequency and standard deviation estimates for every fragment pair considered. although nearby sites along the sequence have elevated interaction frequencies, ifs between pairs of fragments located more than kb are generally close to background levels, with several notable exceptions likely resulting from chromatin looping. choice of distance-to-if transformation although it is clear that pairwise interaction frequencies are inversely correlated with the physical distance between any pair of fragments in the chromatin conformation, there is no consensus on how if depends on physical distance. duan et al. perform distance-to-if conversions by first considering only short-range interactions and obtaining physical distances for these pairs based on polymer models. a given long-range if value is then mapped to the polymer-based distance that is the most likely to have resulted in that value. the resulting conversion approximately follows d ∝ 1/if. mateos-langerak et al. also suggest a relationship of the form d ∝ ifα. bau et al. convert their if via a linear transformation of the if's z-score. tanizawa et al. relate if to physical distance by using a loess regression on a set of physical distances measured by 3d-fish, but do not report the parameters of this regression. the extent to which the function mapping if values to physical distance depends on the specific experimental protocol remains unclear. in the absence of independent structural measurements for the hoxa cluster, we argue that the most accurate model is the one that is best able to predict unseen pairwise interaction frequencies. for each of a set of possible values of α in d = c/ifα, a leave-one-out cross-validation experiment was performed, excluding in turn the interaction frequency measurement of each pair of points, n, inferring a maximum-likelihood structure from the remaining data points, and comparing the left-out if value to the theoretical if value given the distance between fragments i and j in the obtained structure. specifically, let s;α* be the maximum likelihood structure found by mcmc5c on a data sets consisting of the if values for all fragments pairs except, when using value α to transform physical distance to interaction frequencies. we then define mse=1n∑;α*−α−if) mixing and convergence the convergence of the mcmc sampling procedure was tested on all datasets, but for simplicity we focus on those obtained on the hb- 5c data set. we first studied how long a burn-in phase is required before parallel runs converge to a similar conformation distribution. figure shows that mixing is achieved after approximately × iterations, which requires less than seconds of running time. passed this point, structures sampled every steps from the two parallel runs are undistinguishable from each other and sample structures from the same distribution. structures were sampled after burn-in from each of the two runs. the two ensembles of structures were then combined and the structures were clustered based on their structural similarity. we observe that structures from the two runs are interleaved in the clustering, confirming that both runs are correctly sampling from the same posterior distribution. analysis of the two thp- 5c datasets produced similar results, and runs of a larger number of parallel mcmc chains confirm that they all sample similar structures. additional file compares the likelihood of the structures sampled by mcmc5c to those found by several runs of the gradient descent program 5c3d, started from different initial structures. although both approaches succeed at identifying credible structures, we observe that the structures found by 5c3d generally have lower likelihoods than those sampled by mcmc5c - indeed, the misfit function optimized by 5c3d is not equivalent to the likelihood function, which explains the slight decrease in likelihoods observed for many 5c3d runs past a certain number of iterations. importantly, the five 5c3d runs converge to three different solutions, hinting that this type of approach is subject to getting stuck in local optima. accuracy of structure predictions on simulated data having shown proper mixing of the sampling process, we then asked whether the structures produced faithfully correspond to the true structure. in the absence of external experimental data at the appropriate resolution, we used simulated data. starting from a known "true" structure, we generated the corresponding simulated if data, and assess our ability to recover the initial structure. using the hb- 5c dataset, we sampled the structure with the highest posterior probability using mcmc5c. this structure was then used as a''gold standard'' from which simulated noisy if data was generated, based on the noise model described above. four parallel runs of mcmc5c were then performed on the simulated dataset and the structures with the highest posterior probability structure from each run were aligned to the original gold standard structure. clearly, mcmc5c was able to sample structures from the posterior distribution defined by the interaction frequency data by recovering structures that closely match the gold standard from which the simulated interaction frequency dataset was generated.these results suggest that the sampling approach succeeds at finding the correct structure, at least under the assumption that the if data is generated from the pairwise distances using our model. interestingly, the set of four maximum likelihood structures found by the four parallel mcmc5c runs actually contained topological mirror-images of otherwise nearly identical structures. these''enantiomer'' structures have equal probability given our model of if data and the structures were mirrored as required before the superimposition shown in figure was performed. clustering of conformational ensemble upon analysis of the mixing between two parallel mcmc5c runs on the hb- 5c dataset, we observed two distinct clusters in the heatmap that correspond to two subclasses of structures, each of which is sampled from both of the two parallel runs and red labels at the top of the heatmap). the clusters obtained are robust to changes in the clustering algorithm: the cluster membership determined by the hierarchical ward clustering algorithm agrees at 85% with that obtained by the k-means algorithm, which operates in structure space rather than based on a distance matrix, suggesting that the two main clusters are indeed distinct and well separated. we note that we do not necessarily expect these two clusters to reflect two different chromatin conformations present in the population of cells used to generate the 3c library. instead, they represent two possible conformations for the population-wide average conformation. the posterior probability of each class can be estimated as the fraction of the samples belonging to it. the two largest clusters, whose structures mainly differ in the position of the loop in the region lying between the hoxa and hoxa genes, account for 42% and 58% of the structures sampled. this finding illustrates one of the benefits of mcmc5c over 5c3d by demonstrating the ability to discover different subclasses of structures that fit the experimental data almost equally well. analysis of hoxa conformational ensembles while visualization is a powerful analysis approach, chromatin regions whose structure is well supported by the 5c data are better identified by our reliable subset identification algorithm, which identifies, from a given ensemble of structures, the subset of fragments whose spatial relationship varies the least within the ensemble. the subset of fragments that are the most conserved across the ensemble of structures are found to lie within the central core region of the structures. these fragments are spatially close to each other and may be involved in looping contacts that are important for the maintenance of the chromatin structure and are therefore highly conserved. these results are observed in the ensembles of structures for both of the cellular states, whereby the most conserved substructures are found to lie within the regions corresponding to the strongest contact points. estimation of structural properties a powerful use of mcmc5c is in the discovery of structural properties that are strongly supported by the 5c data. this allows researchers to formulate solid hypotheses while avoiding relying on properties that may only be present in a handful of possible structures. it is straightforward for researchers to implement new modules in mcmc5c that will evaluate the structural properties of their choice. here, we utilize this functionality to assess and contrast the degree of looping and base density along the hoxa cluster, in undifferentiated and differentiated thp- cells. the mean base density value and its standard deviation across the ensemble of structures are reported in figure we previously showed that expression of hox genes located at the 5' end of the hoxa cluster undergo repression upon terminal differentiation in fraser et al.. this region includes the hoxa and hoxa genes that have been shown to be oncogenic and are induced by the aberrant expression of the mll-af translocation protein present in the thp- cell line. analysis of the local base density reveals a significant increase in base density corresponding to the region of the hoxa cluster containing the genes that are repressed upon differentiation. further analysis of the base looping measure reveals the creation of a looping contact in this same region upon differentiation and repression of gene expression. these observations fit with previous findings that repressed genes reside in condensed heterochromatin and suggest a model of gene repression during differentiation that involves the formation of a looping contact that serves to close the chromatin structure of the hoxa cluster to aid in repressing of the genes located in that region, and warrants further investigation. finally, we note that without the help of the base density confidence intervals obtained from our structure ensemble, it would have been tempting to interpret many of the apparently large differences between mean base densities as potentially biologically meaningful. however, those differences are not statistically significant, as the corresponding confidence intervals, whose size are quite variable along the sequence, overlap in these regions. analysis of a hi-c dataset to demonstrate the applicability of our method to other datasets, we chose to model the long arm of human chromosome from hi-c data published by lieberman-aiden et al. at a 1mb resolution. we generated an ensemble of structures sampled over × iterations. figure shows the maximum-likelihood structure found. lieberman-aiden et al. proposed the existence of two physically disjoint compartments, whereby compartment a was found to correlate with open and actively transcribed chromatin, while compartment b was found to be more densely packed and repressed. the authors designed four 3d-fish probes that lie consecutively along chromosome but alternate between compartments and showed that the non-consecutive regions of the chromosome that belong to the same compartment appear to be physically closer than those that do not. our results using mcmc5c weakly supports this hypothesis, with the 3d-fish probes l and l indeed being in close proximity. importantly, we used an ensemble of structures to estimate the distribution of predicted euclidean distances between each pair of probes and found an excellent linear correlation with the physical distances measured by lieberman-aiden et al. using 3d-fish. this suggests not only that our model may be physically realistic, at least at a broad level, but also that the if-to-distance transformation used is appropriate. implementation and running time the mcmc5c program is implemented in java and is available at http://dostielab.biochem.mcgill.ca. the program takes the experimental interaction frequency data and the restriction enzyme genomic cut sites as input and produces an ensemble of structures as pdb files as output. individual runs were performed on a ghz intel core duo machine with gb of ram, while simultaneous parallel runs were performed on a cluster comprised of apple dual-processor -ghz compute-node g5s. execution time increases with the number n of fragments in the structure. each mcmc iteration runs in time o, as only the fragment pairs involving the fragment that was moved need updating. however execution time is mostly driven by the time to mixing, which not only depends on the size of the structure but also on how "unique" the solution is; a situation where the pool of likely structures is very small will lead to faster mixing than one where the set of possible solutions is much larger and involves many very different structures. each of our 5c data sets consisted of fragments, yielding between and interaction frequency measurements. mixing was achieved in approximately × iterations for each data set, which took ~ seconds. ensembles of structures were then obtained by running the chain for approximately two hours. for the analysis of the hi-c data from human chromosome which consists of fragments and if pairs, mixing was achieved after × iterations and structures were obtained in approximately hours. however, our attempts to use mcmc5c on the full hi-c dataset from lieberman-aiden et al., consisting of data from all human chromosomes, failed to achieve mixing after hours of execution.  the role of high-level chromatin conformation in regulating gene expression is now well accepted, although only a few loci have been studied in detail. chromosome conformation capture-based technologies offer the ability to measure properties of the high-level chromatin organization by measuring the interaction frequency between genomic fragments. the resolution and accuracy of these techniques is rapidly improving, and, with the use of next generation sequencing, their throughput is increasing while their cost is decreasing. for these reasons, these technologies are increasingly popular. whereas the technological advances allow increasingly complex assays to be performed, few computational and statistical tools exist to analyze the data resulting from such experiments, although good approaches exist to help design the experiments or handle and visualize their output. we previously developed the 5c3d program, which aims at producing the best-fitting conformation for a given dataset. similar optimization-based approaches have also been used to model the structure of the yeast genome, and the α-globin locus. however, the absence of statistical or bayesian approaches make it impossible to assess the reliability of the predicted conformation. downstream analyses are thus limited to qualitative observations that may or may not be reliable. in this paper, we introduce a probabilistic framework to address this problem. by sampling from the posterior probability distribution over conformations, mcmc5c produces an ensemble of different structures that are possible given the data and can find subclasses of structures that fit the data equally well. overlaying these conformations in a visualization tool such as pymol readily allows the identification of reliable and less reliable aspects of the conformation. using ensembles allows the discovery of subclasses of structures and the estimation of structural properties, together with their distribution, which allows the user to focus on statistically sound properties or differences between datasets. although we acknowledge that more refined probabilistic models of 5c and hi-c data will eventually be required to improve the accuracy of the structure predictions, those will be easily accommodated with mcmc5c. none of the existing computational approaches to model 3d chromatin structures make use of advanced physical models of dna and chromatin, although the approach of duan et al. uses a simple polymer physics model to transform interaction frequency, while tanizawa et al. include simple sets of constraints derived from polymer physics. the methodology described in this paper attempts to model chromatin without specifying any type of hard constraints on the predicted structure, although such constraints could easily be included if desired. our probabilistic framework also allows for the easy integration of structure priors based on free energy. although excellent models of polymers exist, it is unclear to what extent these models are informative at the scale we are considering. a number of interesting directions should be investigated in the future. time to mixing remains the main obstacle to running mcmc5c on very large datasets such as the whole-genome hi-c dataset of lieberman-aiden et al.. we are currently working on considering other types of structural perturbations for the mcmc sampling, such as modifying the torsion of a given fragment or the angle between two fragments, or a combination of several types of perturbation. these advances should allow for more rapid sampling from the structure space, thereby aiding in the discovery of alternative conformations belonging to small subclusters of structures. to conclude, we believe that probabilistic tools like mcmc5c are essential for the reliable analysis of data from the 3c-derived techniques such as 5c and hi-c. by integrating complex, high-dimensional and noisy datasets into an easy to interpret ensemble of three-dimensional conformations, mcmc5c allows researchers to reliably interpret the result of their assay and contrast conformations under different conditions. uris mcmc5c is available at http://dostielab.biochem.mcgill.ca. detailed protocols, 3c and 5c support information can also be found at this location. authors' contributions mb and mr designed the computational analysis methods that mr implemented. jf and maf generated the 5c datasets with jd's supervision. all authors discussed the results. mr drafted the manuscript and all authors read, edited, and approved the final manuscript. mr, jd, and mb wrote the manuscript. supplementary material additional file 1 compaction profile of the hoxa region for thp- undifferentiated and differentiated cell states. compaction profile of the hoxa cluster for both the undifferentiated and differentiated thp- cell states. the average interaction frequency value diminishes with increasing linear genomic distance between the fragment pair, but strong contacts can be seen to exist between fragments at distances over 10-kb apart. click here for file additional file 2 hb- likelihoods of mcmc5c and 5c3d structures. likelihood of the structures produced by mcmc5c and by several runs of 5c3d, as a function of the number of iterations. 5c3d very quickly converges to locally optimal structures that are slightly sub-optimal, and different runs converge to different solutions. click here for file additional file 3 hb- structure alignment movie. a quicktime movie of the hb-''gold-standard'' structure aligned with the best structures from the four parallel mcmc5c runs on the simulated data. the reference structure is annotated with the transcription start sites for the hoxa genes. click here for file additional file 4 hb- ensemble. a zip file containing the ensemble of pdb structures generated by mcmc5c from the hb- 5c dataset. click here for file additional file 5 5c hoxa cluster undifferentiated movie. a quicktime movie of the human hoxa cluster in the undifferentiated state as determined by mcmc5c from 5c data. click here for file additional file 6 5c hoxa cluster differentiated movie. a quicktime movie of the human hoxa cluster in the differentiated state as determined by mcmc5c from 5c data. click here for file additional file 7 thp- undifferentiated ensemble. a zip file containing the ensemble of pdb structures generated by mcmc5c from the thp- undifferentiated 5c dataset. click here for file additional file 8 thp- differentiated ensemble. a zip file containing the ensemble of pdb structures generated by mcmc5c from the thp- differentiated 5c dataset. click here for file additional file 9 most reliable subset of fragments. maximum likelihood structures found by mcmc5c from the undifferentiated and differentiated thp- datasets. the hoxa gene transcription start sites are annotated on each of the structures. the most reliable fragment subset of size ten for each of the structures is indicated by shaded white circles. for both undifferentiated and differentiated states, the most reliable subset of fragments is concentrated at the center of the structure. click here for file additional file 10 base looping analysis of undifferentiated and differentiated thp- cells. analysis of base looping comparing the undifferentiated and differentiated cell states. an ensemble of one hundred structures generated by mcmc5c was used for each state. the base looping measure was calculated with a sphere of radius one every tenth base. the error bars report the standard deviation. click here for file additional file 11 hi-c human chromosome movie. a quicktime movie of the hi-c human chromosome structure as determined by mcmc5c from previously published data. click here for file acknowledgements we would like to thank jérôme waldispühl for his useful input, as well mathieu lavalée-adam and pablo cingolani for stimulating discussions and feedback. funding: this work is funded in part by a discovery grant from the national sciences and engineering research council of canada to mb, and grants from the canadian institutes of health research, and the canadian cancer society research institute to jd. mr is supported by nserc. jf is supported by funds from the fonds de la recherche en santé du québec and cihr. maf is supported by a ccsri fellowship. jd is a cihr new investigator and frsq research scholar.
long-range interactions between regulatory dna elements such as enhancers, insulators and promoters play an important role in regulating transcription. we formulate a probabilistic model linking 5c/hi-c data to physical distances and describe a markov chain monte carlo approach called mcmc5c to generate a representative sample from the posterior distribution over structures from if data. chromosome conformation capture carbon copy and its variant hi-c are techniques used to measure the interaction frequency between specific regions of the genome. as chromatin contacts have been found throughout the human genome and in different cell types, spatial transcriptional control is now viewed as a general mechanism of gene expression regulation. we applied these methods to a biological model of human myelomonocyte cellular differentiation and identified distinct chromatin conformation signatures corresponding to each of the cellular states. we believe that tools like mcmc5c are essential for the reliable analysis of data from the 3c-derived techniques such as 5c and hi-c. by integrating complex, high-dimensional and noisy datasets into an easy to interpret ensemble of three-dimensional conformations, mcmc5c allows researchers to reliably interpret the result of their assay and contrast conformations under different conditions. we also demonstrate the ability of our method to run on hi-c data and produce a model of human chromosome at 1mb resolution that is consistent with previously observed structural properties as measured by 3d-fish. structures produced from parallel mcmc runs on the same dataset demonstrate that our mcmc method mixes quickly and is able to sample from the posterior distribution of structures and find subclasses of structures. structural properties were defined and their distribution measured across the ensembles of structures generated.
 long-range interactions between regulatory dna elements such as enhancers, insulators and promoters play an important role in regulating transcription. as chromatin contacts have been found throughout the human genome and in different cell types, spatial transcriptional control is now viewed as a general mechanism of gene expression regulation. chromosome conformation capture carbon copy and its variant hi-c are techniques used to measure the interaction frequency between specific regions of the genome. our goal is to use the if data generated by these experiments to computationally model and analyze three-dimensional chromatin organization.  we formulate a probabilistic model linking 5c/hi-c data to physical distances and describe a markov chain monte carlo approach called mcmc5c to generate a representative sample from the posterior distribution over structures from if data. structures produced from parallel mcmc runs on the same dataset demonstrate that our mcmc method mixes quickly and is able to sample from the posterior distribution of structures and find subclasses of structures. structural properties were defined and their distribution measured across the ensembles of structures generated. we applied these methods to a biological model of human myelomonocyte cellular differentiation and identified distinct chromatin conformation signatures corresponding to each of the cellular states. we also demonstrate the ability of our method to run on hi-c data and produce a model of human chromosome at 1mb resolution that is consistent with previously observed structural properties as measured by 3d-fish.  we believe that tools like mcmc5c are essential for the reliable analysis of data from the 3c-derived techniques such as 5c and hi-c. by integrating complex, high-dimensional and noisy datasets into an easy to interpret ensemble of three-dimensional conformations, mcmc5c allows researchers to reliably interpret the result of their assay and contrast conformations under different conditions. availability http://dostielab.biochem.mcgill.ca 