Reconstruction of 3D genome architecture via a two-stage algorithm

Abstract

Background: The three-dimensional (3D) configuration of chromosomes within the eukaryote nucleus is an important factor for several cellular functions, including gene expression regulation, and has also been linked with cancer-causing translocation events. While visualization of such architecture remains limited to low resolutions, the ability to infer structures at increasing resolutions has been enabled by recently-devised chromosome conformation capture techniques. In particular, when coupled with next generation sequencing, such methods yield an inventory of genome-wide chromatin contacts or interactions. Various algorithms have been advanced to operate on such contact data to produce reconstructed 3D configurations. Studies have shown that these reconstructions can provide added value over raw interaction data with respect to downstream biological insights. However, only limited, low-resolution reconstructions have been realized for mammals due to computational bottlenecks.

Results: Here we propose a two-stage algorithm to partially overcome these computational barriers. The central idea is to initially utilize existing reconstruction techniques on an individual chromosome basis, using intra-chromosomal contacts, and then to relatively position these chromosome-level reconstructions using inter-chromosomal contacts. This two-stage strategy represents a natural approach in view of the within- versus between- chromosome distribution of contacts. It can increase resolution ≈ 20 fold for mouse and human. After describing the algorithm we present 3D architectures for mouse embryonic stem cells and human lymphoblastoid cells. We evaluate the impact of several factors on reconstruction reproducibility and explore a variety of sampling schemes. We further analyze replicate data at differing resolutions obtained from recently devised in situ Hi-C assays. In all instances we demonstrate insensitivity of the whole-genome 3D reconstruction obtained by the two-stage algorithm to the sampling strategy used.

Conclusions: Our two-stage algorithm has the potential to significantly increase the resolution of 3D genome reconstructions. The improvements are such that we can progress from 1 Mb resolution to 100 kb resolution, notable since this latter value has been identified as critical to inferring topological domains in analyses performed on the contact (rather than 3D) level.

Fig. 1

3D reconstruction for mouse embryonic stem cells. Whole genome architecture, at 1 Mb resolution, from applying the two-stage reconstruction algorithm with 10 % equi-spaced sampling to mESC cell line data [11]

Fig. 2

3D reconstruction for human lymphoblastoid cells. Whole genome architecture, at 1 Mb resolution, from applying the two-stage reconstruction algorithm with 10 % equi-spaced sampling to human GM06990 cell line data [5]

Fig. 3

RMSDs for a series of sampling proportions and schemes. RMSD comparisons across a range (0.10,0.20,…,1.0) of second stage sampling proportions and schemes (equi-spaced, aggregated and first principal component based) for reconstructions from human GM06990 lymphoblastoid cell lines [5]. Hybrid and non-hybrid algorithms and MDS weighting options are also contrasted. Comparisons are performed with respect to a referent reconstruction based on equi-spaced sampling at a proportion of 1.0, under the non-hybrid algorithm with inverse squared distance weighting

Fig. 4

RMSD comparisons between replicates at 1 Mb resolution. Comparisons across a range (0.10,0.20,…,1.0) of second stage equi-spaced sampling proportions for reconstructions from primary and replicate human GM12878 B-lymphoblastoid cell line pools [12] at a resolution of 1 Mb. The referent reconstruction is based on a proportion of 1.0 for the primary series. Overplotting obscures coincident points at some sampling proportions

Fig. 5

RMSD comparisons between replicates at 500 kb resolution. Comparisons across a range (0.10,0.20,…,1.0) of second stage equi-spaced sampling proportions for reconstructions from primary and replicate human GM12878 B-lymphoblastoid cell line pools [12] at a resolution of 500 kb. The referent reconstruction is based on a proportion of 1.0 for the primary series. Overplotting obscures coincident points at some sampling proportions