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

Area of Science:

• Genomics
• Computational Biology
• Bioinformatics

Background:

• High-throughput chromosome conformation capture (Hi-C) methods provide structural insights into interphase chromosomes.
• Analyzing Hi-C contact maps to identify spatial genomic clusters is computationally challenging due to complex optimization problems.

Purpose of the Study:

• To develop a robust and accurate method for elucidating spatial clusters of genomic regions from Hi-C contact maps.
• To address the challenges of non-convex objectives and non-negativity constraints in genomic spatial clustering.

Main Methods:

• Formulating the spatial clustering problem as a global optimization problem.
• Implementing and comparing evolutionary algorithms with non-negative matrix factorization (NMF).
• Proposing a novel hybrid differential evolution algorithm (HiCDE) integrating NMF for local search within an evolutionary framework.

Main Results:

• HiCDE demonstrates effectiveness and robustness in identifying spatial genomic clusters.
• Performance benchmarking on yeast and human chromosome-wide Hi-C data validates the algorithm.
• Analysis of convergence, complexity, and parameters supports HiCDE's reliability.

Conclusions:

• The developed HiCDE algorithm offers a significant advancement for analyzing chromosome structure using Hi-C data.
• This method provides novel insights into the spatial organization of the genome.
• HiCDE enhances the accuracy and robustness of genomic region clustering.