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

【摘要】：核糖核苷酸(ribonucleic acid,RNA)作為一類生物大分子,在各種細(xì)胞生命過(guò)程中扮演著重要的角色,包括遺傳信息的表達(dá)、傳遞、基因調(diào)控與催化等。與DNA不同,RNA的結(jié)構(gòu)更加復(fù)雜多樣,這也是RNA具有豐富功能特性的物質(zhì)基礎(chǔ)。首先由于物理實(shí)驗(yàn)方法檢測(cè)RNA空間結(jié)構(gòu)成本較高,其次,僅依靠物理實(shí)驗(yàn)無(wú)法滿足海量的待測(cè)序列數(shù)據(jù)。因此RNA二級(jí)結(jié)構(gòu)的算法模擬預(yù)測(cè)成為一個(gè)重要且具有挑戰(zhàn)性的課題。并且,在RNA二級(jí)結(jié)構(gòu)中有一類由莖區(qū)交叉嵌套產(chǎn)生的子結(jié)構(gòu)叫做假結(jié),由于假結(jié)被證實(shí)在很多RNA催化過(guò)程中起到關(guān)鍵的作用,因此近期在RNA結(jié)構(gòu)預(yù)測(cè)領(lǐng)域越來(lái)越受到重視。本文將遺傳算法應(yīng)用到RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)當(dāng)中,并且包含了兩類假結(jié)結(jié)構(gòu),并通過(guò)實(shí)驗(yàn)測(cè)試,驗(yàn)證算法的可用性與有效性。其次針對(duì)RNA結(jié)構(gòu)預(yù)測(cè)的效率問(wèn)題,提出基于OpenCL的異構(gòu)并行加速,對(duì)串行算法進(jìn)行改進(jìn)和優(yōu)化,分析串行預(yù)測(cè)算法中可并行的部分,對(duì)計(jì)算任務(wù)進(jìn)行重新劃分,通過(guò)CPU+GPU模式進(jìn)行異構(gòu)加速,最終通過(guò)實(shí)驗(yàn)測(cè)試對(duì)比串行算法與并行算法效率的高低。論文主要工作如下:(1)實(shí)現(xiàn)一種改進(jìn)的遺傳算法,相對(duì)于傳統(tǒng)的遺傳算法,改進(jìn)了遺傳操作,使得預(yù)測(cè)算法更加接近RNA分子二級(jí)結(jié)構(gòu)的折疊過(guò)程。算法基于最小自由能思想,結(jié)合MathewsTurner和DirksPierce兩種能量參數(shù),預(yù)測(cè)包含H型假結(jié)在內(nèi)的兩種假結(jié)結(jié)構(gòu)。最終從RNA STRAND數(shù)據(jù)庫(kù)中選取的測(cè)試集測(cè)試獲得0.81的陽(yáng)性預(yù)測(cè)率、0.79的敏感性。說(shuō)明算法有效可用,可以作為RNA二級(jí)結(jié)構(gòu)分析的參考之一。(2)針對(duì)基于遺傳算法帶假結(jié)的RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)低效的問(wèn)題,提出基于Open CL的異構(gòu)并行加速算法,首先進(jìn)行上述串行算法的并行性分析,得到在螺旋區(qū)點(diǎn)陣填充及種群迭代進(jìn)化兩個(gè)最耗時(shí)的階段可以進(jìn)行異構(gòu)加速,然后改進(jìn)算法過(guò)程,在GPU設(shè)備上基于Open CL編程框架對(duì)上述兩個(gè)過(guò)程進(jìn)行改進(jìn)和提升。最終以相同的測(cè)試集進(jìn)行測(cè)試,相對(duì)于串行算法,改進(jìn)后的異構(gòu)并行加速算法平均可獲得2.8x倍的加速。有效降低了RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)的耗時(shí),提升了算法模擬預(yù)測(cè)的效率。
[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.
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：Q522;TP18

【參考文獻(xiàn)】

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

1 夏飛;朱強(qiáng)華;金國(guó)慶;;基于CPU-GPU混合計(jì)算平臺(tái)的RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)算法并行化研究[J];國(guó)防科技大學(xué)學(xué)報(bào);2013年06期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1672494