高效的motif識(shí)別方法研究.pdf

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

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

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