Bioinformatics Advance Access originally published online on January 2, 2008
Bioinformatics 2008 24(3):350-357; doi:10.1093/bioinformatics/btm610
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Natural similarity measures between position frequency matrices with an application to clustering
1Computational Biology, Max Planck Institute f. Molecular Genetics, Ihnestr. 73, 14195 Berlin, 2Mathematics and Computer Science, Free University of Berlin, Takustr. 9, 14195 Berlin, 3COMET group, Genome Informatics, Universität Bielefeld, 33594 Bielefeld and 4Bioinformatics for High-Throughput Technologies, Computer Science 11, Dortmund University, 44221 Dortmund, Germany
*To whom correspondence should be addressed.
 |
Abstract |
|---|
Motivation: Transcription factors (TFs) play a key role in gene regulation by binding to target sequences. In silico prediction of potential binding of a TF to a binding site is a well-studied problem in computational biology. The binding sites for one TF are represented by a position frequency matrix (PFM). The discovery of new PFMs requires the comparison to known PFMs to avoid redundancies. In general, two PFMs are similar if they occur at overlapping positions under a null model. Still, most existing methods compute similarity according to probabilistic distances of the PFMs. Here we propose a natural similarity measure based on the asymptotic covariance between the number of PFM hits incorporating both strands. Furthermore, we introduce a second measure based on the same idea to cluster a set of the Jaspar PFMs.
Results: We show that the asymptotic covariance can be efficiently computed by a two dimensional convolution of the score distributions. The asymptotic covariance approach shows strong correlation with simulated data. It outperforms three alternative methods. The Jaspar clustering yields distinct groups of TFs of the same class. Furthermore, a representative PFM is given for each class. In contrast to most other clustering methods, PFMs with low similarity automatically remain singletons.
Availability: A website to compute the similarity and to perform clustering, the source code and Supplementary Material are available at http://mosta.molgen.mpg.de
Contact: utz.pape{at}molgen.mpg.de
Supplementary information: Supplementary data are available at Bioinformatics online.
Associate Editor: Alfonso Valenica
Received on August 30, 2007; revised on December 5, 2007; accepted on December 6, 2007
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  S. Zhang, M. Xu, S. Li, and Z. Su Genome-wide de novo prediction of cis-regulatory binding sites in prokaryotes Nucleic Acids Res., June 1, 2009; 37(10): e72 - e72. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Nishida, M. C. Frith, and K. Nakai Pseudocounts for transcription factor binding sites Nucleic Acids Res., February 1, 2009; 37(3): 939 - 944. [Abstract] [Full Text] [PDF]
|
|