Calculating transcription factor binding maps for chromatin.

Area of Science:

• Computational Biology
• Genomics
• Molecular Biology

Background:

• High-throughput experiments generate extensive data on DNA sequence-dependent binding affinities of transcription factors (TF).
• Predicting TF binding maps in a chromatin context remains computationally challenging due to factors like nucleosome competition and DNA unwrapping.

Purpose of the Study:

• To evaluate and compare different algorithmic approaches for calculating TF binding maps.
• To develop and present an improved dynamic programming algorithm for TF binding prediction in chromatin.

Main Methods:

• Consideration of DNA as a one-dimensional lattice.
• Analysis of five algorithm classes: binary variable, combinatorial, sequence generating function, transfer matrix, and dynamic programming.
• Development of a dynamic programming algorithm incorporating nucleosome occupancy and DNA unwrapping.

Main Results:

• The binary variable algorithm's exponential time complexity limits its application to small genomic regions.
• Transfer matrix and dynamic programming approaches are suitable for regulatory regions with overlapping binding sites.
• The developed dynamic programming algorithm accounts for TF access to nucleosomal DNA.
• Dynamic programming is faster than the transfer matrix method without nucleosomes, but the transfer matrix method is faster when nucleosome unwrapping is considered.

Conclusions:

• Algorithmic advancements are crucial for accurate genome-wide TF binding map prediction.
• The choice of algorithm depends on factors like DNA length, binding site overlap, and the inclusion of nucleosome dynamics.
• Further strategies are needed to optimize calculations for large-scale genome-wide analyses.