1、 本文首先討論雙序列比對和多序列比對的定義，介紹多序列比對的四種常用模型，分析其優(yōu)缺點(diǎn)；然后分析和比較多序列比對的各類算法(精確算法、近似算法、啟發(fā)式算法和并行算法等)；最后給出需要解決的研究問題。在充分調(diào)研了序列比對問題的基礎(chǔ)上，本文圍繞著放松限制條件的序列比對、多序列比對的并行近似算法和序列比對的并行模型等三個問題開展了研究。 本文主要內(nèi)容：放松限制條件的序列比對；提出了一個時間復(fù)雜度為O((α+1)n2(α+1))的放松限制

2、條件的雙序列比對問題的完全算法；提出了一個時間復(fù)雜度為O(k2(α+1)2(α+1))的LCMSA的近似算法。多序列比對的并行近似算法。 序列比對的并行模型。在研究該模型已有的算法后，本文改進(jìn)了已有的算法，使其在輸出最優(yōu)罰分的同時還能輸出最優(yōu)比對；對改進(jìn)的雙序列比對算法進(jìn)行了復(fù)雜度分析，其晶格開銷為O(l1l2(m+k2)，延遲時間為O(l1l2(m+k)，(l1和l2分別為兩個序列的長度，罰分值用k位二進(jìn)制數(shù)表示，空格計(jì)數(shù)用m位二