基于FFT和k-mer劃分的多序列比對(duì).pdf

1、序列比對(duì)是現(xiàn)代生物信息學(xué)中一個(gè)最基本的研究課題。隨著生物數(shù)據(jù)庫快速持續(xù)的增長(zhǎng)，對(duì)多序列比對(duì)算法的敏感性和運(yùn)算速度提出了更高的要求，開發(fā)具有高敏感性和高效率的算法成為當(dāng)今研究的重點(diǎn)。本文提出一個(gè)新的算法KMD MSA，它能在保持原來比對(duì)精度的前提下，降低比對(duì)的時(shí)間復(fù)雜度。 本文首先介紹了序列比對(duì)涉及的基本問題：空位罰分，替換矩陣和比對(duì)結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)。接著對(duì)基于漸進(jìn)方法構(gòu)建的多序列比對(duì)算法C1ustalw進(jìn)行了深入的研究。然后通過對(duì)這

2、些算法的分析，對(duì)當(dāng)前最流行的漸進(jìn)比對(duì)提出了改進(jìn)。 MAFFT最早將分治思想應(yīng)用到序列比對(duì)。它把快速傅立葉變換應(yīng)用到序列比對(duì)，使得兩序列比對(duì)的時(shí)間復(fù)雜度從O(L1)降低到O(LlgL)。通過把k-mer應(yīng)用在序列比對(duì)中，并結(jié)合分治思想，本文提出了一個(gè)新的多序列比對(duì)方法：KMD MSA。它通過快速的識(shí)別同源區(qū)域，把比對(duì)問題分成子問題予以解決。而尋找同源片斷的時(shí)間復(fù)雜度也從O(LlgL)降低到O(L)。為了降低時(shí)間和空間復(fù)雜度，該方法