检索结果-南通市图书馆

检索条件"主题词=FM索引"

共 3 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

面向基因组组装的索引与检索方法研究

面向基因组组装的索引与检索方法研究

引用

作者：刘郭如西安电子科技大学

学位级别：硕士

人们对生命的渴望和好奇,推动着基因测序技术的飞速发展,基因测序的成本随之大幅下降,相应地,产出的测序序列数据量成倍增长,对测序序列的存储和检索面临的挑战不断加大;另外,基因测序序列的k-mer为人们提供了一个了解基因组序列的组成... 详细信息

人们对生命的渴望和好奇,推动着基因测序技术的飞速发展,基因测序的成本随之大幅下降,相应地,产出的测序序列数据量成倍增长,对测序序列的存储和检索面临的挑战不断加大;另外,基因测序序列的k-mer为人们提供了一个了解基因组序列的组成和生命遗传进化规律的入口。因此,为大规模的基因测序序列建立压缩自索引,减少存储空间,同时支持对测序序列的k-mer信息进行快速检索,越来越成为必要。基因组组装是通过一系列的算法,根据测序得到的短读序列之间的重叠信息,拼接组装得到完整的基因组序列的过程,其中最容易成为瓶颈的是第一步,这一步需要快速的从所有的测序短读中获取所有的k-mer的计数与位置信息并建立k-mer索引,作为后续步骤的基础,比如Flye组装的第一步A-Bruijn图的构建就是k-mer索引的一种虚拟实现,因此,设计并实现高效的存储结构和快速的k-mer信息检索是关键。针对上述问题,本文在通用的文本压缩自索引fm索引的基础上,通过添加辅助结构对索引进行拓展,提出了可支持对基因测序序列的k-mer进行常用的三类基础查询的压缩索引fm-KMQ。在此基础上,结合最小完美哈希函数,针对Flye组装提出了A-Bruijn图的构建方法MPHF-ABG。本文的主要创新性工作如下:(1)提出了可支持对基因测序短读序列的k-mer信息进行高效检索的压缩索引fm-KMQ。fm-KMQ首先将通用的文本压缩自索引fm索引中的后缀数组构建算法替换为适用于大文本的外存并行的后缀数组构建算法,缩短了索引的构建时间,然后在使用了混合编码的fm索引上添加辅助结构对索引进行拓展,使得索引可以支持对测序序列的k-mer的常用三类基础查询。其中,对于长度为n的测序序列,fm-KMQ可以支持CountOfAll查询,CountOfReads查询,以及CountOfOnce Reads查询的时间复杂度为常量时间O(1),可以支持LocateOfAll查询,LocateOfReads查询,以及LocateOfOnce Reads查询的时间复杂度为O(occlog nloglog n),其中occ为不同查询对应情况下k-mer的出现次数。(2)提出了基于最小完美哈希函数的A-Bruijn图的构建方法MPHF-ABG。在Flye组装中,构建A-Bruijn图本质上就是为纠错后的基因测序序列构建k-mer索引,即设计并实现一种便于对任一k-mer快速访问的结构和方法。MPHF-ABG为减少存储结构对空间的消耗,首先对测序序列进行了预处理,只获取纠错后的有效的k-mer,然后使用可以支持常量查询的最小完美哈希函数构建哈希表作为存储结构,实现无哈希冲突的将获取的所有k-mer映射至最小的整数范围上,同时哈希表中每个输入所占的平均位数与输入量无关从而保证该结构所占空间尽可能地小,最后利用已经构建的测序序列的压缩索引fm-KMQ通过多线程技术并行的完成对所需k-mer信息的快速检索。另外,额外的以同样的处理过程得到了生信工具中常用的k-mer计数工具MPHF-KQC,并与现有工具进行性能对比。对本文提出的fm-KMQ在索引构建时间,索引压缩率以及查询时间上进行实验分析与对比,结果表明fm-KMQ不仅支持为更大规模的文件构建索引,而且构建时间也大幅缩短,在压缩率和查询效率上也更优。对本文提出的MPHF-ABG在设计的结构所占的空间以及使用的时间上进行了实验分析和对比,结果表明MPHF-ABG在空间和时间消耗上都有一定的优势。

关键词：后缀数组 fm索引最小完美哈希函数 k-mer索引基因组组装

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向基因组的高效fm-index构造算法

面向基因组的高效FM-index构造算法

引用

作者：王哲西安电子科技大学

学位级别：硕士

随着第一条人类DNA被解码成2.8GB的字符串,许多生物学的研究都集中在对DNA序列的分析上。本文选取DNA序列的索引进行研究,旨在解决目前DNA序列的fm-index不能够在普通电脑(4-8G内存)上高效构造的问题。本文提出的增量式构造fm-index的... 详细信息

随着第一条人类DNA被解码成2.8GB的字符串,许多生物学的研究都集中在对DNA序列的分析上。本文选取DNA序列的索引进行研究,旨在解决目前DNA序列的fm-index不能够在普通电脑(4-8G内存)上高效构造的问题。本文提出的增量式构造fm-index的算法框架为继续研究高效构造fm-index提供了理论基础。现实意义上,该算法扩展了fm-index的应用范围,节约了购买超级计算机的成本。fm-index是压缩全文本自索引的一种。通常fm-index的算法框架分为以下步骤:首先,将文本T经过BWT变换(Burrow-Wheeler Transform)得到的文本L;然后,采用小波树(Wavelet-tree)对文本L进行编码存储;接着为小波树的内部节点提供高效的rank查询结构;最后采样后缀数组(SA)和名次数组(SA-1)。fm-index在这些基础数据结构的支持下实现高效的count,locate和extract操作。它最初最多使用5nHk(T)+o(n)位的空间存储,其中Hk(T)表示T的k阶经验熵,n表示文本的长度。fm-index可在普通电脑内存中存储,然而构造过程中过高的峰值内存或者过长的构造的时间均限制了fm-index的应用。通过大量阅读和分析之前的研究成果,深入理解BWT变换的过程,理解SA、SA-1和LF映射的关系以及rank查询结构的特点,经过大量实验测试与分析,最终得到了本文的算法。本文主要分3个部分进行了研究:首先,为了解决DNA数据的BWT变换无法在普通电脑上完成的问题,本文提出了LF-BWT算法。该算法理论上在线性时间内利用线性空间完成了DNA数据的BWT变换,实验表明,LF-BWT算法仅需不到原文本1倍的空间就可以快速完成DNA数据的BWT变换,并且可以调整参数来获得时间和空间的权衡,进一步扩展了LF-BWT算法的使用范围。该算法在与最新的主流算法的比较中也表现出了优势。第二,为了解决LF-BWT算法在构造过程没有获得SA和SA-1采样的问题,本文提出了由BWT变换生成的文本通过LF映射在线性时间内获得SA和SA-1采样的算法。该算法并不完整存储SA,而是每次LF映射过程中遇到采样点就进行采样,这极大的减小了内存空间的占用。第三,为了更进一步提高fm-index的压缩率和查询效率,本文提出了RRR算法的一个改进版本CF算法,它充分结合了CPU字长以及数据的局部性原理,提高了cache命中率。该算法在保持了与RRR算法的空间和查询时间理论复杂性一致的情况下,提供了更加高效的实际性能。实验表明,不管是随机数据还是真实DNA数据,CF算法均表现出了很大的优势。

关键词： fm索引 BWT变换后向搜索小波树 rank

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一种灵活精度可控的可搜索对称加密方案

一种灵活精度可控的可搜索对称加密方案

引用

作者：陶汝裕华南农业大学

学位级别：硕士

近年来,随着云计算技术和云存储服务的快速发展,越来越多的用户选择将数据外包给公开的云服务器。然而,公开的云服务器作为第三方服务提供商是不可完全信赖的。为了保证用户数据和隐私,用户选择加密明文数据然后外包到公开云服务器存储... 详细信息

近年来,随着云计算技术和云存储服务的快速发展,越来越多的用户选择将数据外包给公开的云服务器。然而,公开的云服务器作为第三方服务提供商是不可完全信赖的。为了保证用户数据和隐私,用户选择加密明文数据然后外包到公开云服务器存储。虽然外包密文数据极大地便利了用户,但是在密文数据下明文数据检索技术就不会起作用。因此可搜索加密技术便应运而生。在传统基于关键词集的可搜索对称加密技术SSE(Searchable Symmetric Encryption)中,关键词集合通常由关键词提取算法生成,这样会使关键词的内容和数量严格地受到关键词提取算法的限制。在这种可搜索加密方案中,关键词提取算法是高效的,用户只能搜索到系统初始化生成的关键词集中的关键词,而无法搜索到任何其他相关内容。关键词提取算法是低效的,用户几乎无法搜索到想要的文件。此外用户可能会接收到大量低精度结果,这些结果与用户想要的结果有一定差距从而影响用户体验。这些问题都极大地限制了加密搜索技术的应用。本文通过研究上述的这些问题,提出了一种能够支持灵活的精度可以控制的可搜索对称加密方案FASSE(Flexible Accuracy-controllable Searchable Symmetric Encryption),通过在系统运行过程中灵活地搜索关键词,减少了对关键词集的过度依赖,有效提高了加密搜索技术灵活性。FASSE在灵活高效的搜索的同时也保证了用户的隐私和数据都不会泄露。FASSE提供了三种基本搜索方式,分别是一次命中搜索、增强搜索和过滤搜索。这三种搜索方式对应着用户一次在字典中找到搜索关键词记录、没有在字典中找到搜索关键词记录而一次在文档摘要中找到搜索关键词记录、多次在字典和文档摘要中查找到搜索关键词记录的三种搜索情况。同时,本文除了一次命中搜索、增强搜索和过滤搜索还结合这三种搜索方式设计了一种基于通配符技术的模糊增强搜索,并且通过设置部分参数从而达到灵活可控精度的搜索效果从而进一步增强系统的实用性。本文中的FASSE方案可以抵抗IND-CKA,并在文中给出了相应的安全性证明。FASSE方案的具体实现语言是Java编程开发语言实现并且通过对一次命中搜索、增强搜索、过滤搜索、模糊增强搜索的实验得出FASSE在实验论文数据集中平均搜索完每一篇论文的时间为100ms。

关键词：可搜索对称加密 BWT数据转换后缀数组 fm索引 LF映射 SubLF映射

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：