基于OpenCL的RNA二級結構預測算法

汪方良，施慧彬

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211100)

基于OpenCL的RNA二級結構預測算法

汪方良，施慧彬

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211100)

包含假結的RNA二級結構預測在計算分子生物學中一直是一個重要的研究領域，而預測包含任意類型假結結構已被證明為NP完全問題。為了解決此類問題，在CPU平臺上實現了一種改進的遺傳算法。該算法可預測包含兩類假結結構的RNA序列，敏感性可達到0.775，陽性預測率可達到0.822 5。針對基于遺傳算法帶假結的RNA二級結構預測低效的問題，提出了基于OpenCL的異構并行加速算法。該算法在分析串行算法并行性的基礎上，在種群迭代進化階段進行異構加速，并基于GPU設備和OpenCL編程框架改進算法過程。為驗證所提算法的可行性和有效性，基于相同的測試集進行了實驗測試。測試結果表明，相對于串行算法，改進后的異構并行加速算法平均可實現2.72倍的速度提升，有效降低了RNA二級結構預測的耗時，提高了算法模擬預測效率。

RNA二級結構預測；假結；OpenCL；異構計算

0 引 言

RNA在基因表達中起到了十分重要的作用，對于每種RNA的功能分析，解析其結構特征是關鍵的一步。通過實驗方法分析RNA結構特征雖然精確，但成本較高，因此，通過計算方法預測RNA二級結構一直是近年來計算分子生物學領域比較熱門的課題之一。

目前預測RNA結構的算法大致可分為兩類：基于多序列比對的預測算法和單序列預測算法。多序列比對算法利用了同源RNA序列具有的相近遺傳信息與結構特性，預測精度較高，但是需要較多的先驗信息[1-2]?！?br>