Three-dimensional reconstruction of single-cell chromosome structure using recurrence plots

Imputation-free reconstructions of three-dimensional chromosome architectures in human diploid single-cells using allele-specified contacts

Single-cell Hi-C analysis of diploid human cells is difficult because of the lack of dense chromosome contact information and the presence of homologous chromosomes with very similar nucleotide sequences. Thus here, we propose a new algorithm to reconstruct the three-dimensional (3D) chromosomal architectures from the Hi-C dataset of single diploid human cells using allele-specific single-nucleotide variations (SNVs). We modified our recurrence plot-based algorithm, which is suitable for the estimation of the 3D chromosome structure from sparse Hi-C datasets, by newly incorporating a function of discriminating SNVs specific to each homologous chromosome. Here, we eventually regard a contact map as a recurrence plot. Importantly, the proposed method does not require any imputation for ambiguous segment information, but could efficiently reconstruct 3D chromosomal structures in single human diploid cells at a 1-Mb resolution. Datasets of segments without allele-specific SNVs, which were considered to be of little value, can also be used to validate the estimated chromosome structure. Introducing an additional mathematical measure called a refinement further improved the resolution to 40-kb or 100-kb. The reconstruction data supported the notion that human chromosomes form chromosomal territories and take fractal structures where the dimension for the underlying chromosome structure is a non-integer value.

Reconstruct high-resolution 3D genome structures for diverse cell-types using FLAMINGO

High-resolution reconstruction of spatial chromosome organizations from chromatin contact maps is highly demanded, but is hindered by extensive pairwise constraints, substantial missing data, and limited resolution and cell-type availabilities. Here, we present FLAMINGO, a computational method that addresses these challenges by compressing inter-dependent Hi-C interactions to delineate the underlying low-rank structures in 3D space, based on the low-rank matrix completion technique. FLAMINGO successfully generates 5 kb- and 1 kb-resolution spatial conformations for all chromosomes in the human genome across multiple cell-types, the largest resources to date. Compared to other methods using various experimental metrics, FLAMINGO consistently demonstrates superior accuracy in recapitulating observed structures with raises in scalability by orders of magnitude. The reconstructed 3D structures efficiently facilitate discoveries of higher-order multi-way interactions, imply biological interpretations of long-range QTLs, reveal geometrical properties of chromatin, and provide high-resolution references to understand structural variabilities. Importantly, FLAMINGO achieves robust predictions against high rates of missing data and significantly boosts 3D structure resolutions. Moreover, FLAMINGO shows vigorous cross cell-type structure predictions that capture cell-type specific spatial configurations via integration of 1D epigenomic signals. FLAMINGO can be widely applied to large-scale chromatin contact maps and expand high-resolution spatial genome conformations for diverse cell-types.

High-resolution reconstruction of spatial chromosome organisation is in demand. Here the authors report FLAMINGO, for reconstructing high-resolution 3D Genome Organisation from HiC data which they use to generate both 5 kb and 1 kb-resolution 3D chromosomal structures for the human genome.

Fast reconstruction of an original continuous series from a recurrence plot

We propose an algorithm to refine the reconstruction of an original time series given a recurrence plot, which is also referred to as a contact map. The refinement process calculates the local distances based on the Jaccard coefficients with the neighbors in the previous resolution for each point and takes their weighted average using local distances. We demonstrate the utility of our method using two examples.

Single-cell Hi-C data analysis: safety in numbers

Over the past decade, genome-wide assays for chromatin interactions in single cells have enabled the study of individual nuclei at unprecedented resolution and throughput. Current chromosome conformation capture techniques survey contacts for up to tens of thousands of individual cells, improving our understanding of genome function in 3D. However, these methods recover a small fraction of all contacts in single cells, requiring specialised processing of sparse interactome data. In this review, we highlight recent advances in methods for the interpretation of single-cell genomic contacts. After discussing the strengths and limitations of these methods, we outline frontiers for future development in this rapidly moving field.

Computational methods for predicting 3D genomic organization from high-resolution chromosome conformation capture data

The advent of high-resolution chromosome conformation capture assays (such as 5C, Hi-C and Pore-C) has allowed for unprecedented sequence-level investigations into the structure-function relationship of the genome. In order to comprehensively understand this relationship, computational tools are required that utilize data generated from these assays to predict 3D genome organization (the 3D genome reconstruction problem). Many computational tools have been developed that answer this need, but a comprehensive comparison of their underlying algorithmic approaches has not been conducted. This manuscript provides a comprehensive review of the existing computational tools (from November 2006 to September 2019, inclusive) that can be used to predict 3D genome organizations from high-resolution chromosome conformation capture data. Overall, existing tools were found to use a relatively small set of algorithms from one or more of the following categories: dimensionality reduction, graph/network theory, maximum likelihood estimation (MLE) and statistical modeling. Solutions in each category are far from maturity, and the breadth and depth of various algorithmic categories have not been fully explored. While the tools for predicting 3D structure for a genomic region or single chromosome are diverse, there is a general lack of algorithmic diversity among computational tools for predicting the complete 3D genome organization from high-resolution chromosome conformation capture data.

Three-dimensional chromatin ensemble reconstruction via stochastic embedding

We propose a comprehensive method for reconstructing the whole-genome chromatin ensemble from the Hi-C data. The procedure starts from Markov state modeling (MSM), delineating the structural hierarchy of chromatin organization with partitioning and effective interactions archetypal for corresponding levels of hierarchy. The stochastic embedding procedure introduced in this work provides the 3D ensemble reconstruction, using effective interactions obtained by the MSM as the input. As a result, we obtain the structural ensemble of a genome, allowing one to model the functional and the cell-type variability in the chromatin structure. The whole-genome reconstructions performed on the human B lymphoblastoid (GM12878) and lung fibroblast (IMR90) Hi-C data unravel distinctions in their morphologies and in the spatial arrangement of intermingling chromosomal territories, paving the way to studies of chromatin dynamics, developmental changes, and conformational transitions taking place in normal cells and during potential pathological developments.

Computational approaches for inferring 3D conformations of chromatin from chromosome conformation capture data

Chromosome conformation capture (3C) and its variants are powerful experimental techniques for probing intra- and inter-chromosomal interactions within cell nuclei at high resolution and in a high-throughput, quantitative manner. The contact maps derived from such experiments provide an avenue for inferring the 3D spatial organization of the genome. This review provides an overview of the various computational methods developed in the past decade for addressing the very important but challenging problem of deducing the detailed 3D structure or structure population of chromosomal domains, chromosomes, and even entire genomes from 3C contact maps.

Joint inference and alignment of genome structures enables characterization of compartment-independent reorganization across cell types

BACKGROUND

Comparisons of Hi-C data sets between cell types and conditions have revealed differences in topologically associated domains (TADs) and A/B compartmentalization, which are correlated with differences in gene regulation. However, previous comparisons have focused on known forms of 3D organization while potentially neglecting other functionally relevant differences. We aimed to create a method to quantify all locus-specific differences between two Hi-C data sets.

RESULTS

We developed MultiMDS to jointly infer and align 3D chromosomal structures from two Hi-C data sets, thereby enabling a new way to comprehensively quantify relocalization of genomic loci between cell types. We demonstrate this approach by comparing Hi-C data across a variety of cell types. We consistently find relocalization of loci with minimal difference in A/B compartment score. For example, we identify compartment-independent relocalizations between GM12878 and K562 cells that involve loci displaying enhancer-associated histone marks in one cell type and polycomb-associated histone marks in the other.

CONCLUSIONS

MultiMDS is the first tool to identify all loci that relocalize between two Hi-C data sets. Our method can identify 3D localization differences that are correlated with cell-type-specific regulatory activities and which cannot be identified using other methods.

Two efficient calculations of edit distance between marked point processes

In this paper, we propose to use linear programming methods or a more specialized method, namely, the Hungarian method, for speeding up the exact calculation of an edit distance for marked point processes [Y. Hirata and K. Aihara, Chaos 25, 123117 (2015)]. The key observation is that the problem of calculating the edit distance reduces to a matching problem on a bipartite graph. Our preliminary numerical results show that the proposed implementations are faster than the conventional ones by a factor of 10-1000.

Nonlinear and Non-Stationary Detection for Measured Dynamic Signal from Bridge Structure Based on Adaptive Decomposition and Multiscale Recurrence Analysis

To test the nonlinearity and non-stationarity of measured dynamic signals from a bridge structure with high-level noise and dense modal characteristics, a method that combines the adaptive signal decomposition with the recurrence analysis is proposed to solve the difficulty of testing nonlinearity and non-stationarity of bridge structure signals. A novel white noise assistance and cluster analysis are introduced to the ensemble empirical mode decomposition to alleviate mode-mixing issues and generate single-mode intrinsic mode functions. Combining the hypothesis-testing scheme of nonstationary and nonlinear synchronization and surrogate techniques, a data-driven recurrence quantification analysis method is proposed and a novel recurrence quantification measure pairs are set up. To demonstrate the efficacy of the proposed methodology, complex signals, which are collected from a carefully instrumented model of a cable-stayed bridge, are utilized as the basis for comparing with traditional nonlinear and non-stationary test methods. Results show that the proposed multiscale recurrence method is feasible and effective for applications to a nonlinear and non-stationary test for real complex civil structures.

Unfolding the Genome: The Case Study of P. falciparum

The development of new ways to probe samples for the three-dimensional (3D) structure of DNA paves the way for in depth and systematic analyses of the genome architecture. 3C-like methods coupled with high-throughput sequencing can now assess physical interactions between pairs of loci in a genome-wide fashion, thus enabling the creation of genome-by-genome contact maps. The spreading of such protocols creates many new opportunities for methodological development: how can we infer 3D models from these contact maps? Can such models help us gain insights into biological processes? Several recent studies applied such protocols to P. falciparum (the deadliest of the five human malaria parasites), assessing its genome organization at different moments of its life cycle. With its small genomic size, fairly simple (yet changing) genomic organization during its lifecyle and strong correlation between chromatin folding and gene expression, this parasite is the ideal case study for applying and developing methods to infer 3D models and use them for downstream analysis. Here, I review a set of methods used to build and analyse three-dimensional models from contact maps data with a special highlight on P. falciparum's genome organization.

Regenerating time series from ordinal networks

Recently proposed ordinal networks not only afford novel methods of nonlinear time series analysis but also constitute stochastic approximations of the deterministic flow time series from which the network models are constructed. In this paper, we construct ordinal networks from discrete sampled continuous chaotic time series and then regenerate new time series by taking random walks on the ordinal network. We then investigate the extent to which the dynamics of the original time series are encoded in the ordinal networks and retained through the process of regenerating new time series by using several distinct quantitative approaches. First, we use recurrence quantification analysis on traditional recurrence plots and order recurrence plots to compare the temporal structure of the original time series with random walk surrogate time series. Second, we estimate the largest Lyapunov exponent from the original time series and investigate the extent to which this invariant measure can be estimated from the surrogate time series. Finally, estimates of correlation dimension are computed to compare the topological properties of the original and surrogate time series dynamics. Our findings show that ordinal networks constructed from univariate time series data constitute stochastic models which approximate important dynamical properties of the original systems.