本文選題：RNA二級結(jié)構(gòu)　切入點：假結(jié)　出處：《南京航空航天大學》2017年碩士論文

【摘要】：核糖核苷酸(ribonucleic acid,RNA)作為一類生物大分子,在各種細胞生命過程中扮演著重要的角色,包括遺傳信息的表達、傳遞、基因調(diào)控與催化等。與DNA不同,RNA的結(jié)構(gòu)更加復雜多樣,這也是RNA具有豐富功能特性的物質(zhì)基礎(chǔ)。首先由于物理實驗方法檢測RNA空間結(jié)構(gòu)成本較高,其次,僅依靠物理實驗無法滿足海量的待測序列數(shù)據(jù)。因此RNA二級結(jié)構(gòu)的算法模擬預(yù)測成為一個重要且具有挑戰(zhàn)性的課題。并且,在RNA二級結(jié)構(gòu)中有一類由莖區(qū)交叉嵌套產(chǎn)生的子結(jié)構(gòu)叫做假結(jié),由于假結(jié)被證實在很多RNA催化過程中起到關(guān)鍵的作用,因此近期在RNA結(jié)構(gòu)預(yù)測領(lǐng)域越來越受到重視。本文將遺傳算法應(yīng)用到RNA二級結(jié)構(gòu)預(yù)測當中,并且包含了兩類假結(jié)結(jié)構(gòu),并通過實驗測試,驗證算法的可用性與有效性。其次針對RNA結(jié)構(gòu)預(yù)測的效率問題,提出基于OpenCL的異構(gòu)并行加速,對串行算法進行改進和優(yōu)化,分析串行預(yù)測算法中可并行的部分,對計算任務(wù)進行重新劃分,通過CPU+GPU模式進行異構(gòu)加速,最終通過實驗測試對比串行算法與并行算法效率的高低。論文主要工作如下:(1)實現(xiàn)一種改進的遺傳算法,相對于傳統(tǒng)的遺傳算法,改進了遺傳操作,使得預(yù)測算法更加接近RNA分子二級結(jié)構(gòu)的折疊過程。算法基于最小自由能思想,結(jié)合MathewsTurner和DirksPierce兩種能量參數(shù),預(yù)測包含H型假結(jié)在內(nèi)的兩種假結(jié)結(jié)構(gòu)。最終從RNA STRAND數(shù)據(jù)庫中選取的測試集測試獲得0.81的陽性預(yù)測率、0.79的敏感性。說明算法有效可用,可以作為RNA二級結(jié)構(gòu)分析的參考之一。(2)針對基于遺傳算法帶假結(jié)的RNA二級結(jié)構(gòu)預(yù)測低效的問題,提出基于Open CL的異構(gòu)并行加速算法,首先進行上述串行算法的并行性分析,得到在螺旋區(qū)點陣填充及種群迭代進化兩個最耗時的階段可以進行異構(gòu)加速,然后改進算法過程,在GPU設(shè)備上基于Open CL編程框架對上述兩個過程進行改進和提升。最終以相同的測試集進行測試,相對于串行算法,改進后的異構(gòu)并行加速算法平均可獲得2.8x倍的加速。有效降低了RNA二級結(jié)構(gòu)預(yù)測的耗時,提升了算法模擬預(yù)測的效率。
[Abstract]:Ribonucleic acid RNA (RNAs), as a class of biological macromolecules, plays an important role in the process of cell life, including the expression, transmission, regulation and catalysis of genetic information. This is also the material basis for the rich functional characteristics of RNA. Firstly, because of the high cost of physical experimental method to detect RNA spatial structure, secondly, Relying on physical experiments alone can not satisfy the mass of data to be tested, so the algorithm simulation and prediction of RNA secondary structure has become an important and challenging topic. In the secondary structure of RNA, a class of substructures generated by cross-nesting of stem region is called pseudoknot, which has been proved to play a key role in many RNA catalytic processes. Therefore, more and more attention has been paid to the field of RNA structure prediction recently. In this paper, genetic algorithm is applied to RNA secondary structure prediction, and two kinds of false junction structures are included. Secondly, aiming at the efficiency problem of RNA structure prediction, this paper proposes a heterogeneous parallel acceleration based on OpenCL, improves and optimizes the serial algorithm, and analyzes the parallelism part of the serial prediction algorithm. This paper redivides the computing tasks, accelerates the isomerism through CPU GPU mode, and finally compares the efficiency of the serial algorithm with the parallel algorithm through experimental tests. The main work of this paper is as follows: 1) to implement an improved genetic algorithm. Compared with the traditional genetic algorithm, the genetic operation is improved, which makes the prediction algorithm more close to the folding process of the secondary structure of RNA molecule. The algorithm is based on the idea of minimum free energy and combines the two energy parameters of MathewsTurner and DirksPierce. Finally, the sensitivity of 0.81 positive prediction rate of 0.79 is obtained from the test set selected from RNA STRAND database. It can be used as one of the reference of RNA secondary structure analysis. (2) aiming at the problem of low efficiency prediction of RNA secondary structure with false junction based on genetic algorithm, a heterogeneous parallel acceleration algorithm based on Open CL is proposed. Firstly, the parallelism of the above serial algorithm is analyzed. It is concluded that the two most time-consuming stages of helical lattice filling and population iterative evolution can be accelerated by isomerism, and then the algorithm process is improved. The above two processes are improved and upgraded based on the Open CL programming framework on the GPU device. Finally, the same test set is used to test, compared with the serial algorithm, The improved heterogeneous parallel acceleration algorithm can achieve an average acceleration of 2.8 x, which effectively reduces the time consuming of RNA secondary structure prediction and improves the efficiency of the algorithm simulation prediction.
【學位授予單位】：南京航空航天大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：Q522;TP18

【參考文獻】

相關(guān)期刊論文 前6條

1 夏飛;朱強華;金國慶;;基于CPU-GPU混合計算平臺的RNA二級結(jié)構(gòu)預(yù)測算法并行化研究[J];國防科技大學學報;2013年06期

2 夏飛;竇勇;宋健;雷國慶;;基于FPGA的細粒度并行CYK算法加速器設(shè)計與實現(xiàn)[J];計算機學報;2010年05期

3 董犖;葛萬成;陳康力;;CUDA并行計算的應(yīng)用研究[J];信息技術(shù);2010年04期

4 陳國良;孫廣中;徐云;龍柏;;并行計算的一體化研究現(xiàn)狀與發(fā)展趨勢[J];科學通報;2009年08期

5 劉元寧;張浩;李妼;崔廣迪;苗軼蟬;;RNA假結(jié)結(jié)構(gòu)分析[J];吉林大學學報(工學版);2009年S1期

6 鄒權(quán);郭茂祖;張濤濤;;RNA二級結(jié)構(gòu)預(yù)測方法綜述[J];電子學報;2008年02期

相關(guān)博士學位論文 前3條

1 劉琦;RNA二級結(jié)構(gòu)的若干計算生物學問題研究[D];浙江大學;2008年

2 方小永;基于比較序列分析的RNA二級結(jié)構(gòu)預(yù)測與評估[D];國防科學技術(shù)大學;2007年

3 劉海軍;RNA二級結(jié)構(gòu)預(yù)測的建模及其應(yīng)用研究[D];上海大學;2005年

相關(guān)碩士學位論文 前5條

1 趙成龍;基于AMD平臺的OpenCL優(yōu)化研究及其在分子動力學中的應(yīng)用[D];南京航空航天大學;2015年

2 吳蘭;基于HSA的Kaveri測試與優(yōu)化[D];蘇州大學;2014年

3 苑寅;帶假結(jié)RNA二級結(jié)構(gòu)預(yù)測研究[D];電子科技大學;2013年

4 彭政;帶假結(jié)的RNA二級結(jié)構(gòu)預(yù)測算法研究[D];湖南大學;2008年

5 張濤濤;基于比較序列分析的RNA二級結(jié)構(gòu)預(yù)測算法研究[D];哈爾濱工業(yè)大學;2007年

，

本文編號：1672494