Natural similarity measures between position frequency matrices with an application to clustering.
BACKGROUND
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.


BACKGROUND
A website to compute the similarity and to perform clustering, the source code and Supplementary Material are available at http://mosta.molgen.mpg.de.
Pape
Utz J
UJ
Computational Biology, Max Planck Institute f. Molecular Genetics, Ihnestr. 73, 14195 Berlin, Germany. utz.pape@molgen.mpg.de
Rahmann
Sven
S
Vingron
Martin
M
D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D001665:Binding Sites; D016000:Cluster Analysis; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D011485:Protein Binding; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D014157:Transcription Factors / Q000235:genetics*
D014157:Transcription Factors