Chromosome Semi-Definite Embedding

Inference of Spatial Organizations of Chromosomes Using Semi-definite Embedding Approach and Hi-C Data


For a long period of time, scientists studied genomes 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 3D chromsomal structure is to model the 3D chromosomal structure from the 3C-dervied data computationally. This paper 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. To the best of our knowledge, ChromSDE is the only method which 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 show that ChromSDE is much more accurate and robust than existing methods. Finally, we demonstrate that interesting biological findings can be uncovered from our predicted 3D structure.
ChromSDE_Result

ChromSDE is described in our paper:
"Inference of Spatial Organizations of Chromosomes Using Semi-definite Embedding Approach and Hi-C Data", ZZ.Zhang, GL.Li, KC.Toh,and W.Sung, RECOMB 2013: 317-332

Supplementary Document


Obtaining a local copy of ChromSDE
(Last update: May 19, 2014)