DNA序列數(shù)據(jù)壓縮算法研究.pdf

1、自20世紀(jì)末以來,生物測序技術(shù)不斷的發(fā)展,隨之產(chǎn)生的各類生物數(shù)據(jù),迅速形成了龐大的生物信息數(shù)據(jù)庫。如何有效的分析,管理這些海量的數(shù)據(jù),是生物學(xué)家和計(jì)算機(jī)專家們必須著力解決的棘手問題。數(shù)據(jù)壓縮技術(shù)是解決這一問題的有效方法。DNA序列數(shù)據(jù)是一類極其重要的生物數(shù)據(jù),具有不同于其他待壓縮數(shù)據(jù)的特征,采用現(xiàn)有的各種通用數(shù)據(jù)壓縮算法,通常不能有效的壓縮。因此,研究專門針對DNA序列數(shù)據(jù)的壓縮算法有著重要意義。
　　 DNA序列數(shù)據(jù)的壓縮是一

2、項(xiàng)艱巨的任務(wù),很多學(xué)者一直致力于這方面的研究,并提出了一些經(jīng)典算法。其中,壓縮效果較好的算法有CTW+LZ,DNACompress,DNAPack。這些算法的共同特點(diǎn)是基于近似匹配壓縮的思想,搜索并壓縮DNA序列中大量存在的因少數(shù)字符的替換、插入或刪除而形成的近似匹配片段。然而,搜索近似匹配的時(shí)間和空間代價(jià)很大,壓縮率的提升卻不是很顯著。鑒于此,本文研究DNA序列中亦大量存在的精確匹配片段(包括互補(bǔ)回文形式)的壓縮,設(shè)計(jì)并實(shí)現(xiàn)一種專門壓

3、縮DNA序列的算法,稱為DNACE(DNACompressionbasedonlyonExactmatching),探索精確匹配壓縮所能實(shí)現(xiàn)的最大壓縮率。
　　 本文的主要工作:首先,系統(tǒng)的研究現(xiàn)有的多種通用無損壓縮算法及各種DNA序列數(shù)據(jù)壓縮算法,分析它們的優(yōu)缺點(diǎn)以及可以改進(jìn)的地方;其次,深入的研究DNA序列數(shù)據(jù)的特點(diǎn),為更好的設(shè)計(jì)改進(jìn)算法提供理論基礎(chǔ);接著,完成DNACE算法的總體設(shè)計(jì),算法結(jié)合兩種字典壓縮思想LZ77和LZ