臺灣博碩士論文加值系統

調控機制為生命運作中最為複雜的秘密。基本上，調控機制是由轉錄因子與基因的上游區域做結合，進而控制基因表現而引響生物體的生命運作。我們再此提出另一種模擬的模型來呈現多個轉錄因子之間的交互作用，與之前的研究不同的是，我們不但考慮結合區域的一致性，也加入了機率模型來描述不同轉錄因子交互作用時其之間的間距。利用貝氏架構的推論，我們將結合區域的一致性以及其之間間距的兩大考量做結合。我們將此演算法，SAMLA，測試大腸桿菌上的資料，並與其他的演算法作比較，可以發現 SAMLA 的確能更加精準的預測大腸桿菌中的調控模組。

One of the keys to deciphering the secrets of life is to understand transcriptional regulation mechanisms. Such mechanisms are typically mediated by the binding of transcription factors to specific upstream or downstream regions of genes, which leads to most recent studies focused on the conservation of binding sites. Unlike current research, we address the importance of the distance between binding sites for the prediction of Regulatory Modules. Based on the Bayesian framework, we present an algorithm, SAMLA (Simulated Annealing for Multiple Local Sequences Alignment), which takes into account the consensus levels of biding sites as well as the relative distance among them. To demonstrate the performance of our new approach, we conducted a comparative study with several current methods. We tested them on the datasets derived from E.coli, and the experimental results show that our method significantly outperforms the others.

Abstract 2
第一章 前言 6
1.1 生物背景 6
1.2 研究動機 10
1.3 研究假設與目標 12
1.4 論文架構 14
第二章 文獻探討 15
2.1 位置比重矩陣（Position Weight Matrix；PWM） 15
2.2 MEME【Bailey and Elkan, 1995】 17
2.3 Gibbs Sampler【Lawrence et. al. 1993】 18
2.4 Dyad Analysis【van Helden et al. 2000】 20
2.5 Bioprospector【Liu et. al. 2001】 22
2.6 SeSiMCMC【Favorov et. al. 2004】 24
2.7 總結 28
第三章 演算法與系統架構 30
3.1 系統流程 30
3.2 調控序列與調控模組模型 32
3.3 核心評分公式 35
3.4 系統核心推演方法 38
3.4.1 模擬退火法 38
3.4.2 核心概觀 39
3.5 系統核心實做與架構 41
第四章 實驗結果與分析 46
4.1 Zn群組調控因子【van Helden et. al. 2000】 46
4.2 大腸桿菌中的雙核心模組 51
4.2.1 Phospho-ArcA【Favorov et. al. 2005】 51
4.2.2 Cyclic AMP Receptor Protein 53
4.2.3 TyrR調控蛋白 58
4.2.4 cpxR調控蛋白 62
4.2.5 narL調控蛋白 66
4.2.7 總結 71
第五章 結論與未來研究方向 74
5.1 結論與討論 74
5.2 未來研究方向 76
參考文獻 77
A. IUPAC對照表 81
B. Precision and Sensitivity 82

1. Agrawed,R. and Srikant,R. (1994) Fast algorithms for mining association rules. Proceedings 199J International Conference VLDB. 487-499.

2. Bailey,T.L. and Elkan,C. (1994) Fitting a mixture model by expectation maximization to discover motifs in biopolymers. Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology. 28-36.

3. Bailey,T.L. and Elkan,C. (1995) Unsupervised learning of multiple motifs in biopolymers using expectation maximization. Mach. Learn., 21, 51.

4. Crooks,G.E., Hon,G., Chandonia,J.M., and Brenner,S.E. (2004) WebLogo: A sequence logo generator. Genome Research, 14, 1188-1190.

5. Day,W.H. and McMorris,F.R. (1993) The computation of consensus patterns in DNA sequence. Math. Comput. Model., 17, 49-52.

6. GuhaThakurta,D. and Stormo,G.D. (2001) Identifying target sites for cooperatively binding factors. Bioinformatics, 17, 608-621.

7. Favorov,A.V., Gelfand,M.S., Gerasimova1,A.V., Ravcheev,D.A., Mironov, A.A., and Makeev,V.J. (2004) A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length. Bioinformatics, 21, 2240-2245.

8. Gusfield. (1997) Algorithms on strings, trees and sequences. Cambridge University Press.

9. Hu,Y., Sandmeyer,S., McLaughlin,C., and Kibler,D. (2000) Combinatorial motif analysis and hypothesis generation on a genomic scale. Bioinformatics, 16, 222-232.

10. Hu,Y. (2003) Finding subtle motifs with variable gaps in unaligned DNA sequences. Computer Methods and Programs in Biomedicine, 70, 11-20.

11. Grayson,J., Bassel-Duby,R., and Williams,R.S. (1998) Collaborative Interactions Between MEF-2 and Sp1 in Muscle-Specific Gene Regulation. Journal of Cellular Biochemistry, 70, 366-375.

12. Jensen,S.T., Liu,X.S., Zhou,Q. and Liu,J.S. (2004). Computational discovery of gene regulatory binding motifs: a Bayesian perspective. Statistical Science 19:188-204.

13. Kirkpatrick,S., Gelatt,Jr., C.D., and Vecchi,M.P.. (1983) Optimization by Simulated Annealing. Science, 220, 671-680.

14. Lawrence,C.E., Altshul,S.F., Boguski,M.S., Liu,J.S., Neuwald,A.F. and Wootton,J.C. (1993) Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science, 262, 208-214.

15. Liu,J.S. (1994) The collapsed Gibbs Sampler in Bayesian computations with applications to a gene regulatory problem. J. Amer. Statist. Assoc. 89, 958-966.

16. Liu,J.S., Neuwald,A.F. and Lawrence,C.E. (1995) Bayesian models for multiple local sequence alignment and Gibbs sampling strategies. J. Amer. Statist. Assoc. 90, 1156-1170.

17. Liu X, Brutlag,D.L., and Liu,J.S. (2001) BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes. Pac Symp Biocomput, 127-38.

18. Mitchell, Tom M.. (1997) Machine Learning. McGraw-Hill.

19. Robison,K., McGuire,A.M., and Church,G.M. (1998) A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K12 genome. Journal of Molecular Biology, 284, 241-254.

20. Sinha,S. and Tompa,M. (2000) A statistical method for finding transcription factor binding sites. In Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, AAAI Press, 344-354.

21. Thijs,G.., Lescot,M., Marchal,K., Rombauts,S., De Moor, B., Rouze, P., and Moreau, Y. (2001) A higher-order background model improves the detection of promoter regulatory elements by Gibbs sampling. Bioinformatics, 17, 1113-1122.

22. Thijs G., Marchal K., Lescot M., Rombauts S., De Moor B., Rouze P., and Moreau Y. (2002) A Gibbs sampling method to detect overrepresented motifs in the upstream regions of coexpressed genes. Journal of Computational Biology, Vol. 9, No. 2: 447-464.

23. van Helden, J., Andre, B, and Collado-Vides, J. (1998) Extracting Regulatory Sites from the Upstream Region of Yeast Genes by Computational Analysis of Oligonucleotide Frequencies. Journal of Molecular Biology, 281, 827-842.

24. van Helden, J., Rios, A. and Collado-Vides, J. (2000) Discovering regulatory elements in non-coding sequences by analysis of spaced dyads. Nucleic Acids Res., 28, 1808-1818.

25. Zhu, J. and Zhang, M.Q. (1999) SCPD: A promoter database of the yeast Saccharomyces cerevisiae. Bioinformatics, 15, 607-611.