IDEAS home Printed from https://ideas.repec.org/a/plo/pcbi00/0030090.html
   My bibliography  Save this article

Binding Site Graphs: A New Graph Theoretical Framework for Prediction of Transcription Factor Binding Sites

Author

Listed:
  • Timothy E Reddy
  • Charles DeLisi
  • Boris E Shakhnovich

Abstract

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.: A historically difficult problem in computational biology is the identification of transcription factor binding sites (TFBS) in the promoters of co-regulated genes. With increasing emphasis on research in transcriptional regulation, this problem is also uniquely relevant to emerging results from recent experiments in high-throughput and systems biology. Despite extensive research in the area, recent evaluations of previously published techniques show much room for improvement. In this paper, we introduce a fundamentally new approach to the identification of TFBS. First, we start by representing nucleotides in promoters as an undirected, weighted graph. Given this representation of a binding site graph (BSG), we employ relatively simple graph clustering techniques to identify functional TFBS. We show that BSG predictions significantly outperform all previously evaluated methods in nearly every performance measure using a standardized assessment benchmark. We also find that this approach is more robust than traditional Gibbs sampling to selection of input promoters, and thus more likely to perform well under noisy experimental conditions. Finally, BSGs are very good at predicting specificity determining nucleotides. Using BSG predictions, we were able to confirm recent experimental results on binding specificity of E-box TFs CBF1 and PHO4 and predict novel specificity determining nucleotides for TYE7.

Suggested Citation

  • Timothy E Reddy & Charles DeLisi & Boris E Shakhnovich, 2007. "Binding Site Graphs: A New Graph Theoretical Framework for Prediction of Transcription Factor Binding Sites," PLOS Computational Biology, Public Library of Science, vol. 3(5), pages 1-11, May.
  • Handle: RePEc:plo:pcbi00:0030090
    DOI: 10.1371/journal.pcbi.0030090
    as

    Download full text from publisher

    File URL: https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.0030090
    Download Restriction: no

    File URL: https://journals.plos.org/ploscompbiol/article/file?id=10.1371/journal.pcbi.0030090&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pcbi.0030090?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Rahul Siddharthan & Eric D Siggia & Erik van Nimwegen, 2005. "PhyloGibbs: A Gibbs Sampling Motif Finder That Incorporates Phylogeny," PLOS Computational Biology, Public Library of Science, vol. 1(7), pages 1-23, December.
    2. Christopher T. Harbison & D. Benjamin Gordon & Tong Ihn Lee & Nicola J. Rinaldi & Kenzie D. Macisaac & Timothy W. Danford & Nancy M. Hannett & Jean-Bosco Tagne & David B. Reynolds & Jane Yoo & Ezra G., 2004. "Transcriptional regulatory code of a eukaryotic genome," Nature, Nature, vol. 431(7004), pages 99-104, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Harri Lähdesmäki & Alistair G Rust & Ilya Shmulevich, 2008. "Probabilistic Inference of Transcription Factor Binding from Multiple Data Sources," PLOS ONE, Public Library of Science, vol. 3(3), pages 1-24, March.
    2. Kenzie D MacIsaac & Ernest Fraenkel, 2006. "Practical Strategies for Discovering Regulatory DNA Sequence Motifs," PLOS Computational Biology, Public Library of Science, vol. 2(4), pages 1-10, April.
    3. Ivan Dotu & Scott I Adamson & Benjamin Coleman & Cyril Fournier & Emma Ricart-Altimiras & Eduardo Eyras & Jeffrey H Chuang, 2018. "SARNAclust: Semi-automatic detection of RNA protein binding motifs from immunoprecipitation data," PLOS Computational Biology, Public Library of Science, vol. 14(3), pages 1-25, March.
    4. Matvei Khoroshkin & Andrey Buyan & Martin Dodel & Albertas Navickas & Johnny Yu & Fathima Trejo & Anthony Doty & Rithvik Baratam & Shaopu Zhou & Sean B. Lee & Tanvi Joshi & Kristle Garcia & Benedict C, 2024. "Systematic identification of post-transcriptional regulatory modules," Nature Communications, Nature, vol. 15(1), pages 1-21, December.
    5. Zing Tsung-Yeh Tsai & Shin-Han Shiu & Huai-Kuang Tsai, 2015. "Contribution of Sequence Motif, Chromatin State, and DNA Structure Features to Predictive Models of Transcription Factor Binding in Yeast," PLOS Computational Biology, Public Library of Science, vol. 11(8), pages 1-22, August.
    6. Gross, Eitan, 2015. "Effect of environmental stress on regulation of gene expression in the yeast," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 430(C), pages 224-235.
    7. Armita Nourmohammad & Michael Lässig, 2011. "Formation of Regulatory Modules by Local Sequence Duplication," PLOS Computational Biology, Public Library of Science, vol. 7(10), pages 1-12, October.
    8. Wei-Sheng Wu & Fu-Jou Lai, 2016. "Detecting Cooperativity between Transcription Factors Based on Functional Coherence and Similarity of Their Target Gene Sets," PLOS ONE, Public Library of Science, vol. 11(9), pages 1-12, September.
    9. Rahul Siddharthan & Eric D Siggia & Erik van Nimwegen, 2005. "PhyloGibbs: A Gibbs Sampling Motif Finder That Incorporates Phylogeny," PLOS Computational Biology, Public Library of Science, vol. 1(7), pages 1-23, December.
    10. Jens Keilwagen & Jan Grau & Ivan A Paponov & Stefan Posch & Marc Strickert & Ivo Grosse, 2011. "De-Novo Discovery of Differentially Abundant Transcription Factor Binding Sites Including Their Positional Preference," PLOS Computational Biology, Public Library of Science, vol. 7(2), pages 1-13, February.
    11. Guo-Cheng Yuan & Jun S Liu, 2008. "Genomic Sequence Is Highly Predictive of Local Nucleosome Depletion," PLOS Computational Biology, Public Library of Science, vol. 4(1), pages 1-11, January.
    12. Jia Lu & Xiaoyi Cao & Sheng Zhong, 2018. "A likelihood approach to testing hypotheses on the co-evolution of epigenome and genome," PLOS Computational Biology, Public Library of Science, vol. 14(12), pages 1-28, December.
    13. Saket Navlakha & Anthony Gitter & Ziv Bar-Joseph, 2012. "A Network-based Approach for Predicting Missing Pathway Interactions," PLOS Computational Biology, Public Library of Science, vol. 8(8), pages 1-13, August.
    14. Leelavati Narlikar & Raluca Gordân & Alexander J Hartemink, 2007. "A Nucleosome-Guided Map of Transcription Factor Binding Sites in Yeast," PLOS Computational Biology, Public Library of Science, vol. 3(11), pages 1-10, November.
    15. Jeremiah J Faith & Boris Hayete & Joshua T Thaden & Ilaria Mogno & Jamey Wierzbowski & Guillaume Cottarel & Simon Kasif & James J Collins & Timothy S Gardner, 2007. "Large-Scale Mapping and Validation of Escherichia coli Transcriptional Regulation from a Compendium of Expression Profiles," PLOS Biology, Public Library of Science, vol. 5(1), pages 1-13, January.
    16. Joshua S Weitz & Philip N Benfey & Ned S Wingreen, 2007. "Evolution, Interactions, and Biological Networks," PLOS Biology, Public Library of Science, vol. 5(1), pages 1-3, January.
    17. Saeed Omidi & Mihaela Zavolan & Mikhail Pachkov & Jeremie Breda & Severin Berger & Erik van Nimwegen, 2017. "Automated incorporation of pairwise dependency in transcription factor binding site prediction using dinucleotide weight tensors," PLOS Computational Biology, Public Library of Science, vol. 13(7), pages 1-22, July.
    18. Aqil M Azmi & Abdulrakeeb Al-Ssulami, 2014. "Encoded Expansion: An Efficient Algorithm to Discover Identical String Motifs," PLOS ONE, Public Library of Science, vol. 9(5), pages 1-9, May.
    19. Dana S F Homsi & Vineet Gupta & Gary D Stormo, 2009. "Modeling the Quantitative Specificity of DNA-Binding Proteins from Example Binding Sites," PLOS ONE, Public Library of Science, vol. 4(8), pages 1-9, August.
    20. Manikandan Narayanan & Adrian Vetta & Eric E Schadt & Jun Zhu, 2010. "Simultaneous Clustering of Multiple Gene Expression and Physical Interaction Datasets," PLOS Computational Biology, Public Library of Science, vol. 6(4), pages 1-13, April.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pcbi00:0030090. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ploscompbiol (email available below). General contact details of provider: https://journals.plos.org/ploscompbiol/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.