DNA序列中基于后綴樹的重復體識別算法.pdf

1、重復體識別是生物信息學中分析基因組序列的主要手段之一。在真核生物基因中重復體DNA占據(jù)了非常重要的地位。通過識別重復體可以發(fā)現(xiàn)基因組的進化規(guī)則和許多疾病的遺傳規(guī)律。許多轉(zhuǎn)位子重復體序列作為可編碼區(qū)域重復出現(xiàn)在基因組序列中，識別這些重復體對基因組解碼起到了很重要的作用。 通過考慮重復體序列的長度和發(fā)生頻率，提出了一種基于后綴樹的識別初級重復體的RepSeeker算法。算法采用最低限制頻率，并通過重疊性合并，最大程度地擴展了重復體

2、的長度。算法以DNA序列所構(gòu)造的后綴樹作為輸入，并以基于后綴樹的查詢算法作為手段，最終生成輸入的DNA序列的初級重復體分類表。為了進一步地提高RepSeeker算法的效率，我們對后綴樹構(gòu)造算法進行了適應性改進。在構(gòu)造后綴樹時，給葉子節(jié)點編號，并在分支節(jié)點加入了葉子信息數(shù)組LL（Leaf List）。在此基礎上，改進了基于后綴樹的查詢算法，從而避免了RepSeeker算法進行高頻度的子樹遍歷。 對Ukkonen后綴樹構(gòu)造算法的改