Reconstructing high-resolution chromosome three-dimensional structures by Hi-C complex networks

BackgroundHi-C data have been widely used to reconstruct chromosomal three-dimensional (3D) structures. One of the key limitations of Hi-C is the unclear relationship between spatial distance and the number of Hi-C contacts. Many methods used a fixed parameter when converting the number of Hi-C contacts to wish distances. However, a single parameter cannot properly explain the relationship between wish distances and genomic distances or the  locations of topologically associating domains (TADs).ResultsWe have addressed one of the key issues of using Hi-C data, that is, the unclear relationship between spatial distances and the number of Hi-C contacts, which is crucial to understand significant biological functions, such as the enhancer-promoter interactions. Specifically, we developed a new method to infer this converting parameter and pairwise Euclidean distances based on the topology of the Hi-C complex network (HiCNet). The inferred distances were modeled by clustering coefficient and multiple other types of constraints. We found that our inferred distances between bead-pairs within the same TAD were apparently smaller than those distances between bead-pairs from different TADs. Our inferred distances had a higher correlation with fluorescence in situ hybridization (FISH) data, fitted the localization patterns of Xist transcripts on DNA, and better matched 156 pairs of protein-enabled long-range chromatin interactions detected by ChIA-PET. Using the inferred distances and another round of optimization, we further reconstructed 40 kb high-resolution 3D chromosomal structures of mouse male ES cells. The high-resolution structures successfully illustrate TADs and DNA loops (peaks in Hi-C contact heatmaps) that usually indicate enhancer-promoter interactions.ConclusionsWe developed a novel method to infer the wish distances between DNA bead-pairs from Hi-C contacts. High-resolution 3D structures of chromosomes were built based on the newly-inferred wish distances. This whole process has been implemented as a tool named HiCNet, which is publicly available at http://dna.cs.miami.edu/HiCNet/.

Related papers:

title: Capturing Chromosome Conformation
abstract: We describe an approach to detect the frequency of interaction between any two genomic loci. Generation of a matrix of interaction frequencies between sites on the same or different chromosomes reveals their relative spatial disposition and provides information about the physical properties of the chromatin fiber. This methodology can be applied to the spatial organization of entire genomes in organisms from bacteria to human. Using the yeast Saccharomyces cerevisiae, we could confirm known qualitative features of chromosome organization within the nucleus and dynamic changes in that organization during meiosis. We also analyzed yeast chromosome III at the G1stage of the cell cycle. We found that chromatin is highly flexible throughout. Furthermore, functionally distinct AT- and GC-rich domains were found to exhibit different conformations, and a population-average 3D model of chromosome III could be determined. Chromosome III emerges as a contorted ring.

title: Chromosome Conformation Capture Carbon Copy (5C): a massively parallel solution for mapping interactions between genomic elements.
abstract: Physical interactions between genetic elements located throughout the genome play important roles in gene regulation and can be identified with the Chromosome Conformation Capture (3C) methodology. 3C converts physical chromatin interactions into specific ligation products, which are quantified individually by PCR. Here we present a high-throughput 3C approach, 3C-Carbon Copy (5C), that employs microarrays or quantitative DNA sequencing using 454-technology as detection methods. We applied 5C to analyze a 400-kb region containing the human beta-globin locus and a 100-kb conserved gene desert region. We validated 5C by detection of several previously identified looping interactions in the beta-globin locus. We also identified a new looping interaction in K562 cells between the beta-globin Locus Control Region and the gamma-beta-globin intergenic region. Interestingly, this region has been implicated in the control of developmental globin gene switching. 5C should be widely applicable for large-scale mapping of cis- and trans- interaction networks of genomic elements and for the study of higher-order chromosome structure.

title: Nuclear organization of active and inactive chromatin domains uncovered by chromosome conformation capture–on-chip (4C)
abstract: The spatial organization of DNA in the cell nucleus is an emerging key contributor to genomic function. We developed 4C technology (chromosome conformation capture (3C)-on-chip), which allows for an unbiased genome-wide search for DNA loci that contact a given locus in the nuclear space. We demonstrate here that active and inactive genes are engaged in many long-range intrachromosomal interactions and can also form interchromosomal contacts. The active β-globin locus in fetal liver preferentially contacts transcribed, but not necessarily tissue-specific, loci elsewhere on chromosome 7, whereas the inactive locus in fetal brain contacts different transcriptionally silent loci. A housekeeping gene in a gene-dense region on chromosome 8 forms long-range contacts predominantly with other active gene clusters, both in cis and in trans, and many of these intra- and interchromosomal interactions are conserved between the tissues analyzed. Our data demonstrate that chromosomes fold into areas of active chromatin and areas of inactive chromatin and establish 4C technology as a powerful tool to study nuclear architecture.

title: Circular chromosome conformation capture (4C) uncovers extensive networks of epigenetically regulated intra- and interchromosomal interactions
abstract: Accumulating evidence converges on the possibility that chromosomes interact with each other to regulate transcription in trans. To systematically explore the epigenetic dimension of such interactions, we devised a strategy termed circular chromosome conformation capture (4C). This approach involves a circularization step that enables high-throughput screening of physical interactions between chromosomes without a preconceived idea of the interacting partners. Here we identify 114 unique sequences from all autosomes, several of which interact primarily with the maternally inherited H19 imprinting control region. Imprinted domains were strongly overrepresented in the library of 4C sequences, further highlighting the epigenetic nature of these interactions. Moreover, we found that the direct interaction between differentially methylated regions was linked to epigenetic regulation of transcription in trans. Finally, the patterns of interactions specific to the maternal H19 imprinting control region underwent reprogramming during in vitro maturation of embryonic stem cells. These observations shed new light on development, cancer epigenetics and the evolution of imprinting.

title: Erez Lieberman-Aiden Principles of the Human Genome Comprehensive Mapping of Long-Range Interactions Reveals Folding
abstract: clicking here. colleagues, clients, or customers by , you can order high-quality copies for your If you wish to distribute this article to others here. following the guidelines can be obtained by Permission to republish or repurpose articles or portions of articles ):  April 4, 2012  www.sciencemag.org (this information is current as of The following resources related to this article are available online at http://www.sciencemag.org/content/326/5950/289.full.html version of this article at: including high-resolution figures, can be found in the online Updated information and services,

title: Topological Domains in Mammalian Genomes Identified by Analysis of Chromatin Interactions
abstract: The spatial organization of the genome is intimately linked to its biological function, yet our understanding of higher order genomic structure is coarse, fragmented and incomplete. In the nucleus of eukaryotic cells, interphase chromosomes occupy distinct chromosome territories, and numerous models have been proposed for how chromosomes fold within chromosome territories. These models, however, provide only few mechanistic details about the relationship between higher order chromatin structure and genome function. Recent advances in genomic technologies have led to rapid advances in the study of three-dimensional genome organization. In particular, Hi-C has been introduced as a method for identifying higher order chromatin interactions genome wide. Here we investigate the three-dimensional organization of the human and mouse genomes in embryonic stem cells and terminally differentiated cell types at unprecedented resolution. We identify large, megabase-sized local chromatin interaction domains, which we term ‘topological domains’, as a pervasive structural feature of the genome organization. These domains correlate with regions of the genome that constrain the spread of heterochromatin. The domains are stable across different cell types and highly conserved across species, indicating that topological domains are an inherent property of mammalian genomes. Finally, we find that the boundaries of topological domains are enriched for the insulator binding protein CTCF, housekeeping genes, transfer RNAs and short interspersed element (SINE) retrotransposons, indicating that these factors may have a role in establishing the topological domain structure of the genome.

title: Three-Dimensional Folding and Functional Organization Principles of the Drosophila Genome
abstract: Chromosomes are the physical realization of genetic information and thus form the basis for its readout and propagation. Here we present a high-resolution chromosomal contact map derived from a modified genome-wide chromosome conformation capture approach applied to Drosophila embryonic nuclei. The data show that the entire genome is linearly partitioned into well-demarcated physical domains that overlap extensively with active and repressive epigenetic marks. Chromosomal contacts are hierarchically organized between domains. Global modeling of contact density and clustering of domains show that inactive domains are condensed and confined to their chromosomal territories, whereas active domains reach out of the territory to form remote intra- and interchromosomal contacts. Moreover, we systematically identify specific long-range intrachromosomal contacts between Polycomb-repressed domains. Together, these observations allow for quantitative prediction of the Drosophila chromosomal contact map, laying the foundation for detailed studies of chromosome structure and function in a genetically tractable system.

title: Comparative Hi-C Reveals that CTCF Underlies Evolution of Chromosomal Domain Architecture
abstract: Topological domains are key architectural building blocks of chromosomes, but their functional importance and evolutionary dynamics are not well defined. We performed comparative high-throughput chromosome conformation capture (Hi-C) in four mammals and characterized the conservation and divergence of chromosomal contact insulation and the resulting domain architectures within distantly related genomes. We show that the modular organization of chromosomes is robustly conserved in syntenic regions and that this is compatible with conservation of the binding landscape of the insulator protein CTCF. Specifically, conserved CTCF sites are co-localized with cohesin, are enriched at strong topological domain borders, and bind to DNA motifs with orientations that define the directionality of CTCF’s long-range interactions. Conversely, divergent CTCF binding between species is correlated with divergence of internal domain structure, likely driven by local CTCF binding sequence changes, demonstrating how genome evolution can be linked to a continuous flux of local conformation changes. We also show that large-scale domains are reorganized during genome evolution as intact modules.

title: A 3D Map of the Human Genome at Kilobase Resolution Reveals Principles of Chromatin Looping
abstract: We use in situ Hi-C to probe the 3D architecture of genomes, constructing haploid and diploid maps of nine cell types. The densest, in human lymphoblastoid cells, contains 4.9 billion contacts, achieving 1 kb resolution. We find that genomes are partitioned into contact domains (median length, 185 kb), which are associated with distinct patterns of histone marks and segregate into six subcompartments. We identify ∼10,000 loops. These loops frequently link promoters and enhancers, correlate with gene activation, and show conservation across cell types and species. Loop anchors typically occur at domain boundaries and bind CTCF. CTCF sites at loop anchors occur predominantly (>90%) in a convergent orientation, with the asymmetric motifs "facing" one another. The inactive X chromosome splits into two massive domains and contains large loops anchored at CTCF-binding repeats.

title: Enhancing Hi-C data resolution with deep convolutional neural network HiCPlus
abstract: Although Hi-C technology is one of the most popular tools for studying 3D genome organization, due to sequencing cost, the resolution of most Hi-C datasets are coarse and cannot be used to link distal regulatory elements to their target genes. Here we develop HiCPlus, a computational approach based on deep convolutional neural network, to infer high-resolution Hi-C interaction matrices from low-resolution Hi-C data. We demonstrate that HiCPlus can impute interaction matrices highly similar to the original ones, while only using 1/16 of the original sequencing reads. We show that the models learned from one cell type can be applied to make predictions in other cell or tissue types. Our work not only provides a computational framework to enhance Hi-C data resolution but also reveals features underlying the formation of 3D chromatin interactions.Despite its popularity for measuring the spatial organization of mammalian genomes, the resolution of most Hi-C datasets is coarse due to sequencing cost. Here, Zhang et al. develop HiCPlus, a computational approach based on deep convolutional neural network, to infer high-resolution Hi-C interaction matrices from low-resolution Hi-C data.

title: The Xist lncRNA Exploits Three-Dimensional Genome Architecture to Spread Across the X Chromosome
abstract: Mammalian genomes encode thousands of large noncoding RNAs (lncRNAs), many of which regulate gene expression, interact with chromatin regulatory complexes, and are thought to play a role in localizing these complexes to target loci across the genome. A paradigm for this class of lncRNAs is Xist, which orchestrates mammalian X-chromosome inactivation (XCI) by coating and silencing one X chromosome in females. Despite the central role of RNA-chromatin interactions in this process, the mechanisms by which Xist localizes to DNA and spreads across the X chromosome remain unknown. Upon activation, Xist spreads from its genomic locus to sites in close three-dimensional proximity. Xist modifies chromatin architecture at these sites, thereby repositioning these regions into the Xist compartment (red cloud) and pulling new regions (green, yellow) of the chromosome into closer proximity. These structural changes allow Xist to access new sites and spread across the entire chromosome.  We developed a biochemical method called RNA antisense purification (RAP) to map the localization of a lncRNA across the genome. RAP uses long biotinylated antisense RNA probes to hybridize to and capture a target lncRNA and associated genomic DNA, enabling high-resolution mapping of lncRNA binding sites through high-throughput DNA sequencing. We applied RAP to study the localization of Xist during the initiation and maintenance of XCI.  We show that during the maintenance of XCI, Xist binds broadly across the X chromosome, lacking defined localization sites. Xist preferentially localizes to broad gene-dense regions and excludes genes that escape XCI. At the initiation of XCI in mouse embryonic stem cells, Xist initially transfers to distal regions across the X chromosome that are not defined by specific sequences. Instead, Xist RNA identifies these regions using a proximity-guided search mechanism, exploiting the three-dimensional conformation of the X chromosome to spread to distal regions in close spatial proximity to the Xist genomic locus. Initially, Xist is excluded from actively transcribed genes and accumulates on the periphery of regions containing many active genes. Xist requires its silencing domain to spread across these regions and access the entire chromosome.  Our data suggest a model for how Xist can integrate its two functions—localization to DNA and silencing of gene expression—to coat the entire X chromosome. In this model, Xist exploits three-dimensional conformation to identify and localize to initial target sites and leads to repositioning of these regions into the growing Xist compartment. These structural changes effectively pull new regions of the chromosome closer to the Xist genomic locus, allowing Xist RNA to spread to these newly accessible sites by proximity transfer. This localization strategy capitalizes on the abilities of a lncRNA to act while tethered to its transcription locus and to interact with chromatin regulatory proteins to modify chromatin structure. Beyond Xist, other lncRNAs may use a similar strategy to locate regulatory targets in three-dimensional proximity and to alter chromatin structure to establish local nuclear compartments containing co-regulated targets. Understanding Xist-ance Large noncoding RNAs (lncRNAs) are increasingly appreciated to play important roles in the cell. A number of lncRNAs act to target chromatin regulatory complexes to their sites of action. Engreitz et al. (p. 10.1126/science.1237973, published online 4 July; see the Perspective by Dimond and Fraser) found that the mouse Xist lncRNA, which initiates X-chromosome inactivation, was transferred from its site of transcription to distant sites on the X chromosome purely through their close three-dimensional proximity to the Xist gene. Xist initially localized to the periphery of active genes on the X chromosome but gradually spread across them using its A-repeat domain, until the Xist RNA bound broadly across the inactive X chromosome in differentiated female cells. A large noncoding RNA uses folds within the chromosome to drive the spread of a chromatin repressive complex.  Many large noncoding RNAs (lncRNAs) regulate chromatin, but the mechanisms by which they localize to genomic targets remain unexplored. We investigated the localization mechanisms of the Xist lncRNA during X-chromosome inactivation (XCI), a paradigm of lncRNA-mediated chromatin regulation. During the maintenance of XCI, Xist binds broadly across the X chromosome. During initiation of XCI, Xist initially transfers to distal regions across the X chromosome that are not defined by specific sequences. Instead, Xist identifies these regions by exploiting the three-dimensional conformation of the X chromosome. Xist requires its silencing domain to spread across actively transcribed regions and thereby access the entire chromosome. These findings suggest a model in which Xist coats the X chromosome by searching in three dimensions, modifying chromosome structure, and spreading to newly accessible locations.

title: Probabilistic modeling of Hi-C contact maps eliminates systematic biases to characterize global chromosomal architecture
abstract: Hi-C experiments measure the probability of physical proximity between pairs of chromosomal loci on a genomic scale. We report on several systematic biases that substantially affect the Hi-C experimental procedure, including the distance between restriction sites, the GC content of trimmed ligation junctions and sequence uniqueness. To address these biases, we introduce an integrated probabilistic background model and develop algorithms to estimate its parameters and renormalize Hi-C data. Analysis of corrected human lymphoblast contact maps provides genome-wide evidence for interchromosomal aggregation of active chromatin marks, including DNase-hypersensitive sites and transcriptionally active foci. We observe extensive long-range (up to 400 kb) cis interactions at active promoters and derive asymmetric contact profiles next to transcription start sites and CTCF binding sites. Clusters of interacting chromosomal domains suggest physical separation of centromere-proximal and centromere-distal regions. These results provide a computational basis for the inference of chromosomal architectures from Hi-C experiments.

title: scHiCNorm: a software package to eliminate systematic biases in single-cell Hi-C data
abstract: We build a software package scHiCNorm that uses zero‐inflated and hurdle models to remove biases from single‐cell Hi‐C data. Our evaluations prove that our models can effectively eliminate systematic biases for single‐cell Hi‐C data, which better reveal cell‐to‐cell variances in terms of chromosomal structures. Availability and implementation: scHiCNorm is available at http://dna.cs.miami.edu/scHiCNorm/. Perl scripts are provided that can generate bias features. Pre‐built bias features for human (hg19 and hg38) and mouse (mm9 and mm10) are available to download. R scripts can be downloaded to remove biases.

title: HiCNorm: removing biases in Hi-C data via Poisson regression
abstract: We propose a parametric model, HiCNorm, to remove systematic biases in the raw Hi-C contact maps, resulting in a simple, fast, yet accurate normalization procedure. Compared with the existing Hi-C normalization method developed by Yaffe and Tanay, HiCNorm has fewer parameters, runs >1000 times faster and achieves higher reproducibility.


AVAILABILITY
Freely available on the web at: http://www.people.fas.harvard.edu/∼junliu/HiCNorm/.


CONTACT
jliu@stat.harvard.edu



Supplementary data are available at Bioinformatics online.

title: A Fast Algorithm for Matrix Balancing
abstract: As long as a square nonnegative matrix A contains sufficient nonzero elements, then the matrix can be balanced, that is we can find a diagonal scaling of A that is doubly stochastic. A number of algorithms have been proposed to achieve the balancing, the most well known of these being Sinkhorn-Knopp. In this paper we derive new algorithms based on inner-outer iteration schemes. We show that Sinkhorn-Knopp belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner iteration can give quadratic convergence at low cost.

title: Three-dimensional modeling of chromatin structure from interaction frequency data using Markov chain Monte Carlo sampling
abstract: BackgroundLong-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 (5C) and its variant Hi-C are techniques used to measure the interaction frequency (IF) 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.ResultsWe formulate a probabilistic model linking 5C/Hi-C data to physical distances and describe a Markov chain Monte Carlo (MCMC) 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 (base looping, condensation, and local density) 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 (CCSs) 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 14 at 1Mb resolution that is consistent with previously observed structural properties as measured by 3D-FISH.ConclusionsWe 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.Availabilityhttp://Dostielab.biochem.mcgill.ca

title: Bayesian Inference of Spatial Organizations of Chromosomes
abstract: Knowledge of spatial chromosomal organizations is critical for the study of transcriptional regulation and other nuclear processes in the cell. Recently, chromosome conformation capture (3C) based technologies, such as Hi-C and TCC, have been developed to provide a genome-wide, three-dimensional (3D) view of chromatin organization. Appropriate methods for analyzing these data and fully characterizing the 3D chromosomal structure and its structural variations are still under development. Here we describe a novel Bayesian probabilistic approach, denoted as “Bayesian 3D constructor for Hi-C data” (BACH), to infer the consensus 3D chromosomal structure. In addition, we describe a variant algorithm BACH-MIX to study the structural variations of chromatin in a cell population. Applying BACH and BACH-MIX to a high resolution Hi-C dataset generated from mouse embryonic stem cells, we found that most local genomic regions exhibit homogeneous 3D chromosomal structures. We further constructed a model for the spatial arrangement of chromatin, which reveals structural properties associated with euchromatic and heterochromatic regions in the genome. We observed strong associations between structural properties and several genomic and epigenetic features of the chromosome. Using BACH-MIX, we further found that the structural variations of chromatin are correlated with these genomic and epigenetic features. Our results demonstrate that BACH and BACH-MIX have the potential to provide new insights into the chromosomal architecture of mammalian cells.

title: Large-scale reconstruction of 3D structures of human chromosomes from chromosomal contact data
abstract: Chromosomes are not positioned randomly within a nucleus, but instead, they adopt preferred spatial conformations to facilitate necessary long-range gene–gene interactions and regulations. Thus, obtaining the 3D shape of chromosomes of a genome is critical for understanding how the genome folds, functions and how its genes interact and are regulated. Here, we describe a method to reconstruct preferred 3D structures of individual chromosomes of the human genome from chromosomal contact data generated by the Hi-C chromosome conformation capturing technique. A novel parameterized objective function was designed for modeling chromosome structures, which was optimized by a gradient descent method to generate chromosomal structural models that could satisfy as many intra-chromosomal contacts as possible. We applied the objective function and the corresponding optimization method to two Hi-C chromosomal data sets of both a healthy and a cancerous human B-cell to construct 3D models of individual chromosomes at resolutions of 1 MB and 200 KB, respectively. The parameters used with the method were calibrated according to an independent fluorescence in situ hybridization experimental data. The structural models generated by our method could satisfy a high percentage of contacts (pairs of loci in interaction) and non-contacts (pairs of loci not in interaction) and were compatible with the known two-compartment organization of human chromatin structures. Furthermore, structural models generated at different resolutions and from randomly permuted data sets were consistent.

title: A statistical approach for inferring the 3D structure of the genome
abstract: Recent technological advances allow the measurement, in a single Hi-C experiment, of the frequencies of physical contacts among pairs of genomic loci at a genome-wide scale. The next challenge is to infer, from the resulting DNA–DNA contact maps, accurate 3D models of how chromosomes fold and fit into the nucleus. Many existing inference methods rely on multidimensional scaling (MDS), in which the pairwise distances of the inferred model are optimized to resemble pairwise distances derived directly from the contact counts. These approaches, however, often optimize a heuristic objective function and require strong assumptions about the biophysics of DNA to transform interaction frequencies to spatial distance, and thereby may lead to incorrect structure reconstruction.  We propose a novel approach to infer a consensus 3D structure of a genome from Hi-C data. The method incorporates a statistical model of the contact counts, assuming that the counts between two loci follow a Poisson distribution whose intensity decreases with the physical distances between the loci. The method can automatically adjust the transfer function relating the spatial distance to the Poisson intensity and infer a genome structure that best explains the observed data.  We compare two variants of our Poisson method, with or without optimization of the transfer function, to four different MDS-based algorithms—two metric MDS methods using different stress functions, a non-metric version of MDS and ChromSDE, a recently described, advanced MDS method—on a wide range of simulated datasets. We demonstrate that the Poisson models reconstruct better structures than all MDS-based methods, particularly at low coverage and high resolution, and we highlight the importance of optimizing the transfer function. On publicly available Hi-C data from mouse embryonic stem cells, we show that the Poisson methods lead to more reproducible structures than MDS-based methods when we use data generated using different restriction enzymes, and when we reconstruct structures at different resolutions.  A Python implementation of the proposed method is available at http://cbio.ensmp.fr/pastis.  william-noble@uw.edu or jean-philippe.vert@mines.org

title: 3D Chromosome Modeling with Semi-Definite Programming and Hi-C Data
abstract: For a long period of time, scientists studied genomes while assuming they are linear. Recently, chromosome conformation capture (3C)-based technologies, such as Hi-C, have been developed that provide the loci contact frequencies among loci pairs in a genome-wide scale. The technology unveiled that two far-apart loci can interact in the tested genome. It indicated that the tested genome forms a three-dimensional (3D) chromosomal structure within the nucleus. With the available Hi-C data, our next challenge is to model the 3D chromosomal structure from the 3C-derived data computationally. This article presents a deterministic method called ChromSDE, which applies semi-definite programming techniques to find the best structure fitting the observed data and uses golden section search to find the correct parameter for converting the contact frequency to spatial distance. Further, we develop a measure called consensus index to indicate if the Hi-C data corresponds to a single structure or a mixture of structures. To the best of our knowledge, ChromSDE is the only method that can guarantee recovering the correct structure in the noise-free case. In addition, we prove that the parameter of conversion from contact frequency to spatial distance will change under different resolutions theoretically and empirically. Using simulation data and real Hi-C data, we showed that ChromSDE is much more accurate and robust than existing methods. Finally, we demonstrated that interesting biological findings can be uncovered from our predicted 3D structure.

title: HSA: integrating multi-track Hi-C data for genome-scale reconstruction of 3D chromatin structure
abstract: Genome-wide 3C technologies (Hi-C) are being increasingly employed to study three-dimensional (3D) genome conformations. Existing computational approaches are unable to integrate accumulating data to facilitate studying 3D chromatin structure and function. We present HSA (http://ouyanglab.jax.org/hsa/), a flexible tool that jointly analyzes multiple contact maps to infer 3D chromatin structure at the genome scale. HSA globally searches the latent structure underlying different cleavage footprints. Its robustness and accuracy outperform or rival existing tools on extensive simulations and orthogonal experiment validations. Applying HSA to recent in situ Hi-C data, we found the 3D chromatin structures are highly conserved across various human cell types.

title: Chromosome3D: reconstructing three-dimensional chromosomal structures from Hi-C interaction frequency data using distance geometry simulated annealing
abstract: BackgroundReconstructing three-dimensional structures of chromosomes is useful for visualizing their shapes in a cell and interpreting their function. In this work, we reconstruct chromosomal structures from Hi-C data by translating contact counts in Hi-C data into Euclidean distances between chromosomal regions and then satisfying these distances using a structure reconstruction method rigorously tested in the field of protein structure determination.ResultsWe first evaluate the robustness of the overall reconstruction algorithm on noisy simulated data at various levels of noise by comparing with some of the state-of-the-art reconstruction methods. Then, using simulated data, we validate that Spearman’s rank correlation coefficient between pairwise distances in the reconstructed chromosomal structures and the experimental chromosomal contact counts can be used to find optimum conversion rules for transforming interaction frequencies to wish distances. This strategy is then applied to real Hi-C data at chromosome level for optimal transformation of interaction frequencies to wish distances and for ranking and selecting structures. The chromosomal structures reconstructed from a real-world human Hi-C dataset by our method were validated by the known two-compartment feature of the human chromosome organization. We also show that our method is robust with respect to the change of the granularity of Hi-C data, and consistently produces similar structures at different chromosomal resolutions.ConclusionChromosome3D is a robust method of reconstructing chromosome three-dimensional models using distance restraints obtained from Hi-C interaction frequency data. It is available as a web application and as an open source tool at http://sysbio.rnet.missouri.edu/chromosome3d/.

title: The role of topological constraints in the kinetics of collapse of macromolecules
abstract: It is shown that the kinetics of collapse of a polymer coil consisting of N segments after an abrupt decrease of temperature is a two-stage process if N >> Ne. The first stage takes a time ∼ N2 and leads to the peculiar state — crumpled, or fractal, globule. Any part of a chain of any scale is itself a globule in this state ; these parts are segregated from each other in space due to the non-phantomness of a chain. The chain fold in the crumpled globule is a fractal line with fractal dimension 3, equal to the space dimension. The second stage is a chain knotting ; it is realized by means of reptation-like mechanism of motion, takes a time ∼ N3 and is accompanied by an increase of globule density.

title: Higher-order chromatin structure: bridging physics and biology.
abstract: Advances in microscopy and genomic techniques have provided new insight into spatial chromatin organization inside of the nucleus. In particular, chromosome conformation capture data has highlighted the relevance of polymer physics for high-order chromatin organization. In this context, we review basic polymer states, discuss how an appropriate polymer model can be determined from experimental data, and examine the success and limitations of various polymer models of higher-order interphase chromatin organization. By taking into account topological constraints acting on the chromatin fiber, recently developed polymer models of interphase chromatin can reproduce the observed scaling of distances between genomic loci, chromosomal territories, and probabilities of contacts between loci measured by chromosome conformation capture methods. Polymer models provide a framework for the interpretation of experimental data as ensembles of conformations rather than collections of loops, and will be crucial for untangling functional implications of chromosomal organization.

title: Three-dimensional modeling of the P. falciparum genome during the erythrocytic cycle reveals a strong connection between genome architecture and gene expression.
abstract: The development of the human malaria parasite Plasmodium falciparum is controlled by coordinated changes in gene expression throughout its complex life cycle, but the corresponding regulatory mechanisms are incompletely understood. To study the relationship between genome architecture and gene regulation in Plasmodium, we assayed the genome architecture of P. falciparum at three time points during its erythrocytic (asexual) cycle. Using chromosome conformation capture coupled with next-generation sequencing technology (Hi-C), we obtained high-resolution chromosomal contact maps, which we then used to construct a consensus three-dimensional genome structure for each time point. We observed strong clustering of centromeres, telomeres, ribosomal DNA, and virulence genes, resulting in a complex architecture that cannot be explained by a simple volume exclusion model. Internal virulence gene clusters exhibit domain-like structures in contact maps, suggesting that they play an important role in the genome architecture. Midway during the erythrocytic cycle, at the highly transcriptionally active trophozoite stage, the genome adopts a more open chromatin structure with increased chromosomal intermingling. In addition, we observed reduced expression of genes located in spatial proximity to the repressive subtelomeric center, and colocalization of distinct groups of parasite-specific genes with coordinated expression profiles. Overall, our results are indicative of a strong association between the P. falciparum spatial genome organization and gene expression. Understanding the molecular processes involved in genome conformation dynamics could contribute to the discovery of novel antimalarial strategies.

title: Control of Cell Identity Genes Occurs in Insulated Neighborhoods in Mammalian Chromosomes
abstract: The pluripotent state of embryonic stem cells (ESCs) is produced by active transcription of genes that control cell identity and repression of genes encoding lineage-specifying developmental regulators. Here, we use ESC cohesin ChIA-PET data to identify the local chromosomal structures at both active and repressed genes across the genome. The results produce a map of enhancer-promoter interactions and reveal that super-enhancer-driven genes generally occur within chromosome structures that are formed by the looping of two interacting CTCF sites co-occupied by cohesin. These looped structures form insulated neighborhoods whose integrity is important for proper expression of local genes. We also find that repressed genes encoding lineage-specifying developmental regulators occur within insulated neighborhoods. These results provide insights into the relationship between transcriptional control of cell identity genes and control of local chromosome structure.

title: Methods for identifying higher-order chromatin structure.
abstract: Eukaryotic genomic DNA is combined with histones, nonhistone proteins, and RNA to form chromatin, which is extensively packaged hierarchically to fit inside a cell's nucleus. The nucleosome-comprising a histone octamer with 147 base pairs of DNA wrapped around it-is the initial level and the repeating unit of chromatin packaging, which electron microscopy first made visible to the human eye as "beads on a string" nearly four decades ago. The mechanism and nature of chromatin packaging are still under intense research. Recently, classic methods like chromatin immunoprecipitation and digestion with deoxyribonuclease and micrococcal nuclease have been combined with high-throughput sequencing to provide detailed nucleosome occupancy maps, and chromosome conformation capture and its variants have revealed that higher-order chromatin structure involves long-range loop formation between distant genomic elements. This review discusses the methods for identifying higher-order chromatin structure and the information they have provided on this important topic.

title: The Properties of Genome Conformation and Spatial Gene Interaction and Regulation Networks of Normal and Malignant Human Cell Types
abstract: The spatial conformation of a genome plays an important role in the long-range regulation of genome-wide gene expression and methylation, but has not been extensively studied due to lack of genome conformation data. The recently developed chromosome conformation capturing techniques such as the Hi-C method empowered by next generation sequencing can generate unbiased, large-scale, high-resolution chromosomal interaction (contact) data, providing an unprecedented opportunity to investigate the spatial structure of a genome and its applications in gene regulation, genomics, epigenetics, and cell biology. In this work, we conducted a comprehensive, large-scale computational analysis of this new stream of genome conformation data generated for three different human leukemia cells or cell lines by the Hi-C technique. We developed and applied a set of bioinformatics methods to reliably generate spatial chromosomal contacts from high-throughput sequencing data and to effectively use them to study the properties of the genome structures in one-dimension (1D) and two-dimension (2D). Our analysis demonstrates that Hi-C data can be effectively applied to study tissue-specific genome conformation, chromosome-chromosome interaction, chromosomal translocations, and spatial gene-gene interaction and regulation in a three-dimensional genome of primary tumor cells. Particularly, for the first time, we constructed genome-scale spatial gene-gene interaction network, transcription factor binding site (TFBS) – TFBS interaction network, and TFBS-gene interaction network from chromosomal contact information. Remarkably, all these networks possess the properties of scale-free modular networks.

title: A Protein Domain Co-Occurrence Network Approach for Predicting Protein Function and Inferring Species Phylogeny
abstract: Protein Domain Co-occurrence Network (DCN) is a biological network that has not been fully-studied. We analyzed the properties of the DCNs of H. sapiens, S. cerevisiae, C. elegans, D. melanogaster, and 15 plant genomes. These DCNs have the hallmark features of scale-free networks. We investigated the possibility of using DCNs to predict protein and domain functions. Based on our experiment conducted on 66 randomly selected proteins, the best of top 3 predictions made by our DCN-based aggregated neighbor-counting method achieved a semantic similarity score of 0.81 to the actual Gene Ontology terms of the proteins. Moreover, the top 3 predictions using neighbor-counting, χ2, and a SVM-based method achieved an accuracy of 66%, 59%, and 61%, respectively, when used to predict specific Gene Ontology terms of human target domains. These predictions on average had a semantic similarity score of 0.82, 0.80, and 0.79 to the actual Gene Ontology terms, respectively. We also used DCNs to predict whether a domain is an enzyme domain, and our SVM-based and neighbor-inference method correctly classified 79% and 77% of the target domains, respectively. When using DCNs to classify a target domain into one of the six enzyme classes, we found that, as long as there is one EC number available in the neighboring domains, our SVM-based and neighboring-counting method correctly classified 92.4% and 91.9% of the target domains, respectively. Furthermore, we benchmarked the performance of using DCNs to infer species phylogenies on six different combinations of 398 single-chromosome prokaryotic genomes. The phylogenetic tree of 54 prokaryotic taxa generated by our DCNs-alignment-based method achieved a 93.45% similarity score compared to the Bergey's taxonomy. In summary, our studies show that genome-wide DCNs contain rich information that can be effectively used to decipher protein function and reveal the evolutionary relationship among species.

title: Ring1B compacts chromatin structure and represses gene expression independent of histone ubiquitination.
abstract: How polycomb group proteins repress gene expression in vivo is not known. While histone-modifying activities of the polycomb repressive complexes (PRCs) have been studied extensively, in vitro data have suggested a direct activity of the PRC1 complex in compacting chromatin. Here, we investigate higher-order chromatin compaction of polycomb targets in vivo. We show that PRCs are required to maintain a compact chromatin state at Hox loci in embryonic stem cells (ESCs). There is specific decompaction in the absence of PRC2 or PRC1. This is due to a PRC1-like complex, since decompaction occurs in Ring1B null cells that still have PRC2-mediated H3K27 methylation. Moreover, we show that the ability of Ring1B to restore a compact chromatin state and to repress Hox gene expression is not dependent on its histone ubiquitination activity. We suggest that Ring1B-mediated chromatin compaction acts to directly limit transcription in vivo.

title: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
abstract: We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics are also considered that allow faster performance. This method has been implemented in the IPOPT code, which we demonstrate in a detailed numerical study based on 954 problems from the CUTEr test set. An evaluation is made of several line-search options, and a comparison is provided with two state-of-the-art interior-point codes for nonlinear programming.

title: Collective dynamics of ‘small-world’ networks
abstract: Networks of coupled dynamical systems have been used to model biological oscillators, Josephson junction arrays,, excitable media, neural networks, spatial games, genetic control networks and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon, (popularly known as six degrees of separation). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.

title: A discussion of the solution for the best rotation to relate two sets of vectors
abstract: A method is discussed for obtaining the best proper rotation to relate two sets of vectors.

title: Complex multi-enhancer contacts captured by Genome Architecture Mapping (GAM)
abstract: The organization of the genome in the nucleus and the interactions of genes with their regulatory elements are key features of transcriptional control and their disruption can cause disease. Here we report a genome-wide method, genome architecture mapping (GAM), for measuring chromatin contacts and other features of three-dimensional chromatin topology on the basis of sequencing DNA from a large collection of thin nuclear sections. We apply GAM to mouse embryonic stem cells and identify enrichment for specific interactions between active genes and enhancers across very large genomic distances using a mathematical model termed SLICE (statistical inference of co-segregation). GAM also reveals an abundance of three-way contacts across the genome, especially between regions that are highly transcribed or contain super-enhancers, providing a level of insight into genome architecture that, owing to the technical limitations of current technologies, has previously remained unattainable. Furthermore, GAM highlights a role for gene-expression-specific contacts in organizing the genome in mammalian nuclei.