Transcription factors (TFs) play a key role in gene regulation. They interact with specific binding sites or motifs on the DNA sequence and regulate expression of genes downstream of these binding sites. In silico prediction of potential binding of a TF to a binding site is an important task in computational biology. From a statistical point of view, the DNA sequence is a long text consisting of four different letters ('A','C','G', and 'T'). The binding of a TF to the sequence corresponds to the occurence of a word in the sequence, e.g. 'AACCTC'. Hence, word count statistics can be applied to problems such as number of binding sites and distances between binding sites. The major problem in word count statistics are dependencies between sequence positions. These dependencies arise due to possible overlaps of words. So far, exact formulae to compute the count distribution of clustered occurrences only exist based on generating functions. We newly derive a recursive formula and use it to obtain a normal approximation. In fact, a TF does not bind to one single word but allows mismatches and substitutions. This is captured in a statistical model called Position Frequency Matrix (PFM). A PFM assigns a score to each position of the word and letter. If the summed score reaches a certain threshold, the TF is assumed to bind to that sequence region. In fact, one can transform this representation to a set of words which are bound by the TF. Unfortunately, enumeration of the set of words takes exponential costs. In addition, the set of words grows enourmously for longer binding sites (around 500,000 for a binding site of length 15). Hence, word count statistics and its approximations become inefficient and very inaccurate. Therefore, the need for new statistics and efficient algorithms arises. Instead of enumerating all words, we use a statistical representation - the PFM - and model dependencies explicitly. In fact, probabilities for overlaps are dependencies of the summed scores between two positions. Hence, we reduce the problem to computing the two dimensional convolution of the score distributions for each possible overlap and derive an exact formula for the variance of PFM counts. Furthermore, we found an accurate approximation for the distribution of the number of occurrences using a compound Poisson distribution. Our approximation outperforms all alternative approaches. In addition, we give Poisson statistics for the number of occurrences without overlaps such that other standard word count statistics (like distances between occurences) can be applied. Third, we develop statistics to compute the significance of co- occurrences and co-operativity among sets of TFs. Fourth, we use the variance to define a natural measure of similarity between DNA motifs. We explicitly state formulae for PFMs. Compared to standard approaches, it shows higher correlation with empirical data. It also allows to cluster sets of TFs and gives results comparable with more sophisticated clustering algorithms. Finally, we use this similarity measure to compute the representation quality of PFMs for a set of experimentally verified binding sites. Besides a threshold optimization method which significantly improves the quality of PFMs in Transfac and Jaspar, we can indeed select DNA motifs, which violate PFM assumptions and, therefore, cannot be reasonbly represented as PFMs.
Transkriptionsfaktoren (TF) spielen eine entscheidende Rolle in der Regulation von Genen. Sie interagieren mit spezifischen Bindestellen oder Motifen auf der DNA Sequenz. Daher ist eine wichtige Aufgabe der Bioinformatik, potentielle Bindestellen von TF in silico vorherzusagen. Nimmt man einen statistischen Standpunkt ein, dann ist die DNA Sequenz ein langer Text bestehend aus vier verschiedenen Buchstaben 'A', 'C', 'G' und 'T' für die vier verschiedenen Basen. Bindet ein TF an eine Bindestelle, so ist dies gleichbedeutend damit, dass das Wort, welches die Bindestelle beschreibt, in dem Text vorkommt. Daher kann man für verschiedene Statistiken auf schon bekannte zurückgreifen und somit Fragen nach der Wahrscheinlichkeit eine bestimmte Anzahl von Wörtern zu beobachten oder der Distanz zwischen zwei Vorkommen beantworten. Jedoch tritt bei der Herleitung solcher Statistiken immer wieder das gleiche Problem auf: Die Wörter können überlappen. Daher entstehen Abhängigkeiten zwischen den zugrunde liegenden Zufallsvariablen. Dadurch gibts es z.B. bisher noch keine exakte Formel - die nicht auf erzeugenden Funktionen beruht - zum Berechnen der Wahrscheinlichkeit eine bestimmte Anzahl von nicht-überlappenden Wörtern zu sehen. Wir leiten diese Formel her und erhalten dadurch auch eine Normalverteilungs-Approximation. Leider bindet ein TF aber nicht nur ein an einzelnes Wort, sondern normalerweise gibt es innerhalb des Wortes Position, die Variationen zu lassen. Daher werden TF meist in dem statistischen Modell PFM dargestellt. Dieses Modell weist jedem Buchstaben auf jeder Position ein Gewicht zu. Wenn die Summe aller Gewichte für eine gegebene Sequenz der Länge des Motifs einen Schwellenwert übersteigt, so ist diese Sequenz eine Bindestelle. Daher kann man auch alle derartigen Wörter aufzählen und erhält so eine Menge von Wörtern, die ein Motif beschreibt. Allerding kann diese Menge sehr gross werden. Z.B. für ein Motif der Länge 15 ist die Anzahl normalerweise um die 500.000. Abgesehen davon, dass das Aufzählen der Wörter exponentielle Laufzeit hat, kommen auch die bekannten Statistiken bei einer so grossen Anzahl von Wörtern an ihre Grenzen. Das heisst, sie sind nur sehr aufwändig zu berechnen und die Näherungsergebnisse sind nicht sehr genau. Daher werden neue Statistiken und effiziente Algorithmen benötigt. Wir haben solche Statistiken entwickelt. Dabei nutzen wir aus, dass wir die Wahrscheinlichkeit für überlappende Bindestellen ausrechnen können ohne die Wörter aufzuzählen. Genauer gesagt, benutzen wir das PFM Modell um eine zwei- dimensionale Gewichtsverteilung zu berechnen. Von dieser können wir besagte Wahrscheinlichkeit ablesen. Von diesem Ergebnis ausgehend, leiten wir die exakte Varianz der Anzahl von Vorkommen her. Ausserdem können wir die Verteilung der Vorkommen durch eine zusammengesetzte Poisson Verteilung beschreiben. Simulationen zeigen, dass dies die beste bekannte Approximation ist. Auch können wir für nicht überlappende Vorkommen entsprechende Statistiken auf Basis einer Poisson Verteilung berechnen. Erweiterung auf mehrere verschiedene DNA Motife führt zur Berechnung der Signifikanz von gemeinsamen Vorkommen und der Kooperation von TF. Zusätzlich führen wir die Kovarianz als Maß für die Ähnlichkeit von DNA Motifen ein. Dadurch erhalten wir ein natürliches und vor allem generelles Ähnlichkeitsmaß, das nicht von einem speziellen Modell ausgeht. Explizite Formeln leiten wir für das PFM Modell her und Vergleich mit Simulationen und anderen Maßen zeigt, dass unser Maß tatsächlich die von uns definierte Ähnlichkeit am Besten wiedergibt. Ein verwandtes Maß verwenden wir zum Gruppieren von Klassen von TF. Auch hier zeigt ein Vergleich mit optimierten Gruppierungsalgorithmen, dass wir vergleichbar gute Ergebnisse erhalten. Schließlich nutzen wir die Ähnlichkeit, um herauszufinden, wie gut ein DNA Motif mit einem bestimmten Modell dargestellt werden kann. Hierfür berechnen wir die Kovarianz zwischen den experimentell verifizierten Sequenzen und dem Modell. Dies entspricht der Representations-Qualität von DNA Motif Modellen. Wiederum leiten wir für PFMs explizite Formeln her. Darauf basierend zeigen wir, dass die Qualität auch dafür genutzt werden kann, Modellparameter (in unserem Fall der Schwellenwert) zu optimieren. Außerdem zeigen wir, dass die Qualität für Motife, die den Annahmen des PFM Modells nicht entsprechen, auch signifikant niedriger ist.
