基因序列中Tandem Repeats查找方法研究.pdf

1、生物信息學是近年來新興的一門綜合性的交叉學科。它綜合利用計算機科學、信息科學和數(shù)理統(tǒng)計學，對大量的生物序列進行存儲、檢索、分析和利用。生物信息學中的一個重要研究方向就是tandemrepeat查找。 由于Tandemrepeat在基因組成和進化中起到非常重要的作用，因此Tandemrepeat查找問題已經成為當前生物信息學的一個前沿領域和研究焦點。目前在這一研究領域存在多類解決方法，主要有基于LZ分解技術的tandemrepea

2、t查找方法，和最近興起的基于后綴樹索引的tandemrepeat查找方法。本文選取了兩種時間復雜度達到O(nlogn+z)數(shù)量級的代表性的方法，對這兩種方法進行了全面的綜述，并對它們的性能進行了系統(tǒng)的比較和分析。 同時，tandemrepeat查找領域也不斷的出現(xiàn)新的亟待解決的問題，如最近提出的最大tandemrepeats查找問題，由于最大tandemrepeats信息含量高，在字符串中的數(shù)量少等特點，使得這個問題從出現(xiàn)起就引

3、起了研究人員的廣泛興趣。鑒于目前尚沒有可用的最大tandemrepeats查找算法，在上面兩種算法比較結果的基礎上，選擇了性能優(yōu)先的基于后綴樹的tandemrepeat查找算法，對它的理論體系進行了合理的擴展，并基于這些擴展理論實現(xiàn)了最大tandemrepeats查找算法。 最后對最大tandemrepeats查找算法進行了正確性驗證和性能試驗分析，結果表明，該算法能準確地找到所有的最大tandemrepeats，并且它的性能相