臺灣博碩士論文加值系統

真核生物在遺傳資訊核糖核酸實際轉譯成蛋白質之前，可能受環境、序列上的特定二級結構、特定部分序列樣式……等影響，而製造出目的、功能不同的蛋白質，這項生物機制稱為選擇性接合。目前對於選擇性接合機制的形成原因、根據何項資訊作選擇性調控，尚未有全面性的研究足以判斷。本研究嘗試透過發展適當的資料探勘技術，分析大量核糖核酸序列，找出可能影響選擇性接合的序列樣式。
選擇性接合可分為七種類型，我們針對其中一類稱為跳接式選擇性接合的基因資料，根據分析該資料的特性，提出兩類型的容錯資料探勘方法與流程，分別是全序列樣式探勘與轉化重複結構樣式探勘。前者對發生跳接式選擇性接合的整段intron序列，找出所有容錯頻繁樣式。再利用Kum[18]等人提出的一致性序列樣式的近似探勘方法，找出足以代表同一群聚中所有頻繁容錯樣式的一致性序列樣式。
轉化重複結構樣式探勘的作法則是先找出intron序列的前後部分區段中，可能具有容錯轉化重複樣式的序列集合。再進行容錯頻繁樣式探勘與一致性序列樣式的近似探勘方法。由於轉化重複樣式是生物序列中常見的一種序列結構，可能透過該類型結構，影響跳接式選擇性接合的發生方式。因此利用這樣的探勘方法，我們可以找到可能的具重要決定性轉化重複結構樣式。
最後，我們對兩個選擇性接合資料集合Avatar-120和ISIS-54，進行全序列樣式探勘與轉化重複結構樣式探勘實驗，討論發掘出序列樣式的支持度及平均錯誤率。並進一步與Miriami[24]等人研究發表的兩個樣式比較，利用整體序列最佳並列排比，評估樣式間的差異性，以發掘出“新穎”的樣式。

Before RNA sequences are translated into proteins, eukaryotes may produce different functional proteins from the same RNA sequences. It is due to influence of environment, second structure, specific substring pattern, etc. This mechanism is named alternative splicing. At present, there are still not enough research to judge causes and critical information of alternative splicing. We try to develop suitable data mining technologies to analyze large number of RNA sequences, and find out possible patterns affecting alternative splicing.
Basically, there are seven possible types of alternative splicing. We focus on “exon skipping” type. According to the analysis of exon skipping data, we propose two fault-tolerant data mining methods and procedures: “Full Sequence Pattern Mining (FSPM)” and “Inverted Repeat Pattern Mining (IRPM).” Full sequence pattern mining method can be applied to mine all fault-tolerant frequent substrings in the whole intron sequences, and then get consensus sequential patterns using ApproxMap method proposed by Kum[18].
Inverted repeat pattern mining method can be used to look for consenesus patterns with structure of inverted repeat. Because inverted repeat patterns are often appeared in biological sequences and such structural patterns may result in exon skipping. We could discover some important patterns by this method.
Finally, we mined patterns from two alternative splicing databsets “Avatar-120” and “ISIS-54”by above two proposed methods. The support and average fault number of mined patterns were discussed. These patterns were also used global alignment method as compared with two patterns (C / G-rich) discovered by Miriami[24]. Novel patterns measured by discrimination were reported.

第一章 導論 1
1.1 研究動機 1
1.2 研究目的 3
1.3 論文架構 4
第二章 相關研究 5
2.1 生物選擇性接合機制 5
2.1.1 生物遺傳法則 5
2.1.2 接合機制運作與選擇性接合調控 7
2.2 選擇性接合資料庫 12
2.3 資料探勘 20
2.3.1 頻繁樣式探勘 21
2.3.2 循序探勘 21
2.3.3 容錯序列資料探勘 22
2.4 選擇性接合樣式分析 22
第三章 選擇性接合資料庫容錯序列探勘 25
3.1 容錯轉化重複樣式探勘（fault-tolerant inverted repeat pattern mining） 27
3.1.1 容錯轉化重複樣式問題定義 27
3.1.2 容錯轉化重複樣式探勘演算法 28
3.2 容錯序列探勘（fault-tolerant sequence mining） 32
3.2.1 容錯序列探勘問題定義 34
3.2.2 容錯序列探勘演算法 36
3.3 一致性序列樣式的近似探勘（approximate mining of consensus sequential patterns） 38
3.3.1 一致性序列樣式的近似探勘問題定義 39
3.3.2 一致性序列樣式的近似探勘演算法 39
第四章 實驗與結果分析 46
4.1 資料來源 46
4.1.1 對Avatar資料庫來源使用的過濾條件 47
4.1.2 對ISIS 資料庫來源使用的過濾條件 47
4.2 系統架構與實作 48
4.2.1 系統架構 48
4.2.2 系統實作及參數 49
4.3 實驗結果及分析 52
4.3.1 全序列樣式探勘（FSPM）與轉化重複結構樣式探勘（IRPM）結果 52
4.3.2 與Miriami[24]等學者研究所得樣式的比較 68
第五章 結論與未來研究方向 86
5.1 結論 86
5.2 未來研究方向 87
參考文獻 88
附錄 一 91

[1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of International Conference on Very Large Databases (VLDB’94), 1994.
[2] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proc. of the 11th International Conference on Data Engineering (ICDE’95), 1995.
[3] B. Brejova, et al., “Finding Patterns in Biological Sequences,” Technical Report CS-2000-22, University of Waterloo, 2000.
[4] M. Burset, I. A. Seledtsov, and V. V. Solovyev, “SpliceDB: Database of Canonical and Non-canonical Mammalian Splice Sites,” Nucleic Acids Research, Vol.29, No.1, 2000.
[5] F. H. C. Crick, “The Biological Replication of Macromolecules,” Symposia of the Society for Experimental Biology, 1958.
[6] L. Croft, S. Schandorff, F. Clark, K. Burrage, P. Arctander, and J. S. Mattick, “ISIS, the Intron Information System, Reveals the High Frequency of Alternative Splicing in the Human Genome,” Nature Genetics, Vol. 24, 2000.
[7] I. Dralyuk, M. Brudno, M.S. Gelfand, M. Zorn, and I. Dubchak, “ASDB: Database of Alternatively Spliced Genes,” Nucleic Acids Research, Vol.28, No.1, 2000.
[8] D. Fisher, “Improving Inference through Conceptual Clustering,” Proc. of AAAI’87, 1987.
[9] J. D. Glasner, P. Liss, G. Plunkett III, A. Darling, T. Prasad, M. Rusch, A. Byrnes, M. Gilson, B. Biehl, F. R. Blattner, and N. T. Perna, “ASAP, a systematic annotation package for community analysis of genomes,” Nucleic Acids Research, Vol.31, No.1, 2003.
[10] P. J. Grabowski, R. A. Padgett, and P. A. Sharp, “Messenger RNA Splicing in Vitro: an Excised Intervening Sequence and a Potential Intermediate,” Cell, Vol. 37, No. 2, 1984.
[11] F. R. Hsu and J. F. Chen, “Aligning ESTs to Genome Using Multi-Layer Unique Markers”, Proc. of 2003 IEEE Computer Society Bioinformatics Conference (CSB’03), 2003.
[12] F. R. Hsu, M. Y. Shi, and J. H. Liu, “Avatar: a Value Added Transcriptome,” Proc. of the 6th Conference on Engineering Technology and Chinese/Western Medicine Applications, 2003.
[13] F. R. Hsu, et al., “Genome-Wide Alternative Splicing Events Detection through Analysis of Large Scale ESTs,” Proc. of the 4th IEEE Symposium on Bioinformatics and Bio- engineering (BIBE'04), 2004.
[14] F. R. Hsu, et al., "AVATAR: A database for genome-wide alternative splicing event detection using large scale ESTs and mRNAs," Bioinformation, Vol.1, No.1, 2005.
[15] Y. H. Huang, J. J. Chen, S. T. Yang, U. C. Yang, “PALS db: Putative Alternative Splicing Database,” Nucleic Acids Research, Vol. 30, No.1, 2002.
[16] H. Ji, Q. Zhou, F. Wen, H. Xia, X. Lu, Y. Li, “AsMamDB: An Alternative Splice Database of Mammals,” Nucleic Acids Research, Vol.29, No.1, 2001.
[17] E. M. Knorr and R. T. Ng, “Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining,” IEEE Transaction on Knowledge and Data Engineering, Vol. 8, No. 6, 1996.
[18] H.C. Kum, J. Pei, W. Wang, and D. Duncan, “ApproxMAP: Approximate Mining of Consensus Sequential Patterns,” Proc. of SIAM International Conference on Data Mining (SDM’03), 2003.
[19] A. N. Ladd and T. A. Cooper, “Finding Signals that Regulate Alternative Splicing in the Post-genomic era,” Genome Biology, Vol.3, No. 11, 2002.
[20] C. Lee, L. Atanelov, B. Modrek, and Y. Xing, “ASAP: The Alternative Splicing Annotation Project,” Nucleic Acids Research, Vol. 31, No.1, 2003.
[21] B. Liu, W. Hsu, and Y. Ma, “Integrating Classification and Association Rule Mining,” Proc. of ACM International Conference on Knowledge Discovery and Data Mining (KDD’98), 1998.
[22] N. Matter, P. Herrlich, and H. Konig, “Signal-dependent Regulation of Splicing via Phosphorylation of Sam68,” Nature, Vol. 420, No. 6916, 2003.
[23] H. Miyaso, M. Okumura, S. Kondo, S. Higashide, H. Miyajima, and K. Imaizumi, “An Intronic Splicing Enhancer Element in SMN Pre-mRNA,” Journal of Biological Chemistry, Vol. 278, No. 18, 2003
[24] E. Miriami, H Margalit, and R. Sperling, “Conserved Sequence Elements Associated With Exon Skipping,” Nucleic Acid Research, Vol. 31, No.7, 2003.
[25] A. A. Mironov, J. W. Fickett, and M. S. Gelfand, “Frequent Alternatice Splicing of Human Genes,” Genome Research, Vol. 9, 1999.
[26] B. Modrek, A. Resch, C. Grasso, and C. Lee, “Genome-wide Detection of Alternative Splicing in Expressed Sequences of Human Genes,” Nucleic Acids Research, Vol. 29, No. 13, 2001.
[27] B. Modrek and C. Lee. “A Genomic View of Alternative Splicing,” Nature Genetics, Vol. 30, No. 1, 2002.
[28] R. T. Ng and J. Han, “Efficient and Effective Clustering Methods for Spatial Data Mining,” Proc. of International Conference on Very Large Databases (VLDB’94), 1994.
[29] R. A. Padgett, M. M. Konarska, P. J. Grabowski, S. F. Hardy, and P. A. Sharp, “Lariat RNA's as Intermediates and Products in the Splicing of Messenger RNA Precursors,” Science, Vol. 225, No. 4665, 1984.
[30] I. Pei, J. W. Han, B. Mortazavi-asl, and H. Zhu, “Mining Access Patterns Efficiently from Web Logs,” Proc. of Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’00), 2000.
[31] J. Pei, A. K. H. Tung, and J. W. Han, “Fault-Tolerant Frequent Pattern Mining: Poblems and Challenges,” Proc. of Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD’01), 2001.
[32] P. Rice, I. Longden, and A. Bleasby, “EMBOSS: The European Molecular Biology Open Software Suite,” Trends in Genetics, Vol. 16, No. 6, 2000.
[33] T. A. Thanaraj, S. Stamm, F. Clark, J. J. Riethoven, V. Le Texier, J. Muilu, “ASD: the Alternative Splicing Database,” Nucleic Acids Research, Vol. 32, No. 1, 2004.