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

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

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