生物信息學(xué)中的基序發(fā)現(xiàn)問題算法研究.pdf

1、從生物序列中發(fā)現(xiàn)基序是生物信息學(xué)中一個(gè)的熱點(diǎn)研究問題，也是生物學(xué)中理解基因調(diào)控的最重要的基礎(chǔ)計(jì)算問題之一。隨著生物技術(shù)的迅速發(fā)展，人們不斷地對(duì)最初的基序發(fā)現(xiàn)問題的計(jì)算模型進(jìn)行改進(jìn)，并針對(duì)不同的計(jì)算模型提出了許多求解基序發(fā)現(xiàn)問題的算法。 本文首先對(duì)已有的各類基序發(fā)現(xiàn)問題算法進(jìn)行綜述，詳細(xì)介紹基序發(fā)現(xiàn)問題算法中基序模型表示方式、計(jì)分模型和評(píng)價(jià)指標(biāo)等相關(guān)內(nèi)容，分析三類經(jīng)典基序發(fā)現(xiàn)問題算法的基本思想和特點(diǎn)。本文選取九個(gè)經(jīng)典的求解

2、植入基序問題(PMP)的(l,e)問題的算法進(jìn)行標(biāo)準(zhǔn)測(cè)試，并分析測(cè)試結(jié)果的綜合性能。 在研究中發(fā)現(xiàn)，擴(kuò)展的基序問題(EMP)中的(l,e)-(20-16)問題是目前生物學(xué)家十分關(guān)注的基序發(fā)現(xiàn)問題。針對(duì)這個(gè)具體的問題，本文提出了一種基于彩色編碼技術(shù)的樣本驅(qū)動(dòng)(SD)搜索算法——彩色編碼基序發(fā)現(xiàn)算法(Color Coding Motif Finding Algorithm，CCMF算法)。它利用彩色編碼技術(shù)將(l,e)-(2

3、0-16)問題轉(zhuǎn)化為序列條數(shù)t=16的(l,e)問題(記作(l,e)-(16-16)問題)，再采用分治算法和分支定界法來求解(l,e)-(16-16)問題。在解決將(l,e)-(20-16)問題轉(zhuǎn)化為(l,e)-(16-16)問題時(shí)，CCMF算法利用彩色編碼技術(shù)將4845個(gè)組合降低到403個(gè)著色，將能極大減少用分治算法和分支定界法求解(l,e)-(16-16)問題的次數(shù)，從而明顯提高整個(gè)算法的運(yùn)行效率。測(cè)試結(jié)果表明，CCMF算法能快速發(fā)