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

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

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

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