HiC-Spector: A matrix library for spectral and reproducibility analysis of Hi-C contact maps

Koon‐Kiu Yan, Galip Guürkan Yardimci, William Stafford Noble, Mark GersteinbioRxiv 2016 · DOI

TL;DR

This paper introduces HiC-spector, a Julia library for analyzing Hi-C contact maps, which represent the 3D organization of the genome. It presents a novel spectral decomposition-based metric to quantify the reproducibility of Hi-C experiments, effectively distinguishing between biological replicates, pseudo-replicates, and different cell types.

What Problem Does This Paper Address?

Understanding the three-dimensional (3D) organization of the genome is crucial for deciphering its function. Techniques like Hi-C generate "contact maps," which are essentially matrices showing how frequently different genomic regions are in close physical proximity. However, these 2D data structures are distinct from traditional 1D genomic signals, posing new computational challenges. A key question is how to reliably assess the reproducibility of Hi-C experiments. Are two experiments truly capturing the same underlying genomic structure, or are the observed similarities due to chance or experimental artifacts? This paper aims to address this by providing tools for analyzing these contact maps and, specifically, by developing a robust method to quantify their similarity and thus experimental reproducibility.

Methods

The core of HiC-spector's approach lies in spectral analysis of the Hi-C contact maps. A contact map is represented as a symmetric, non-negative adjacency matrix $W$, where $W_{ij}$ indicates the contact frequency between genomic loci $i$ and $j$. The authors then construct the Laplacian matrix $L$ from $W$, often in a normalized form ($L = D^{-1/2}LD^{-1/2}$). The eigenvalues and eigenvectors of this Laplacian matrix, known as its "spectrum," capture the underlying structure of the genomic interactions.

The paper introduces a novel reproducibility metric, $S_r(A, B)$, which quantifies the similarity between two contact maps (A and B) by comparing the Euclidean distance between their corresponding leading eigenvectors. The intuition is that eigenvectors associated with smaller eigenvalues capture the larger-scale, more stable structures of the genome, and thus should be more similar between reproducible experiments. They propose using the first $r$ leading eigenvectors, with $r=20$ found to be a good practical choice. To provide a score between 0 and 1, they rescale this distance into a "reproducibility score" $Q(A,B)$.

Beyond the reproducibility metric, HiC-spector also includes functions for matrix balancing (using the Knight-Ruiz algorithm), estimating average contact frequency with genomic distance, and identifying A/B compartments.

Datasets

The paper evaluates its reproducibility metric using Hi-C contact maps from 11 cancer cell lines obtained from the ENCODE consortium. They analyze three sets of comparisons:

  • Biological replicates: Pairs of replicates from the same experiment.
  • Pseudo-replicates: Created by pooling reads from two replicates and then down-sampling.
  • Different cell types: Pairs of maps from distinct cell lines.

The paper does not introduce a new benchmark dataset but rather uses existing data to validate its proposed metric.

Key Insights and Ideas

  • Spectral decomposition reveals genomic structure: The eigenvalues and eigenvectors of the Laplacian matrix of a Hi-C contact map effectively capture the large-scale structural organization of the genome, with lower-order eigenvectors representing more stable and significant features.
  • High-order eigenvectors are noise: The paper demonstrates that the Euclidean distance between high-order eigenvectors of two contact maps approaches the distance between randomly sampled unit vectors. This suggests that these higher-order components are primarily noise and do not contain meaningful biological signal.
  • Reproducibility metric effectively discriminates: The developed spectral decomposition-based reproducibility score ($Q$) successfully distinguishes between different levels of similarity: pseudo-replicates show higher scores than biological replicates, which in turn show higher scores than maps from different cell types. This indicates the metric is sensitive to biological variation and experimental consistency.

Key Results

The HiC-spector library provides a suite of tools for Hi-C data analysis, with a highlight being the novel reproducibility metric. This metric, based on comparing leading eigenvectors, was shown to effectively differentiate between:

  • Pseudo-replicates: Highest reproducibility scores.
  • Biological replicates: Intermediate reproducibility scores.
  • Different cell types: Lowest reproducibility scores.

The paper also reports that for a pair of human chromosome 1 contact maps with a bin size of 40kb, the computation of the reproducibility metric takes approximately 80 seconds on a laptop with a 2.8GHz Intel Core i7 processor and 16GB of RAM, indicating efficient performance for practical use.

Limitations and Future Work

Limitations: * The paper notes that the runtime for evaluating the reproducibility metric is heavily dependent on the size of the contact maps, which can be a bottleneck for very high-resolution data. * While $r=20$ was found to be a good rule of thumb for selecting leading eigenvectors, the optimal choice of $r$ might vary depending on the specific dataset or biological question.

Future Work: * The authors provide the source code in Julia and documentation, suggesting that the library is intended for further development and application by the research community. * The inclusion of functions for matrix balancing, contact frequency estimation, and A/B compartment identification indicates a broader aim to provide a comprehensive toolkit for Hi-C analysis.

Summary updated

Abstract

Abstract Summary Genome-wide proximity ligation based assays like Hi-C have opened a window to the 3D organization of the genome. In so doing, they present data structures that are different from conventional 1D signal tracks. To exploit the 2D nature of Hi-C contact maps, matrix techniques like spectral analysis are particularly useful. Here, we present HiC-spector, a collection of matrix-related functions for analyzing Hi-C contact maps. In particular, we introduce a novel reproducibility metric for quantifying the similarity between contact maps based on spectral decomposition. The metric successfully separates contact maps mapped from Hi-C data coming from biological replicates, pseudo-replicates and different cell types. Availability Source code in Julia and the documentation of HiC-spector can be freely obtained at https://github.com/gersteinlab/HiC_spector Contact [email protected]
BibTeX
@misc{yan2016hic,
  author = {Koon‐Kiu Yan and Galip Guürkan Yardimci and William Stafford Noble and Mark Gerstein},
  title = {{HiC-Spector: A matrix library for spectral and reproducibility analysis of Hi-C contact maps}},
  year = {2016},
  doi = {10.1101/088922},
  howpublished = {bioRxiv},
}

Loading related content...

Figure