Large-scale chromosomal 3D structure reconstruction

Abstract

The recent advanced technique in genome analysis has demonstrated that chromatins have preferred three dimensional (3D) structures.Through spatial folding, two distance genes along nucleotide sequence can contact each other in space. Such property is of vital importance to the functional activities of genes, like gene controlling and gene-gene interactions. In order to understand the structure of chromosomal 3D structures, lot of efforts have put into this topic in the past ten years. Like the 3C methods, which can capture the physical contacts of chromosomal fragments. But most of them can not analysis the whole genome simultaneous. Lieberman-Aiden et. al. devised a new method named Hi-C in 2009 [1], as a modified 3C technique, which can perform a high-throughput analysis of the whole genome contact informations at the same time. They demonstrated with the analysis of human genome data at a 1MB resolutions, and recently, they made it at a 5Kb resolutions [2] with in situ protocol. Lot's of algorithms, like ChromSDE, and ShRec3D, working on the reconstruction problems. However they cannot handle volume dataset well. There are two difficults, the data size is too large which can not store in memory or the running time is not acceptable. Hence, we proposed a divide-conquer approach to perform the reconstruction task, which is magnitude faster than other algorithms. And by conducting a two phases process, coarse-grain reconstruction and refinement, our algorithm also produced a more credible structure.