Evolving Spatial Clusters of Genomic Regions From High-Throughput Chromatin Conformation Capture Data

High-throughput chromosome-conformation-capture (Hi-C) methods have revealed a multitude of structural insights into interphase chromosomes. In this paper, we elucidate the spatial clusters of genomic regions from Hi-C contact maps by formulating the underlying problem as a global optimization problem. Given its nonconvex objective and nonnegativity constraints, we implement several evolutionary algorithms and compare their performance with non-negative matrix factorization, revealing novel insights into the problem. In order to obtain robust and accurate spatial clusters, we propose and describe a novel hybrid differential evolution algorithm called HiCDE, which adopts non-negative matrix factorization as local search according to each candidate individual provided by differential evolution algorithm. Based on the fitness value of each individual, the population is partitioned into three subpopulations with different sizes; each subpopulation is equipped with a specific mutation strategy for either exploitation or exploration. Finally, all control parameters in the pool have equal probability to be selected for generating trial vectors. The effectiveness and robustness of HiCDE are supported by real-world performance benchmarking on chromosome-wide Hi-C contact maps of yeast and human, time complexity analysis, convergence analysis, parameter analysis, and case studies.