Abstract
Transcription factor binding sites (motifs) are crucial in the regulation of the gene transcription. Recently, the chromatin immunoprecipitation followed by cDNA microarray hybridization (ChIP array) have been used to identify potential regulatory sequences, but the procedure can only map the probable protein-DNA interaction loci within 1-2 kilobases resolution. To find out the exact binding motifs, it is necessary to build a computational method to examine the ChIP-array binding sequences and search for possible motifs representing the transcription factor binding sites. In this thesis, we design a program to find out accurate motif sites in the yeast genome with dependency graphs and their expanded Bayesian networks. The program incorporates with the binomial probability model to build significant initial motif sets. Finally, we compare our results with those obtained from famous programs and show that our program outperforms these program in the consistence with known specificities.