Transcriptional Regulatory Elements: Detection and Evolutionary Analysis

A major challenge in life sciences is the understanding of mechanisms that regulate the expression of genes. An important step towards this goal is the ability to identify transcriptional regulatory elements like binding sites for transcription factors. In computational biology, a popular approach for this task is comparative sequence analysis using both distantly as well as closely related species. Although this method has successfully identified conserved regulatory regions, the majority of binding sites can change rapidly even between closely related species. This makes it difficult to detect them using DNA sequences alone. In this thesis, we introduce two new approaches for the detection and evolutionary analysis of transcriptional elements that consider the challenges of binding site turnover. In the first part, we develop a method for detecting homologous motifs in a given set of sequences in order to obtain evidence for evolutionary events and turnover. Based on a detailed theoretical scaffold, we develop a simple, but effective and efficient heuristic for assembling local pairwise sequence alignments into a local multiple sequence alignment. This kind of multiple alignment only contains conserved motifs represented in columns which satisfy the order implied by the underlying sequences. By favoring motifs that are contained in a great range of sequences, our method is additionally able to detect even small conserved motifs. Furthermore, the calculation of the initial local pairwise alignments is generic. This allows the use of fast heuristic methods in case of large data sets while exact alignment programs can be used for small data sets where detailed information is needed. Application to artificial as well as biological data sets demonstrate the capabilities of our algorithm. In the second part, we propose a conceptually simple, but mathematically non-trivial, phenomenological model for the binding site turnover at a genomic locus. The model is based on the assumption that binding sites have a constant rate of origination and a constant decay rate per binding site. The elementary derivation of the transient probability distribution is affirmed by simulations of sequence evolution as well as biological data. Based on the derived distribution, we develop a phenomenological model of binding site number dynamics in order to detect changes in selective constraints acting on transcription factor binding sites. Using a maximum likelihood implementation as well as exploratory data analysis, we show the functionality of the model by identifying functionally important changes in the evolutionary turnover rates on biological data. Each part of this thesis leads to the development of a new program. While Tracker allows the computation of conserved homologous motifs and their representation in a local multiple alignment, Creto determines the evolutionary turnover rates for arbitrary clades of a phylogenetic tree with given binding site numbers at the final taxa. Both software tools are freely available to the scientific community for further research in this important and exciting field