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

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

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

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