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

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

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

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