Transcription factors (TFs) play a crucial role in gene regulation by binding to specific regulatory sequences. The sequence motifs recognized by a TF can be described in terms of position frequency matrices. Searching for motif matches with a given position frequency matrix is achieved by employing a predefined score cutoff and subsequently counting the number of matches above this cutoff. In this article, we approximate the distribution of the number of motif matches based on a novel dynamic programming approach, which accounts for higher order sequence background (e.g., as is characteristic for CpG islands) and overlapping motif matches on both DNA strands. A comparison with our previously published compound Poisson approximation and a binomial approximation demonstrates that in particular for relaxed score thresholds, the dynamic programming approach yields more accurate results.
Get full access to this article
View all access options for this article.
References
1.
AlbertsB., JohnsonA., LewisJ., et al.2002. Molecular Biology of the Cell, Fourth Edition. Garland Science, London.
2.
BaileyT.L., BodenM., BuskeF.A., et al.2009. Meme suite: Tools for motif discovery and searching. Nucleic Acids Res gkp335.
3.
BishopC.M. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Berlin, Heidelberg.
4.
CarthariusK., FrechK., GroteK., et al.2005. Matinspector and beyond: Promoter analysis based on transcription factor binding sites. Bioinformatics. 21:2933–2942.
5.
ChenQ.K., HertzG.Z., and StormoG.D.1995. Matrix search 1.0: A computer program that scans dna sequences for transcriptional elements using a database of weight matrices. Comput. Appl. Biosci., 11:563–566.
6.
FrithM.C., FuY., YuL., et al.2004. Detection of functional DNA motifs via statistical over-representation. Nucleic Acids Res. 32:1372–1381.
7.
KarlinS., and TaylorH.E.1981. A Second Course in Stochastic Processes. Academic Press, London, UK.
8.
KoppW., and VingronM.2017. An improved compound poisson model for the number of motif hits in DNA sequences. Bioinformatics, 33:3929–3937.
9.
KulakovskiyI.V., MedvedevaY.A., SchaeferU., et al.2013. Hocomoco: A comprehensive collection of human transcription factor binding sites models. Nucleic Acids Res. 41:D195–D202.
10.
LiN., and TompaM.2006. Analysis of computational approaches for motif discovery. Algorithms Mol. biol. 1:8.
11.
LiuJ.S., and LawrenceC.E.1999. Bayesian inference on biopolymer models. Bioinformatics. 15:38–52.
12.
MarschallT., and RahmannS.2008. Probabilistic arithmetic automata and their application to pattern matching statistics, 95–106. Eds: FerraginaP., and LandauG.M. In Annual Symposium on Combinatorial Pattern Matching. Springer, Berlin-Heidelberg.
13.
MarschallT., and RahmannS.2010. Speeding up exact motif discovery by bounding the expected clump size, 337–349. In International Workshop on Algorithms in Bioinformatics. Springer.
14.
McLeayR.C., and BaileyT.L.2010. Motif enrichment analysis: A unified framework and an evaluation on chip data. BMC Bioinformatics. 11:165.
15.
NeymanJ., and PearsonE.S.1933. The testing of statistical hypotheses in relation to probabilities a priori. Math. Proc. Camb. Philos. Soc. 29:492–510.
16.
PapeU.J., RahmannS., SunF., et al.2008. Compound poisson approximation of the number of occurrences of a position frequency matrix (PFM) on both strands. J. Comput. Biol. 15:547–564.
17.
RahmannS., MüllerT., and VingronM.2003. On the power of profiles for transcription factor binding site detection. Stat. Appl. Genet. Mol. Biol. 2:Article7.
18.
ReinertG., SchbathS., and WatermanM.S.2000. Probabilistic and statistical properties of words: An overview. J. Comput. Biol. 7:1–46.
19.
RoiderH.G., MankeT., O'keeffeS., et al.2009. Pastaa: Identifying transcription factors associated with sets of co-regulated genes. Bioinformatics. 25:435–442.
20.
SandelinA., AlkemaW., EngströmP., et al.2004. Jaspar: An open-access database for eukaryotic transcription factor binding profiles. Nucleic Acids Res. 32:D91–D94.
21.
SchneiderT.D., and StephensR.M.1990. Sequence logos: A new way to display consensus sequences. Nucleic Acids Res. 18:6097–6100.
22.
StormoG.D.2000. DNA binding sites: Representation and discovery. Bioinformatics. 16:16–23.
ThurmanR.E., RynesE., HumbertR., et al.2012. The accessible chromatin landscape of the human genome. Nature. 489:75–82.
25.
TouzetH., and VarréJ.S.2007. Efficient and accurate p-value computation for position weight matrices. Algorithms Mol. Biol. 2:1748–1788.
26.
WingenderE., DietzeP., KarasH., et al.1996. Transfac: A database on transcription factors and their DNA binding sites. Nucleic Acids Res. 24:238–241.
27.
ZambelliF., PesoleG., and PavesiG.2009. Pscan: Finding over-represented transcription factor binding site motifs in sequences from co-regulated or co-expressed genes. Nucleic Acids Res., 37:W247–W252.
28.
ZhangJ., JiangB., LiM., et al.2007. Computing exact p-values for DNA motifs. Bioinformatics. 23:531–537.
