基于壓縮后綴數(shù)組的空間高效短讀比對(duì)算法.pdf

1、新一代基因測(cè)序技術(shù)(NGS)的出現(xiàn)使得測(cè)序成本飛速下降，隨之而來(lái)的是大量的短讀序列需要更快速準(zhǔn)確的比對(duì)程序來(lái)處理。第一代基于散列表技術(shù)的序列比對(duì)算法如Bowtie等能夠快速準(zhǔn)確的完成比對(duì)工作，但其不支持gap比對(duì)的特性使得在短讀序列(short reads)過(guò)長(zhǎng)導(dǎo)致indel出現(xiàn)頻繁時(shí)，比對(duì)的精度也隨之下降。另一方面，近年來(lái)壓縮索引(BWT,CSA,FM-index)領(lǐng)域的相關(guān)研究使得在較小內(nèi)存中索引人類(lèi)基因組這樣的大規(guī)模序列成為可能。

2、這導(dǎo)致近年來(lái)出現(xiàn)了很多基于壓縮索引的短讀比對(duì)算法，如BWA,Bowtie等。本文提出了一種基于壓縮后綴數(shù)組和后向搜索實(shí)現(xiàn)近似匹配的算法來(lái)實(shí)現(xiàn)短讀比對(duì)，在比對(duì)時(shí)間和空間以及比對(duì)精度上都取得了很好的效果。
　　基于壓縮后綴數(shù)組的短讀比對(duì)算法(CSAA)，采用了壓縮后綴數(shù)組來(lái)構(gòu)建參考序列的索引，并使用后向搜索來(lái)做匹配。通過(guò)引入搜索樹(shù)，CSAA實(shí)現(xiàn)了近似匹配算法，從而支持完全的gap比對(duì)。此外CSAA在搜索樹(shù)上使用了一種類(lèi)似堆的優(yōu)先堆數(shù)據(jù)

3、結(jié)構(gòu)，大大減小了搜索空間。而且每一次的搜索方向都能保證是最優(yōu)的。最后結(jié)合罰分機(jī)制以及dif f erence距離，定義seed等方法，進(jìn)一步降低搜索空間，提高了CSAA的比對(duì)速度和精度。
　　CSAA的高效體現(xiàn)在三個(gè)方面。一是空間高效的索引方法；二是基于后向搜索的高效的近似匹配方法；三是seed策略和多線(xiàn)程比對(duì)技術(shù)的利用。本文采用了增量法進(jìn)行壓縮后綴數(shù)組索引的構(gòu)建，從而跳過(guò)后綴數(shù)組的構(gòu)建，降低了對(duì)內(nèi)存的需求。而在比對(duì)時(shí)，seed的