Skip to main content

Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites.

Publication ,  Journal Article
Reddy, TE; DeLisi, C; Shakhnovich, BE
Published in: PLoS Comput Biol
May 2007

Computational prediction of nucleotide binding specificity for transcription factors remains a fundamental and largely unsolved problem. Determination of binding positions is a prerequisite for research in gene regulation, a major mechanism controlling phenotypic diversity. Furthermore, an accurate determination of binding specificities from high-throughput data sources is necessary to realize the full potential of systems biology. Unfortunately, recently performed independent evaluation showed that more than half the predictions from most widely used algorithms are false. We introduce a graph-theoretical framework to describe local sequence similarity as the pair-wise distances between nucleotides in promoter sequences, and hypothesize that densely connected subgraphs are indicative of transcription factor binding sites. Using a well-established sampling algorithm coupled with simple clustering and scoring schemes, we identify sets of closely related nucleotides and test those for known TF binding activity. Using an independent benchmark, we find our algorithm predicts yeast binding motifs considerably better than currently available techniques and without manual curation. Importantly, we reduce the number of false positive predictions in yeast to less than 30%. We also develop a framework to evaluate the statistical significance of our motif predictions. We show that our approach is robust to the choice of input promoters, and thus can be used in the context of predicting binding positions from noisy experimental data. We apply our method to identify binding sites using data from genome scale ChIP-chip experiments. Results from these experiments are publicly available at http://cagt10.bu.edu/BSG. The graphical framework developed here may be useful when combining predictions from numerous computational and experimental measures. Finally, we discuss how our algorithm can be used to improve the sensitivity of computational predictions of transcription factor binding specificities.

Duke Scholars

Published In

PLoS Comput Biol

DOI

EISSN

1553-7358

Publication Date

May 2007

Volume

3

Issue

5

Start / End Page

e90

Location

United States

Related Subject Headings

  • Transcription Factors
  • Sequence Analysis, DNA
  • Protein Binding
  • Promoter Regions, Genetic
  • Molecular Sequence Data
  • Models, Genetic
  • Models, Chemical
  • Computer Simulation
  • Bioinformatics
  • Binding Sites
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reddy, T. E., DeLisi, C., & Shakhnovich, B. E. (2007). Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites. PLoS Comput Biol, 3(5), e90. https://doi.org/10.1371/journal.pcbi.0030090
Reddy, Timothy E., Charles DeLisi, and Boris E. Shakhnovich. “Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites.PLoS Comput Biol 3, no. 5 (May 2007): e90. https://doi.org/10.1371/journal.pcbi.0030090.
Reddy TE, DeLisi C, Shakhnovich BE. Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites. PLoS Comput Biol. 2007 May;3(5):e90.
Reddy, Timothy E., et al. “Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites.PLoS Comput Biol, vol. 3, no. 5, May 2007, p. e90. Pubmed, doi:10.1371/journal.pcbi.0030090.
Reddy TE, DeLisi C, Shakhnovich BE. Binding site graphs: a new graph theoretical framework for prediction of transcription factor binding sites. PLoS Comput Biol. 2007 May;3(5):e90.

Published In

PLoS Comput Biol

DOI

EISSN

1553-7358

Publication Date

May 2007

Volume

3

Issue

5

Start / End Page

e90

Location

United States

Related Subject Headings

  • Transcription Factors
  • Sequence Analysis, DNA
  • Protein Binding
  • Promoter Regions, Genetic
  • Molecular Sequence Data
  • Models, Genetic
  • Models, Chemical
  • Computer Simulation
  • Bioinformatics
  • Binding Sites