CEMIG: prediction of the cis-regulatory motif using the de Bruijn graph from ATAC-seq

Yizhong Wang, Yang Li, Cankun Wang, Chan-Wang Jerry Lio, Qin Ma, Bingqiang LiuBriefings in Bioinformatics 2024 · DOI

TL;DR

This paper introduces CEMIG, a novel algorithm that leverages de Bruijn graphs and Hamming distance graphs to predict transcription factor (TF) binding motifs directly from ATAC-seq data. CEMIG outperforms existing methods in identifying cell-type-specific and shared motifs, offering a more robust approach for understanding gene regulation in accessible chromatin regions.

What Problem Does This Paper Address?

Understanding how transcription factors (TFs) bind to DNA is crucial for deciphering gene regulation. While techniques like ChIP-seq have been used for this, they have limitations such as antibody dependency and potential bias. ATAC-seq offers a more direct way to identify accessible chromatin regions, which are likely sites of TF activity. However, existing computational tools often focus on "footprinting" (identifying open regions) rather than precisely predicting the TF binding motifs themselves within these regions. This gap leaves a need for algorithms that can accurately predict motif sites directly from ATAC-seq data, especially considering that TF binding patterns in accessible chromatin might differ from those inferred from ChIP-seq.

Methods

CEMIG employs a multi-stage approach that combines graph theory with statistical modeling:

  • k-mer P-value Calculation: It first calculates the statistical significance (P-value) of short DNA sequences (k-mers) within the ATAC-seq data, using background nucleotide frequencies derived from Markov models.
  • Graph Construction: CEMIG constructs two key graphs:
  • Hamming Distance Graph: Vertices represent k-mers, and edges connect k-mers with a small Hamming distance (indicating sequence similarity).
  • De Bruijn Graph (DBG): This graph represents all k-mers, with edges connecting k-mers that overlap by k-1 nucleotides, capturing sequence contiguity.
  • Graph Clustering: The algorithm clusters k-mers on the Hamming distance graph to group similar sequences. These clusters are then used to merge nodes in the DBG, creating a "cluster graph."
  • Motif Discovery via Path Extension: CEMIG identifies potential motifs by finding paths within the cluster graph. It then refines these paths to predict the motif sequences and their lengths. This approach prioritizes k-mer connectivity within the DBG over simple frequency, allowing it to infer motifs even when direct binding evidence is sparse.

Datasets

The study utilized several datasets for evaluation:

  • ATAC-seq Datasets: 129 datasets from the Cistrome Data Browser were used for benchmarking CEMIG against other methods. These datasets varied in the number of accessible chromatin regions (peaks).
  • GM12878 and K562 Cell Lines: ATAC-seq and RNA-seq data from these two cell lines were used to identify cell-type-specific and shared TF motifs and to investigate their functional implications.
  • ChIP-seq Datasets: 28 ChIP-seq datasets were used to assess CEMIG's performance in a context where motif prediction is more established.
  • HOCOMOCO v.11 Database: This database of known TF binding motifs was used as a reference for validating the motifs predicted by CEMIG.

Key Insights and Ideas

  • De Bruijn Graphs for Motif Discovery: The paper highlights the power of de Bruijn graphs, typically used for genome assembly, in capturing sequence relationships for motif discovery, especially in noisy ATAC-seq data.
  • Hamming Distance for Clustering: Using Hamming distance to cluster k-mers before integrating them into the DBG is a novel way to group similar sequences and improve signal-to-noise ratio.
  • Prioritizing Connectivity over Frequency: CEMIG's strategy of prioritizing k-mer connectivity in the DBG over individual frequency is key to its ability to find motifs in ATAC-seq data, where direct binding evidence might be less concentrated than in ChIP-seq.
  • Bridging Footprinting and Motif Prediction: CEMIG effectively bridges the gap between identifying accessible regions (footprinting) and predicting the specific TF binding motifs within them, a crucial step for functional genomics.

Key Results

  • Superior Performance on ATAC-seq: CEMIG outperformed three established motif discovery methods (BioProspector, MEME-CHIP, and XXmotif) on 129 ATAC-seq datasets across multiple evaluation metrics, including precision, specificity, accuracy, and AUPRC.
  • Accurate Cell-Type Specificity: CEMIG successfully identified both cell-type-specific and shared TF motifs in GM12878 and K562 cell lines, demonstrating its ability to capture nuanced regulatory differences.
  • Functional Validation: The motifs identified by CEMIG were linked to enriched gene ontology (GO) terms and KEGG pathways, providing functional validation for their biological relevance.
  • ChIP-seq Validation: CEMIG also showed high similarity to known motifs in the HOCOMOCO database when applied to ChIP-seq data, indicating its general applicability.

Limitations and Future Work

  • Computational Cost of XXmotif: The paper notes that XXmotif struggled with computational time on larger datasets, highlighting a practical limitation of that method.
  • Focus on ATAC-seq: While CEMIG is designed for ATAC-seq, its performance on other sequencing-based epigenomic data types could be explored.
  • Further Biological Validation: While functional genomics analyses were performed, further experimental validation of specific predicted motifs in relevant biological contexts could strengthen the findings.
  • Algorithm Refinement: The authors suggest that further exploration of graph-based clustering and path extension strategies could lead to even more refined motif predictions.

Summary updated

BibTeX
@article{wang2024cemig,
  author = {Yizhong Wang and Yang Li and Cankun Wang and Chan-Wang Jerry Lio and Qin Ma and Bingqiang Liu},
  title = {{CEMIG: prediction of the cis-regulatory motif using the de Bruijn graph from ATAC-seq}},
  journal = {Briefings in Bioinformatics},
  year = {2024},
  doi = {10.1093/bib/bbad505},
}
Figure