【摘 要】
：
信息技术的发展带来了数据的指数级增长,同时也给数据的存储和检索带来了巨大挑战。海量数据中存在着大量的字符串或文本序列,文本和序列数据具有多样的特征,目前存在许多针对特定数据的压缩索引方法,解决了特定领域数据的存储和检索问题。但面对海量多样的数据,特定的压缩索引方法并不能满足当前需求。另一方面,近些年来基因测序技术快速发展,测序成本大大降低,随之带来了基因组数量的迅速增加。为充分利用如此丰富的基因组
论文部分内容阅读
信息技术的发展带来了数据的指数级增长,同时也给数据的存储和检索带来了巨大挑战。海量数据中存在着大量的字符串或文本序列,文本和序列数据具有多样的特征,目前存在许多针对特定数据的压缩索引方法,解决了特定领域数据的存储和检索问题。但面对海量多样的数据,特定的压缩索引方法并不能满足当前需求。另一方面,近些年来基因测序技术快速发展,测序成本大大降低,随之带来了基因组数量的迅速增加。为充分利用如此丰富的基因组数据的全部潜力,泛基因组逐渐取代传统的单一参考基因组成为基因分析的基础。研究针对泛基因组图模型的压缩索引方法,能够捕获到更加完整的遗传变异信息,从而提升全基因组关联分析的准确性。本文围绕压缩索引这一主题,首先针对海量多样的文本和序列数据的存储和检索问题,提出了自适应的通用压缩索引方法GeFM（Generic FM-index）。该方法能够感知数据的分布特征,以选择最适合的应对策略。在此基础上,将通用压缩索引方法应用于泛基因组图这一特定领域,提出了泛基因组图索引方法PGFM（Pan-genome FM-index）。本文主要创新工作如下:（1）提出了通用文本压缩索引方法GeFM。对经过BWT变换（Burrows-Wheeler transform）后的文本序列,使用小波树将其映射为比特序列。对小波树节点分块并根据数据分布采用不同编码方法进行压缩,使得编码长度达到最小。对于长度为n字符集大小为σ的文本序列T,GeFM将其压缩的理论空间占用为nHk（T）+o（n log σ）比特,其中k≤c logσ n-1且0＜c＜1,Hk为文本T的k阶经验熵。除此之外,GeFM使用解码加速表加速查询,使得编码块内的查询时间达到常量。在压缩小波树的结构上,结合后缀数组采样和逆后缀数组采样。GeFM支持三种文本模式匹配算法。分别为计数查询、定位查询和恢复查询。给定长度为m的模式P,计数查询能在O（m（log σ））的时间内计算P在文本序列T中出现的次数。定位查询能在O（（m+occ log n log log n）logσ）时间内计算P在T中出现的所有位置,occ为P在T中出现的次数。恢复查询能在O（（len+log n log log n）logσ）时间内恢复出T中任意长度为len的序列。（2）提出了泛基因组图索引方法PGFM,该方法以泛基因组的有向无环图表示为基础。使用倍增法构建路径图,包括路径扩展和对路径进行剪枝以减小索引空间。设计实现了针对泛基因组图的BWT变换,对BWT变换后的字符序列建立GeFM中的压缩小波树结构,对路径图的入度出度等信息构建简明索引结构。结合路径起始位置采样,PGFM提供两种路径匹配算法,分别为区间查询和比对查询。给定模式长度为m的模式P,区间查询在O（m log n）时间内计算P匹配到路径图排序节点集合的区间[l,r],其中n为图BWT变换得到的字符序列长度。比对查询在O（（occ+m）logn）时间内返回P匹配到泛基因组图路径的起始位置集,其中occ=r-l+1。（3）将本文提出的GeFM通过实验与其它主流通用压缩索引进行对比。实验表明,在具有不同分布特征的基准数据集上,GeFM整体具有领先的查询效率。且在部分数据集上空间效率与其它主流方法相当。将PGFM与同类型的泛基因组图索引方法GCSA2进行比较,实验表明PGFM在空间上具有明显优势,其索引大小约为GCSA2 的 50%。
其他文献
目标跟踪是计算机视觉领域的一个重要课题,在安防监控、视觉导航、医疗诊断、军事制导等方面有广泛应用前景。然而,由于目标运动过程中会出现多尺度变化、遮挡干扰等问题,现有目标跟踪算法并不能同时有效应对多种问题。本文聚焦于跟踪过程中目标多尺度变化和遮挡干扰问题展开研究,旨在通过借鉴目标检测领域相关技术提升跟踪器精度,实现跟踪器有效、稳定运行。（1）针对目标跟踪过程中的多尺度变化问题,结合多层特征融合思想,
单细胞转录组测序技术的发明使得对细胞的研究从之前Bluk测序的群细胞水平上升到单个细胞水平。随着技术的日益成熟,单个细胞的测序成本也大幅下降,越来越多的大规模数据被测出。更大规模的数据可以让研究人员更深入的探究细胞间的差异,发现未知的细胞类型。聚类作为单细胞转录组研究中用于细胞类型识别最常用方法,是单细胞数据后续深入研究的基础,但是随着数据规模的增长,现阶段的聚类算法已经出现运行效率低以及不能正常
染色质结构在基因调控与细胞功能中发挥着重要的作用,目前对于单细胞染色质结构的研究有基于图像和染色质构象捕获技术（Hi-C）等方法,这些方法能够捕获全基因组范围内基因的相互作用信息。传统的染色质结构研究认为染色质在细胞核中形成了一种从最小的染色质环（Loop）到拓扑相关结构域（TAD）、从TAD到A/B区室、从区室到染色体疆域的从小到大的层级关系。通过染色质相互作用数据准确地识别各个结构在细胞基因组
目前,资本市场对于国家的经济发展非常重要,特别是在经济和储蓄水平不是很高的泰国。资本市场有助于刺激和推动经济增长更快,并对增加收入和提高国家生活水平产生影响。根据每年决定投资股票市场的新进入投资者数量,股票市场已经成为了泰国人民获得收益的热门渠道之一。此外,上市公司应了解投资者的行为以及决定投资股票的因素。因此,本研究的目的集中在影响投资股票市场决策的人口特征因素与投资行为之间的关系。研究的主要目
伴随着5G技术的快速发展,多媒体视频信息量呈现爆炸式增长。视频技术正在突破传统的二维平面类向空间自由视角方向上演进,它给人们带来高清、可交互的视频观影体验。自由视角视频技术的突破将改变人与媒体的交互方式,在5G超高清视频、体育、综艺、智慧场馆、直播等场景具有重大应用价值。中国超高清视频产业联盟发布的《5G超高清新场景白皮书》指出:超高清视频业务是5G早期研究场景中最具吸引力的方向。其中自由视角视频
在医学临床研究中,病理影像是医生诊断癌症的基础。随着数字切片技术的发展,全视野的数字化病理图像相较于传统玻璃切片,可以在不同倍率下清晰地表示出细胞信息。但每一张病理图像仍然需要病理专家认真地读片,并没有降低医生在诊断方面耗费的时间与精力。随着计算机硬件与人工智能技术的发展,将深度学习与病理图像相结合一方面可以用于预测病理图像中的肿瘤区域或其他目标区域,另一方面可以用于挖掘病理图像中隐藏的疾病特征并
使用计算方法预测疾病相关的基因有助于揭示疾病的分子机理,为通过生物实验验证基因和疾病的关系提供指导,减少实验开销。复杂的生命活动往往经由分子间的相互合作、相互作用来实现,因此许多方法通过构建和使用分子网络来挖掘疾病相关的基因。随着对疾病相关遗传因素研究的深入以及测序技术的发展,融合多个网络、构建包含疾病与多种生物分子间的关联及相互作用的异质网络成为了可能,异质网络的引入为可以从多个层面分析和理解疾
小肠间质瘤（Small Intestinal Stromal Tumor,SIST）是原发于人体小肠部位的一种潜在恶性肿瘤,缺乏特异性临床表现。目前,在影像学中对SIST的诊断主要取决于医生丰富的临床经验,该方式效率低且受主观因素影响大。近年来,深度学习技术在医疗辅助诊断领域中发挥着重要作用,有效提升了病灶筛查的效率和准确率。然而,现有方法在SIST检测任务中的应用仍面临着特征提取及融合不充分、假
癌症是一种复杂疾病,其产生过程与多种因素有关,通常会伴随异常的基因转录调控。因此,研究癌症中基因的转录调控对于认识癌症的复杂机理有积极的促进作用。目前人们更多关注泛癌或特定癌症类型的一般基因调控关系,而对于癌症类型特异的基因调控鲜有研究。近期研究表明,不同类型的癌症体现了特异的染色质开放性,而开放状态的染色质通常是转录调控发生的前提,这使得研究癌症类型特异的基因调控关系成为可能。本文创新性地提出了
小肠间质瘤（SIST）是一种起源于间质细胞的潜在恶性肿瘤,临床表现缺乏特异性,往往容易被误诊。目前,对SIST的早期诊断主要依靠专业的临床医生对病人的CT影像进行分析,然而该过程效率低且很容易引入人工误差。伴随着图像处理技术以及深度学习的迅速发展,计算机辅助检测（CAD）逐渐应用在各种医学影像检测任务中,有效地缓解了该问题。但是,SIST的CT影像存在尺度差别大、背景复杂等特点,以及深度学习的训练