Genome-wide discovery of cis-regulatory RNA motifs and transcriptional regulatory networks

Cis-regulatory RNA structural elements and DNA sequence motifs play important roles in gene regulation. My thesis focuses on developing effective computational approaches based on comparative sequence analysis to systematically identify cis-regulatory RNA structural elements and DNA sequence motifs in bacterial genomes.;To identify cis-regulatory RNA structural elements, I developed two new algorithms, RNA Sampler and RSSVM. RNA Sampler predicts common RNA secondary structure and structural alignment in multiple sequences by iteratively sampling aligned stems and updating base pairing and base alignment probabilities to form converged common structure. It outperforms other leading common RNA structure prediction programs in both sensitivity and specificity with a fast speed. RSSVM is an RNA classifier based on Support Vector Machines, using the structures and alignments generated by RNA Sampler to classify functional RNA structural motifs from random RNA structures. It is more sensitive than other leading programs in identifying functional RNAs while maintaining the same false positive rate, particularly on sets with low sequence identities. I applied RNA Sampler and RSSVM to multiple Shewanella genomes and identified a number of known and novel RNA motifs conserved in the 5' untranslated regions of orthologous genes. A large fraction of the novel predictions are supported by published reports or overlap with other independent predictions.;To identify cis-regulatory DNA sequence motifs in Shewanella genomes, I applied a new comparative genomics pipeline that combines phylogenetic footprinting, motif searching, and motif clustering approaches to predict DNA motifs that are not only conserved across species but also shared by multiple genes. A large numbers of our predictions match known motifs or are supported by literature or other evidence. In addition, I applied the pipeline to differentially expressed genes from microarray experiments and identified DNA motifs specifically involved in metal reduction. This study provides one of the most comprehensive transcriptional regulatory networks in bacteria.;My thesis provides efficient new tools and pipelines for genome-wide identification of cis-regulatory RNA structural elements and DNA sequence motifs. Application of these approaches to Shewanella genomes helps extend our knowledge and deepen our understanding on gene regulation at both transcriptional and post-transcriptional levels in bacteria.