【摘 要】
:
生活中我们随时随地接受到各种信息,而信息通常可以抽象为有限字符组成的序列。以DNA为例,它是由A、C、G、T四种碱基有机结合构成的序列。寻找多条序列的最长公共子序列(即MLCS问题)是序列挖掘中最重要的研究方向之一,它在生物信息学、模式识别、文本分析等领域有着广泛应用。但是,在大数据时代,MLCS问题中需要研究的序列数量越来越多,长度越来越长。很多算法无法在可接受的时间内完成求解,甚至会出现内存溢
论文部分内容阅读
生活中我们随时随地接受到各种信息,而信息通常可以抽象为有限字符组成的序列。以DNA为例,它是由A、C、G、T四种碱基有机结合构成的序列。寻找多条序列的最长公共子序列(即MLCS问题)是序列挖掘中最重要的研究方向之一,它在生物信息学、模式识别、文本分析等领域有着广泛应用。但是,在大数据时代,MLCS问题中需要研究的序列数量越来越多,长度越来越长。很多算法无法在可接受的时间内完成求解,甚至会出现内存溢出的问题。因此,更高效更实用的MLCS求解算法的需求日益迫切。本文首先总结了MLCS问题的国内外研究现状,然后针对现有算法存在的不足提出了两种新的求解方法。(1)提出了一种节省存储空间的分支定界法。首先,设计了一种更为合理的下界估计策略。对序列构造局部的有向无环图(DAG图),每一层保留结点时同时考虑匹配点坐标的大小及分布情况,使得到的真实公共子序列尽可能长。然后,设计了一种更简单的上界估计策略。定义新的概念“边界点”,利用边界点的性质推导出新的上界计算公式。这样,对得到的新匹配点可快速估计它所在分支的长度上界,只有当上界不小于下界时才将它加入到图中。另外,设计了节省存储的图模型。令DAG图在任何时刻只保留入度为0的结点,而每个结点存储的是从源点到该结点经过的路径对应的字符串集合。基于标准数据集,将新提出的算法一与几种有代表性算法进行对比实验,证明了算法一是有效且高效的。(2)设计了一种快速构造DAG图的分支定界法。通过对提出的算法一进行分析,发现它存在一些不足。由于它逐层构图,对每一层产生的新结点都要进行上界估计,而很多结点会多次出现在不同层,所以会对大量结点进行重复的上界计算。针对这一点,设计了一种实时更新的下界估计策略和新的上界估计策略,并且对算法框架进行调整。首先,从源点出发快速构造完整的DAG图,保证图中没有重复点。然后,从终点向源点进行深度优先回溯,回溯时对经过的结点进行上界估计,及时删除冗余点及冗余点所在分支,并根据回溯得到的序列的长度对下界进行实时更新。下界实时更新策略进一步提高了算法的剪枝能力。当所有分支回溯完毕,所有的最长公共子序列也就得到了。另外,由于图的规模过大时系统存储的数据会超出内存,本方法附加了物理方法,在构图时采用内存与外存协同调度,将部分数据结构存储到外存中,使系统能保存更大的DAG图。将新提出的算法二与几种有代表性算法在标准数据集上进行对比实验,实验数据显示算法二能处理更大规模序列的MLCS问题。
其他文献
随着材料科学技术的蓬勃发展,溶胶凝胶法目前已被广泛应用于氧化物连续纤维的制备。溶胶凝胶法是一种湿化学方法,具有工艺过程温度低,化学成分均匀度高,产品纯度高等优点。本文采用溶胶凝胶法制备了氧化铝-氧化硅复合陶瓷连续纤维和氧化硅连续纤维,并从可纺性前驱体溶胶的制备、凝胶纤维的成型、凝胶纤维陶瓷化、陶瓷纤维微观结构及力学性能等方面做了详细的研究和表征。氧化物连续纤维由于其特殊的性能在航空航天等邻域具有广
氧化铝纤维具有高强度、高模量、耐磨、高温抗氧化性等优异的性能,与其它材料结合可形成诸多性能优异的复合材料,是目前国内纤维材料研究的热点。硼化合物作为陶瓷材料的重要成分,将B2O3添加到纤维中有望改善纤维的物理化学性能,但目前含硼氧化铝连续纤维的生产在国内仍然存在空白,因此国内研究人员也一直致力于探讨新的纺丝体系和工艺制备直径较细、性能良好的含硼氧化铝基陶瓷连续纤维。本文采用溶胶-凝胶法技术结合干法
随着电子信息的迅速发展,图像数据量的迅速增加,图像分割系统对图像处理的实时性和处理速度要求越来越高。在实时性要求比较高的航空领域中,FPGA(Field Programmable Gate Array)由于其处理速度快及并行处理能力强的优点在机载图像分割领域中得到了广泛关注。基于FPGA的图像分割系统对图像进行处理时,可利用其丰富的寄存器资源以及流水线结构对大量的图像数据进行高实时性的分割处理,能
近年来,随着集成电路行业的快速发展,半导体器件的尺寸不断缩小。当器件尺寸达到深亚微米级别甚至是纳米级别时,传统平面MOS器件的尺寸缩小已经达到了极限。短沟道效应等非理想效应的加重导致了器件性能的严重退化,研究人员开始将目光放到各种具有优秀栅控性能的新结构器件中,Fin FET、堆叠纳米线(NWFET)以及堆叠纳米片(NSFET)结构被相继提出。其中,NSFET在嵌合当前主流Fin FET工艺流程基
图像信息的获取与感知是计算机视觉的基础,也是模式识别与人工智能等领域的研究热点问题之一。随着传感技术和计算技术的发展,二维图像信息难以满足生产和生活需要,亟需研究三维深度信息的获取技术和方法。双目立体匹配算法是从二维图像中获取深度信息的重要技术,相比于激光雷达、结构光等接触式测量方式具有设备成本低、稳定性高、易于部署等优点。然而,双目立体匹配任务中仍存在众多问题:由于弱纹理区域与遮挡区域匹配信息缺
本论文制备了一种莫来石-氧化铝复合连续纤维,得到的纤维制品既具有氧化铝陶瓷纤维强度高、硬度高、耐侵蚀、耐磨损等优良性能,又改善了其脆性大、抗高温蠕变性差的缺点。我们首先通过水热技术在不同温度、pH值下制备了颗粒均匀、分散性好的γ-AlOOH,最后通过对γ-AlOOH进行烧结,得到分散均匀的α-Al2O3。以自制铝溶胶、市购硅溶胶、自制α-Al2O3分散液为原料,添加纺丝助剂,利用溶胶-凝胶法经减压
AlN(氮化铝)材料具有超宽禁带宽度、高临界击穿电场强度及高热导率,在下一代高功率、高效率和耐高温电力电子器件方面具有极强的应用前景。然而,AlN材料中掺杂杂质的电离能较高,载流子浓度比较低;另外,由于AlN材料的超宽带隙,传统金属与AlN材料之间的势垒高度较高,很难在AlN上形成良好的欧姆接触,因此,AlN电子器件研制的难度较大,目前报道的AlN电子器件导通电阻很大,输出电流很小,仍处于研发早期
随着“十四五”规划发布,功率器件的重要性随之增加,逐渐成为“十四五”科技兴国线路中的重中之重。作为功率器件的顶梁柱,绝缘栅双极晶体管(IGBT)器件研究与生产也越来越重要。近年来有很多科研工作者一直致力于改善IGBT的工作性能。IGBT研究目前主要存在两个方面的问题,其一是对通态性能与关断损耗之间的折衷;其二是元胞边缘容易引起电场集中,导致边缘处提前击穿耐压下降,需要进行终端保护设计。目前大多数牵
当前互联网流量激增,对网络交换芯片的性能要求日益提高。网络芯片中的硬件查找技术主要用于路由查找、流表匹配,目前在查找速度、表项更新效率、可扩展性等方面仍面临着诸多挑战。因此,研究硬件查找技术,以提升网络芯片性能具有重要的现实意义。本论文工作源自国家部委项目,重点开展100 Gbps传输速率网络交换芯片中硬件查找匹配技术的研究。所实现的硬件查找器具备较低的查找延迟、较快的查找速度和较高的表项更新效率
计算机和通信网络经历了重大的变化,网络设备的设计成本巨大,固定功能的硬件加速器已经逐渐无法适应网络技术的高速发展,并且由于现代网络越来越复杂以及新兴服务所要求的灵活性越来越高,这种共存方式在管理网络基础设施方面带来了极大的复杂性,不断发展的网络需求给网络设备的功能和性能带来了巨大的挑战。传统Open Flow的实现,可编程性能不足,难以实现协议无关处理的需求,这将给设备厂商和用户带来极大的不便。本