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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

7 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Article number7974767
Pages (from-to)400-407
Journal / PublicationIEEE Transactions on Nanobioscience
Issue number6
Online published11 Jul 2017
Publication statusPublished - Sept 2017


High-throughput chromosome-conformationcapture (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.

Research Area(s)

  • chromatin conformation capture, Differential evolution, genomic regions, non-negative matrix factorization