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

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

2、植入基序問題(PMP)的(l,e)問題的算法進行標準測試，并分析測試結(jié)果的綜合性能。 在研究中發(fā)現(xiàn)，擴展的基序問題(EMP)中的(l,e)-(20-16)問題是目前生物學(xué)家十分關(guān)注的基序發(fā)現(xiàn)問題。針對這個具體的問題，本文提出了一種基于彩色編碼技術(shù)的樣本驅(qū)動(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)問題時，CCMF算法利用彩色編碼技術(shù)將4845個組合降低到403個著色，將能極大減少用分治算法和分支定界法求解(l,e)-(16-16)問題的次數(shù)，從而明顯提高整個算法的運行效率。測試結(jié)果表明，CCMF算法能快速發(fā)