RNA二級結(jié)構(gòu)比對動態(tài)時間規(guī)整算法研究.pdf

1、RNA研究是生物信息學領域的重要內(nèi)容之一。RNA結(jié)構(gòu)決定RNA功能。RNA二級結(jié)構(gòu)比對是結(jié)構(gòu)生物、結(jié)構(gòu)化學和生物信息學中的基礎性問題。RNA二級結(jié)構(gòu)比對研究對RNA二級結(jié)構(gòu)預測和RNA功能的研究有重要意義。
　　首先，提出了一種新的RNA二級結(jié)構(gòu)表示方法，將RNA二級結(jié)構(gòu)表示成一條時間序列，序列元素為非負整數(shù)。這種表示法不受RNA二級結(jié)構(gòu)是否含有假結(jié)的影響，能夠完整地表示RNA二級結(jié)構(gòu)的結(jié)構(gòu)信息。
　　其次，在這種表示法的基

2、礎上，提出一種新的、基于動態(tài)時間規(guī)整算法的RNA二級結(jié)構(gòu)比對算法，即DTW-RSC算法。算法將RNA二級結(jié)構(gòu)轉(zhuǎn)化成與RNA等長的時間序列，通過動態(tài)時間規(guī)整算法計算時間序列間規(guī)整距離，以此度量RNA二級結(jié)構(gòu)間相似性，規(guī)整距離越小代表相似性越高。
　　再次，針對DTW-RSC算法比對效果和計算時間花費兩方面，對算法進行優(yōu)化并提出基于帶約束的加權(quán)動態(tài)時間規(guī)整的RNA二級結(jié)構(gòu)比對算法，即CWDTW-RSC算法。算法加入全局約束半徑限制，縮

3、小規(guī)整路徑搜索范圍，并在計算過程中運用權(quán)重調(diào)整機制，提高計算時對結(jié)構(gòu)差異性影響較大的序列點對的計算權(quán)重，使得差異性和相似性結(jié)果更加顯著，提高RNA二級結(jié)構(gòu)數(shù)據(jù)集比對結(jié)果的區(qū)分度。
　　最后，通過兩組對比實驗分別驗證DTW-RSC算法和CWDTW-RSC算法的可行性。第一個實驗分別在四組不同數(shù)據(jù)集上運用DTW-RSC算法進行比對實驗。第二個實驗以算法運行時間和比對結(jié)果分布情況為評價標準驗證CWDTW-RSC算法的優(yōu)化效果。實驗結(jié)果表