高效的motif識別方法研究.pdf

1、轉(zhuǎn)錄因子結(jié)合位點(diǎn)預(yù)測問題,即在DNA序列中發(fā)現(xiàn)允許出現(xiàn)變異的motif的問題,不論對于分子生物學(xué)還是對于計(jì)算生物學(xué),都是一項(xiàng)非常重要的研究?；谝恢滦蛄斜磉_(dá)的模式發(fā)現(xiàn)算法,典型的如使用后綴樹來存儲DNA序列,當(dāng)通過深度優(yōu)先遍歷后綴樹來匹配模式時,有許多方法可以用來提升算法速度,例如記錄不匹配字符數(shù)或使用一些基于統(tǒng)計(jì)概率的模型來拋棄一些路徑。但是目前這些算法的復(fù)雜度依然很高,一些算法轉(zhuǎn)而使用空間復(fù)雜度較高的結(jié)構(gòu)來加速匹配過程,效果雖有提高

2、,但仍然無法完全滿足現(xiàn)實(shí)需求。為了解決這一問題,本文提出了一個數(shù)據(jù)結(jié)構(gòu)以及與之對應(yīng)的兩個算法,通過充分利用匹配過程中產(chǎn)生的中間結(jié)果,從而在保持精確性且空間耗費(fèi)很小的情況下大大提高進(jìn)程的效率。
　　 在本文提出的算法中,同樣使用后綴樹來存儲DNA序列。然而,本文提出了一個匹配路徑集合棧數(shù)據(jù)結(jié)構(gòu)來記錄中間匹配結(jié)果,稱之為SUTMAPST結(jié)構(gòu),以便具有公共前綴的不同模式匹配過程共享公共前綴的匹配結(jié)果信息。使用匹配路徑集合棧,匹配過程可

3、以層次式遍歷與回溯從而避免了大量的重復(fù)匹配操作,能夠有效的支持基于后綴樹的模式發(fā)現(xiàn)算法。
　　 本文提出了SUTMAPSTA算法,可以很好的解決植入d-Motif問題(Plantedd-Motif Problem)從而驗(yàn)證SUTMAPST數(shù)據(jù)結(jié)構(gòu)的有效性。另外,本文使用SUTMAPST數(shù)據(jù)結(jié)構(gòu)結(jié)合Weeder的剪枝思想提出WSUTMAPSTA算法。WSUTMAPSTA算法與Weeder算法相比在不降低準(zhǔn)確性的情況下,大幅提升了算