One of the most challenging open problems of the post-genomic era for computer scientists, bioinformaticians and molecular biologists is to identify and characterize all the elements involved in the gene regulation, at both the transcriptional and post-transcriptional level. The rapid availability of multiple genomes also necessitates a need for efficient computational solutions to aid in comparative syntenic analysis - the analysis of relative gene-order conservation between species - which can provide key insights into evolutionary chromosomal dynamics, rearrangement rates between species, and speciation analysis. Thus, in this dissertation, we address these issues and develop computational approaches to identify genomic patterns at both micro and macro levels.
To address the problem of gene regulation, we developed algorithms for identifying transcription factor binding sites (short repeated patterns or sequence motifs) in genomes. We have developed a level based search algorithm which is able to identify regulatory motifs in a wide variety of datasets and demonstrate that our method works more efficiently than the current best methods. Further, we have also developed statistical models for identification of known motifs. Finally, we refine the motif discovery process through methods that discriminate and characterize the co-factors of a transcription factor.
At macro level, we developed efficient methods (Cinteny) for fast identification of syntenic blocks with various levels of coarse graining and determine evolutionary relationships between genomes in terms of the number of rearrangements (the reversal distance). Cinteny web server integrates syntenic region browsing with evolutionary distance assessment, offers flexibility to adjust all parameters and recompute the results on-the-fly, and ability to work with user provided data.