Elucidating the mechanisms of transcriptional regulation relies heavily on the sequence annotation of the binding sites of DNA-binding proteins called transcription factors. With the rationale that binding sites conserved across different species are more likely to be functional, the standard approach is to employ cross-species comparisons and focus the search to conserved regions. Usually, computational methods that annotate conserved binding sites perform the alignment and binding site annotation steps separately and combine the results in the end. If the binding site descriptions are weak or the sequence similarity is low, the local gap structure of the alignment poses a problem in detecting the conserved sites. In this thesis, I introduce a novel method that integrates the two axes of sequence conservation and binding site annotation in a simultaneous approach yielding \emph{annotated alignments} -- pairwise alignments with parts annotated as putative conserved transcription factor binding sites. Standard pairwise alignments are extended to include additional states for binding site profiles. A statistical framework that estimates profile-related parameters based on desired type I and type II errors is prescribed. This forms the core of the tool {\bf{SimAnn}}. As an extension, I use existing probabilistic models to demonstrate how the framework can be adapted to consider position-specific evolutionary characteristics of binding sites during parameter estimation. This underlies the tool {\bf{eSimAnn}}. Through simulations and real data analysis, I study the influence of considering a simultaneous approach as opposed to a multi-step one on resulting predictions. The former enables a local rearrangement in the alignment structure to bring forth perfectly aligned binding sites. This precludes the necessity of adopting post-processing steps to handle errors in pre-computed alignments, as is usually done in multi-step approaches. Additionally, the framework for parameter estimation is applicable to any novel profile of interest. Especially for instances with poor sequence conservation or profile quality, the simultaneous approach stands out. As a by-product of the analysis, I also present a formulation of the annotated alignment problem as an extended pair Hidden Markov Model and illustrate the correspondence between the various theoretical concepts.
Ansaetze, die das bessere Verstaendnis von Mechanismen transkriptioneller Regulation zum Ziel haben, bauen oft auf der Annotation der Genomsequenz bezueglich DNA Bindestellen von Transkriptionsfaktoren (TFBS) auf. Dies ist auch das Thema der vorliegenden Arbeit. Von grossem Interesse sind Bindestellen, die zwischen zwei oder mehr Spezies erhalten sind. Dem liegt die Hypothese zugrunde, dass diesen mit groesserer Wahrscheinlichkeit eine biologische Funktion zukommt. Gewoehnlich findet man solche Bindestellen mit Hilfe von Computermethoden, die einen separaten Alignment- und Annotationsschritt durchfuehren. Ist die Beschreibung der Bindestelle nicht sehr spezifisch, oder sind sich die zu annotierenden Sequenzen sich nicht besonders aehnlich, so bereitet die lokale Gapstruktur im Alignment Probleme beim Auffinden konservierter Bindestellen. In dieser Arbeit stellen wir neue Methoden vor, die Sequenzalignment und -annotation simultan ausfuehren und deren Endergebnis annotierte Alignments - paarweise Sequenzalignments mit als TFBS annotierten Teilsequenzen - sind. Diesbezueglich wurde der Standardansatz paarweiser Alignments dahingehend erweitert, dass nun zusaetzliche Zustaende fuer TFBS beschreibende Profile moeglich sind. Wir entwickeln statistische Methoden, die das Schaetzten dem Profil assoziierter algorithmischer Parameter mit kontrollierten Fehlern erster oder zweiter Art erlauben. Zusammengenommen ergibt dies den Kern unseres Tools SimAnn. Zusaetzlich zeigen wir, wie die von uns entwickelten Methoden ergaenzt werden koennen, so dass den evolutionaeren Charakteristika der TFBS Rechnung getragen wird. Dies wird in dem Tool eSimAnn zusammengefasst. Wir zeigen den Effekt eines simultanen Zugangs zu Alignment und TFBS Annotation im Kontrast zu Verfahren auf, die mehrere sequenzielle Schritte durchfuehren. Dazu fuehren wir Simulationsstudien durch und vergleichen Resultate auf realen Sequenzdatensaetzen. Ein simultaner Zugang erlaubt es Gaps im Alignment automatisch lokal so zu positionieren, dass die Struktur perfekt alignierter TFBS hervorgehoben wird. Dies macht ein Entfernen von Alignmentfehlern, wie es bei sequenziellen Verfahren ueblich ist, unnoetig. Als besonders vorteilhaft stellt sich dies fuer Sequenzen mit nur maessiger Konservierung und fuer Transkriptionsfaktoren mit mittlerer Profilqualitaet heraus. Unsere Analyse beinhaltet die Modellierung des Problems annotierter Alignments als ein extended pair Hidden Markov Model und zeigt Verbindungen und Zusammenhaenge verschiedener theoretischer Konzepte auf. Die Arbeit ist wie folgt strukturiert: Kapitel 1 und 2 fuehren in die grundlegenden Konzepte und Methoden ein, die im Weiteren benoetigt werden. Kapitel 1 gibt einen ueberblick ueber aktuelle Methoden, sowohl experimentell als auch in silico. In Kapitel 2 diskutieren wir formale Aspekte, die sowohl TFBS Profilen als auch Alignments zugrunde liegen. Annotierte Alignments werden in Kapitel 3 vorgestellt. Als erstes wird ein erweiterter Algorithmus aus der klasse der dynamischen Programmierung beschrieben, mit dem sich annotierte Alignments erstellen lassen. Danach stellen wir zwei Methoden zum Schaetzen Profil assoziierter Parameter vor. Erst werden die DNA Bindestellen von Transkriptionsfaktoren in beiden Sequenzen unabhaengig behandelt; danach wird mit Hilfe von positionsspezifischen evolutionaeren Modellen der Abhaengigkeit zwischen Bindestellen explizit Rechnung getragen. Im Weiteren formulieren wir Annotierte Alignments als extended pair Hidden Markov Model und schliessen mit einer Laufzeitanalyse des vorgestellten Algorithmus. In Kapitel 4 untersuchen wir verschiedene Aspekte unsres Ansatzes. Wir untermauern unseren statistischen Ansatz zur Parameterwahl aus Kapitel 3 mit Simulationen. Mit Simulierten und realen Daten kontrastieren wir unseren simultanen Ansatz gegenueber sequenziellen mehrschrittigen Strategien. Wir betrachten sowohl den Einfluss evolutionaerer Distanz als auch den der Qualitaet des TFBS Profils. Schlussendlich wird in Kapitel 5 eine Zusammenfassung gegeben. Zusaetzlich werden Perspektiven fuer zukuenftige Forschung aufgezeigt, denen hier beschriebene Methoden zugrunde liegen.
