核醣核酸二級結構預測 - 使用基因規劃

Abstract

核醣核酸二級結構預測 – 使用基因規劃 研究生：陳兆奕 指導教授：胡毓志博士 國立交通大學資訊科學研究所 摘要 本研究嘗試以基因規劃(genetic programming)的方式尋找一組相關核醣核酸序列(related RNA sequences)裡的共同二級結構(common secondary structure)。研究中我們首先提出兩種莖幹的描述方法，並藉由對莖幹的描述，在程式的第一個步驟中取出所有的候選莖幹(candidate stem)，其中有一些候選莖幹會是共同結構的一個部分。除了莖幹的描述方法之外，本研究另外也提出一種非常彈性的二級結構描述語言，利用此語言來描述任何的核醣核酸二級結構。在程式的第二個步驟中，基因規劃裡的每一個個體(individual)就是一個用此語言所描述的一種共同二級結構，而我們演化的目的就是希望將這些結果最佳化(optimize)。關於基因規劃最重要的適應函數(fitness function)部分，本研究提出一種有別於自由能評估(free energy measure)的方法來評估我們的個體。在測試了包含兩組有擬節(pseudo-knot)結構在內的六個核醣核酸序家族之序列，我們獲得良好的實驗結果。本研究網頁版本的工具GPRM (Genetic Programming for RNA Motifs) 之網址如下：http://bioinfo.cis.nctu.edu.tw/service/gprm/.

RNA Secondary Structure Prediction by Genetic Programming Student：Chao-I Chen Advisor：Yuh-Jyh Hu Institute of Computer and Information Science National Chiao Tung University Hsinchu, Taiwan, Republic of China ABSTRACT In this study we apply genetic programming to a set of related RNA sequences to find their common RNA secondary structures. Our method contains two main procedures. At the first stage, we provide two different stem representations to extract all legal candidate stems on each sequence. Some of these stems are in common secondary structures. Next, genetic programming is used to optimize individuals in population. In this step, each individual representing common secondary structures is described by our structure representation, a flexible representation for all kinds of RNA secondary structures. We also propose a new fitness criterion other than free energy measure to evaluate common secondary structures. We had obtained satisfactory experimental results on six different RNA families including two pseudo-knot data sets. This web-based tool, Genetic Programming for RNA Motifs (GPRM), is available at http://bioinfo.cis.nctu.edu.tw/service/gprm/.