基于模式匹配的DNA多序列比對及相似性分析.pdf

1、隨著人類基因組計劃(HumanGenomeProjeot，HGP)的順利實施和信息技術(shù)的迅速發(fā)展，大量分子序列數(shù)據(jù)被人們發(fā)掘出來。對這些分子序列數(shù)據(jù)進行科學(xué)有效的分析和處理，讓它們?yōu)槿祟惣膊〉脑\斷和治療、疫情的預(yù)防、新藥的開發(fā)等領(lǐng)域發(fā)揮更大的作用，已經(jīng)成為人們愈加重視的研究話題，也是生物信息學(xué)的重要研究方向。生物信息學(xué)是多門學(xué)科相融合的新型的交叉學(xué)科。在生物信息學(xué)中，如何對基因序列進行有效且快速的比對，基因序列的相似性分析和進化關(guān)系分析

2、都是其熱門課題之一。
　　 本文的主要工作是提出一種新的多序列比對算法-基于模式匹配的DNA多序列比對算法，并在其基礎(chǔ)上進行基因序列的相似性分析。具體工作概括如下：
　　 多序列比對是生物信息學(xué)中的一個基本問題。本文在模式匹配和Aho-Corasick搜索算法的理論基礎(chǔ)上，深入分析研究了基于關(guān)鍵字樹的DNA多序列比對算法，提出了一種新的多序列比對算法-基于模式匹配的DNA多序列比對算法。對該算法通過三組實驗進行分析，并與

3、原星比對算法、基于關(guān)鍵字樹的DNA多序列比對算法進行比較。當序列相似度相對較低時，雖然該算法所用時間略長于基于關(guān)鍵字樹的DNA多序列比對算法，但比對結(jié)果要優(yōu)于基于關(guān)鍵字樹的DNA多序列比對算法。當相似度很高的序列進行比對時，其比對的時間復(fù)雜度也優(yōu)于另兩種方法。實驗結(jié)果表明了該算法的有效性。
　　 序列相似性分析也是生物信息學(xué)中的基本問題之一，其分析結(jié)果可廣泛應(yīng)用于物種分類、結(jié)構(gòu)和功能預(yù)測、物種進化分析等領(lǐng)域。本文將模式匹配方法應(yīng)