RNA是生命體內(nèi)重要的大分子之一,不僅在遺傳信息翻譯中起決定作用,還具有酶的催化、細(xì)胞調(diào)節(jié)、病毒遺傳信息攜帶等功能。RNA功能多樣性的關(guān)鍵在于RNA空間結(jié)構(gòu),而RNA空間結(jié)構(gòu)的構(gòu)成由RNA二級結(jié)構(gòu)決定。真實(shí)RNA二級結(jié)構(gòu)存在于高于最小自由能一定閾值范圍內(nèi)的RNA二級結(jié)構(gòu)集合中。因此,通過計算RNA二級結(jié)構(gòu)間距離區(qū)別RNA二級結(jié)構(gòu)差異,并使用高效的聚類算法對RNA二級結(jié)構(gòu)集合進(jìn)行劃分篩選代表結(jié)構(gòu),對真實(shí)RNA結(jié)構(gòu)預(yù)測有重要意義。本文對RNA二級結(jié)構(gòu)距離計算算法和RNA二級結(jié)構(gòu)聚類算法進(jìn)行研究,內(nèi)容如下。首先,針對已有RNA二級結(jié)構(gòu)距離計算算法計算依據(jù)單一,誤差性大的問題,提出RNA二級結(jié)構(gòu)形狀-堿基對距離計算算法。算法第一步是計算RNA二級結(jié)構(gòu)的形狀距離,將RNA二級結(jié)構(gòu)抽象為帶符號的有序樹,通過轉(zhuǎn)換、刪除的樹編輯操作來計算形狀距離。第二步通過歸一化思想計算形狀距離和堿基對的平均分。第三步對Rsd-bp算法進(jìn)行多進(jìn)程優(yōu)化,實(shí)現(xiàn)計算效率的提升。其次,針對傳統(tǒng)算法采用隨機(jī)選擇的方式初始化中心點(diǎn),易陷入局部最優(yōu)解的問題,提出半監(jiān)督的RNA二級結(jié)構(gòu)k-medoids算法,根據(jù)Rsd-bp算法計算... 

【文章來源】：燕山大學(xué)河北省

【文章頁數(shù)】：72 頁

【學(xué)位級別】：碩士

【部分圖文】：

RNA二級結(jié)構(gòu)的多邊形表示圖和抽象結(jié)構(gòu)表示RNAHeliCes[32]

燕山大學(xué)工程碩士學(xué)位論文第 2 章 相關(guān)知識概念酸)是由核糖核苷酸經(jīng)磷酯鍵縮合而成長鏈狀分子起構(gòu)成已知生命形式所必需的四種主要大分子。如核苷酸分子、磷酸、核糖、堿基構(gòu)成，RNA 堿基主呤、C 胞嘧啶、U 尿嘧啶。根據(jù)堿基配對原則，R生物學(xué)功能。RNA 堿基配對規(guī)則為 A-U、C-G、G，又被稱為擺動基對。

25: else:26: D←D127: maxd1← [maxd - dist(m0,m)]28: space←seg_maxd(newr,dist(:,m))29: sapce←space-al30: M,d← f_m(m0[i],maxd,cluster,space,D,m)31: return M,dEND算法 4.2 通過可變搜索鄰域的方式進(jìn)行中心點(diǎn)替換減少了數(shù)據(jù)比對的次數(shù)提高了算法效率。算法 4.2 時間復(fù)雜度分析主要包括兩部分：(1)12 行到 31 行通過遞歸的方式查找某一中心點(diǎn)可替換中心點(diǎn)，其時間復(fù)雜度為 O( log N )，N 在最壞的情況下為該簇搜索最大半徑內(nèi)的數(shù)據(jù)個數(shù)；(2)1 到 11 行為主函數(shù)，遍歷搜索該簇內(nèi)的新中心點(diǎn)。綜上所述，算法 4.2 的總時間復(fù)雜度為O( N log N )，空間復(fù)雜度為O( N )。

【參考文獻(xiàn)】：
期刊論文
[1]云計算環(huán)境下面向數(shù)據(jù)分布的K-means聚類算法[J]. 劉雪娟,袁家斌,操鳳萍.  小型微型計算機(jī)系統(tǒng). 2017(04)
[2]IC-kmedoids:適用于RNA二級結(jié)構(gòu)預(yù)測的聚類算法[J]. 王常武,劉小鳳,王寶文,劉文遠(yuǎn).  生物醫(yī)學(xué)工程學(xué)雜志. 2015(01)
[3]半監(jiān)督聚類的若干新進(jìn)展[J]. 李昆侖,曹錚,曹麗蘋,張超,劉明.  模式識別與人工智能. 2009(05)
[4]RNA二級結(jié)構(gòu)預(yù)測中動態(tài)規(guī)劃的優(yōu)化和有效并行[J]. 譚光明,馮圣中,孫凝暉.  軟件學(xué)報. 2006(07)
[5]RNA折疊[J]. 王傳銘,潘珉,曹槐.  自然雜志. 2004(05)

博士論文
[1]半監(jiān)督聚類算法的研究與應(yīng)用[D]. 管仁初.吉林大學(xué) 2010

碩士論文
[1]基于RBP的次最優(yōu)自由能RNA二級結(jié)構(gòu)的密度聚類問題研究[D]. 王秀芹.燕山大學(xué) 2014



本文編號：3601135