生物序列比對算法的研究與實現(xiàn).pdf

1、生物信息學是利用現(xiàn)代計算技術來處理和研究生物數(shù)據(jù)的一門新型交叉學科。其中,序列比對是生物信息學中最基本的信息處理方法,對于發(fā)現(xiàn)核酸和蛋白質(zhì)序列上的功能、結構和進化信息具有非常重要的意義。如何獲得比對準確率更高、時間空間效率更好的序列比對算法是生物信息學研究的一個重要課題。本文研究了以動態(tài)規(guī)劃算法為代表的全局比對算法和以Smith-Waterman算法、BLAST算法、FASTA算法為代表的局部比對算法。在對這些算法的設計思想進行研究、性

2、能進行比較分析的基礎上,提出了基于后綴樹的雙序列比對算法SPLSA。該算法分為三個主要步驟—建立后綴樹,尋找公共子串,連接公共子串。本算法建立帶后綴鏈的后綴樹,利用后綴鏈可以快速定位下一后綴內(nèi)結點的優(yōu)勢在線性時間內(nèi)完成后綴樹的建立；另外,后綴樹本身具有易于尋找公共子串的特性,利用此后綴樹可以在線性時間內(nèi)完成公共子串的尋找；而公共子串連接成匹配段的過程中采用了剪枝策略,降低了算法的運行時間；采用深度擴展和廣度擴展相結合的方式提高了算法比對

3、準確性。實驗結果表明,SPLSA算法在運行時間上優(yōu)于Smith-Waterman算法,在比對準確率上優(yōu)于BLAST算法。本文研究了目前主流的多序列比算法—漸進多序列比對算法和迭代多序列比對算法,分析了這兩類算法的優(yōu)缺點及適用范圍。研究并實現(xiàn)了ClustalW漸進多序列比對算法。在對上述算法研究的基礎上,實現(xiàn)了一個生物序列比對系統(tǒng)。該系統(tǒng)中雙序列比對采用SPLSA算法,多序列比對采用ClustalW算法。除此之外,該系統(tǒng)還提供了文件搜索、