高度相似基因组序列数据集的压缩算法研究

发布时间：2021-01-01 12:51

　　随着高通量测序技术的发展,测序需要的成本急速下降,得到的基因组数据呈爆炸式增长,因此有效地存储和搜索这些基因组数据成为了急需解决的问题。压缩技术可以减少数据的存储空间,所以优秀的压缩索引算法成为了解决这一问题的关键技术。研究发现基因序列与普通文本数据的结构不同,序列中包含较多的冗余信息,而且同一物种或者按照生物分类法则划分的较相近的物种间的序列相似度很高,通用的文本压缩算法无法有效地压缩及搜索基因组序列集。所以,需要研究针对高度相似基因组序列数据集的压缩索引算法。本文提出一种新的基于参考序列的压缩索引算法FMQ,能够高效地存储和搜索基因组序列集。主要思路是将序列集划分为参考序列和非参考序列,然后计算非参考序列与参考序列之间的差异信息,再设计压缩索引结构存储这些差异信息,并提出了在压缩索引结构上的搜索算法（包括子串提取和模式定位算法）。具体工作如下:压缩索引构建。首先,随机选取一条序列作为参考序列,顺序比较参考序列与非参考序列,得到不匹配的子序列,利用最长公共子序列算法获得参考序列与每个子序列之间的公共部分,根据公共部分逆推得到序列间的差异信息。然后,根据差异信息不同部分的特点,分别对差... 

【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

L串的平衡小波树表示

西安电子科技大学硕士学位论文三层结构的主要思想是首先将长度为 n 的比特串 B 划分为长度 s = log2n / 2 的超块，然后将每个超块划分为长度 b=logn/ 2 的块。利用数组 Rs 存储当前超块起始位置之前 1 的个数，即 Rs[j] = rank(B, j s)，j [0, n / s]。Rb 存储当前块的起始位置与其所在超块的起始位置之间 1 的个数，即 Rb[j] = rank(B, j b) rank(B, k s)，j [0n/s]，其中 k 为块号为 j 的块所处的超块号。建立查找表 Rp，其中记录的是长度为块大小 b 的所有可能出现的比特串的 rank 值。经典的三层结构如图 2.5 所示。

以及在压缩结构上的子串提取与模式定位算法进行详细介绍，并在理论上分析算法的性能。3.1 算法框架本文的主要研究对象是高度相似的基因组序列数据集。研究的具体问题是：给定包含 m 条高度相似基因组序列的集合 G={S1, S2, …, Sm}，每条序列取自字符表 ={A,T,C,G,N}，序列 Si的长度用|Si|来表示，1≤i≤m，目标是建立有效的压缩索引结构，获得较好的压缩效率并支持高效的子串提取及模式定位操作，其中子串提取操作是提取某个序列从特定位置开始的子串，即 extract 操作。模式定位操作是得到某个模式在整个基因组序列集中出现的位置，即 locate 操作。任意两条基因序列之间是高度相似的，因此整个基因组序列集 G 中一定包含很多重复的冗余信息。如果能够得到尽可能多的冗余信息，采用少量的信息标记这些冗余，那么存储整个序列集的空间代价将会极大地降低。本文算法 FMQ 采用的算法框架如图 3.1 所示：

【参考文献】：
硕士论文
[1]基于FM-index的DNA序列数据压缩算法[D]. 李新娱.西安电子科技大学 2017



本文编号：2951320