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

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

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

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