高通量DNA测序数据的多任务并行压缩算法

研究采用任务并行的方法,对FastQ格式文件的压缩程序DSRC (DNA sequence reads compression)进行了加速.这一任务并行算法将DSRC分为数据读入和数据压缩两个独立的任务,而后将数据压缩的统计过程进一步细分为title行数据统计和其他数据统计两个独立任务.研究结合CPU多线程、GPU、MIC(many integrated core),针对title行数据设计了高并行度的统计算法,实现title行数据的并行统计.在维持原有压缩比的情况下,本研究得到的最大压缩通量可以达到144 MBps,最大加速比可达三倍.结果表明,多任务并行的方法可以有效地加速DSRC,而协处理器对DSRC的加速效果并不明显.另外本算法在压缩ILLUMINA和SOLiD测序平台下的FastQ数据时,其加速效果比压缩LS454测序平台的数据更为明显.     

向量式有限元面单元行为数据并行压缩研究

在工程技术和科学技术领域,有限元计算是应用数学和力学知识,计算机技术,解决工程技术问题的数值计算方法.模型通过程式计算,得到的结果数据称为向量式有限元后处理数据,简称行为数据.介绍了向量式有限元面单元行为数据的特点,相应的并行压缩模型,并对算法进行验证.验证结果表明,该并行压缩模型能有效压缩有限元行为数据.     

并行绘制系统Chromium中的3D模型数据压缩

网络带宽不足严重限制了Chromium等并行图形绘制系统渲染巨型几何场景的速度。通过对网络传输中的几何数据进行无损压缩,提出了一种能有效缓解网络负荷的方法。该方法可以很容易地实现不同算法对特定几何数据的压缩。实现了ZLib和哈夫曼算法对Chromium系统的压缩,测试了系统对10类OpenGL应用程序的加速比和压缩比,以及在4种配置环境下的并行运行效果。使用ZLib算法时,测试程序的运行速度都有不同程度的提高,最高提升3倍;数据压缩比平均在5.0以上,最高为30;并行绘制加速比在单服务器数目下最高。ZLib算法整体表现良好,能有效减少网络通信量。     

分布式并行绘制系统中几何指令流压缩的研究与实现

对分布式并行绘制系统的几何指令进行压缩能缓解网格带宽瓶颈，对操作码作用LZW算法，对法向量使用球面对称网格剖分算法，对颜色和位置数据使用DPCM型预测编码算法，根据位置数据的特殊性，使用了4类预测器和自适应量化算法，对几何指令流组合使用多种压缩算法取得了良好的效果。在几何模型质量基本没有损失的情况下，指令平均长度压缩到原来的1/3左右，执行速度达到了400指令/ms。     

基于字符和0/1码的DNA压缩模式匹配算法*

分析对DNA序列数据进行压缩和压缩模式匹配的重要性,采用0/1编码的非自适应算法进行压缩,提出两类压缩模式匹配思路,设计实现了四种算法,并进行了性能比较.     

基于KD-tree剖分的三维动态场景快速有效压缩

为充分利用GPU并行计算特点,实现对三维动态数据的快速有效压缩,降低网络带宽的限制,提出一种基于KD-tree剖分的快速有效压缩方法。首先使用KD-tree在第0帧对整个三维场景进行划分,并对每个叶子节点进行刚体的并行构造;建立能构造刚体的叶子节点和均匀划分的三维网格之间的映射关系,在三维空间使用并查集合并并行构造的刚体;最后将压缩后的动态数据传输到客户端并重构一定时间内的三维动态场景。算法可以极大提高服务器端数据的压缩速度,有效减少需要传输的数据量。实验结果表明：该算法在保证压缩质量的同时,可以对原始三维动态场景进行快速有效压缩,有效降低网络带宽对数据传输的限制。     

面向集成电路逻辑仿真的高效数字波形压缩方法

电路仿真在集成电路设计中占有十分重要的地位.超大规模集成电路仿真输出的信号波形会占用大量存储空间,输出波形的压缩对提升电路仿真效率至关重要.逻辑仿真的输出波形主要包含信号跳变时刻信号值,还包含全部信号名、信号类型、信号位宽等辅助信息.首先提出对辅助信息的压缩处理方法,然后针对信号值数据的特点改进现有工作中的信号名压缩方案,并据此提出一种更高效的数字波形压缩存储格式.所提出的格式有利于变长编码压缩的同时,可以使用通用压缩算法进行二次压缩,进一步提升了压缩率.最后通过引入并行策略,压缩和解压缩过程能够以3阶段流水线模式运行.在缩短压缩和解压缩时间的同时,能更好地与逻辑仿真器相结合.实验结果表明,所提方法的压缩率最大达到720倍,相较于现有方法,在更短的压缩、解压缩耗时下文件压缩率最大提升近23倍.     

多重压缩DNA序列数据

根据DNA序列数据的特点,提出对DNA序列数据进行多重压缩的思想。多重压缩的首要步骤是扩展字母表。首先对DNA序列数据进行0/1编码,然后每8位转换成一个ASCII码字符,将原来的DNA序列数据仅含有的4个字符扩展到256个字符。第二步采取基于统计模型的Huffman编码压缩算法和基于转换模型的Burrows-Wheeler算法,对扩展后的DNA序列数据进行二次压缩。最后对各种算法的压缩结果进行性能分析比较,比较结果显示,多重压缩算法有较优的压缩比。     

基于字典的DNA序列压缩算法研究及应用*

在现有DNA序列数据压缩算法的基础上,以DNA序列数据的存储效率及生物学解释综合考虑,设计并实现了基于字典的DNA序列压缩算法DNADCompress.算法核心包括重复子串字典建立、字典项筛选、字串压缩编码三方面.实验数据表明,数据压缩算法压缩效果达到常用DNA序列压缩算法水平,并为序列生物学解释提供了基础.     

超长DNA序列的高效压缩算法研究

DNA序列虽然只由四个碱基组成,但数据量却非常巨大。有效的压缩DNA数据能大量节省传输的时间开销。目前已经有一些DNA序列专用的压缩算法,如Biocompress,DNACompress和CTW＋LZ。虽然这些算法可以获得较好的压缩比,但是由于采用了传统的CTW算法或Iz系列的字典替换,导致花费太多的时间。为了解决这一问题,提出使用改进的RLE,差分编码和可变长整形等一系列编码方式进行多重压缩的高效压缩算法Dzip。标准DNABenchmark数据测试的实验数据表明,该算法与现行DNA专用压缩算法相比,加速比至少为28。     

A high performance multiple sequence alignment system for pyrosequencing reads from multiple reference genomes

Genome resequencing with short reads generated from pyrosequencing generally relies on mapping the short reads against a single reference genome. However, mapping of reads from multiple reference genomes is not possible using a pairwise mapping algorithm. In order to align the reads w.r.t each other and the reference genomes, existing multiple sequence alignment(MSA) methods cannot be used because they do not take into account the position of these short reads with respect to the genome, and are highly inefficient for a large number of sequences. In this paper, we develop a highly scalable parallel algorithm based on domain decomposition, referred to as P-Pyro-Align, to align such a large number of reads from single or multiple reference genomes. The proposed alignment algorithm accurately aligns the erroneous reads, and has been implemented on a cluster of workstations using MPI library. Experimental results for different problem sizes are analyzed in terms of execution time, quality of the alignments, and the ability of the algorithm to handle reads from multiple haplotypes. We report high quality multiple alignment of up to 0.5 million reads. The algorithm is shown to be highly scalable and exhibits super-linear speedups with increasing number of processors.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。     

DNA序列拼接的分布式并行处理

针对分布式存储环境,本文提出一种DNA序列拼接的并行算法,分别对序列拼接中OVERAP、LAYOUT和CONSENSUS阶段的串行处理过程和并行算法进行了描述,并给出了算法复杂性分析。数值试验结果表明,算法是高效的。     

混沌系统和DNA编码的并行遥感图像加密算法

目的 针对传统基于混沌系统的图像加密算法在加密遥感图像时存在速度差、安全性不足等问题,提出一种混沌系统和脱氧核糖核酸（deoxyribonucleic acid,DNA）编码的并行遥感图像加密算法,提升图像加密的效率和安全性。方法 利用明文图像的安全散列算法256（secure Hash algorithm 256,SHA-256）哈希值修改混沌系统的参数和初始值,提高算法的明文敏感性,并通过2维Hénon-Sine映射置乱图像,打乱像素之间的分布规律;然后利用图形处理器（graphics processing unit,GPU）并行计算密钥序列,缩短加密时间,通过选择多个高维混沌系统和修改混沌系统初始值确保密钥序列的随机性;最后利用密钥序列和GPU对图像进行DNA并行加密,得到最终的密文图像。在DNA并行加密过程中,生成一种DNA-S盒,对DNA编码进行非线性替换。结果 在遥感图像以及普通彩色图像上的仿真实验和安全性分析结果表明,本文算法在加密遥感图像上速度达到80 Mbit/s以上,密钥空间大于10²⁰⁰,信息熵趋近于8,密文图像直方图平坦均匀,且通过了美国国家标准与技术研究院（National Institute of Standards and Technology,NIST）随机测试以及卡方检验;与其他算法相比,本文算法在密钥空间、相邻像素相关性、像素改变率（number of changing pixel rate,NPCR）、统一平均变化强度（unified averaged changed intensity,UACI）和信息熵等评价指标上更接近理想值。结论 本文算法在大幅提升加密速度的同时,保证算法足够安全,能够抵抗各种攻击,适合遥感图像以及大容量图像的保密存储和网络传输。     

基于新测序技术的比对与组装算法

针对新型超高通量测序仪Solexa测序仪所产生的测序片段read的比对与组装问题,提出一种短序列比对与组装算法SRMA,采用对参考序列进行hash的方法,将测序片段read分3段快速、准确地定位于参考序列,对不能定位的read采取从头（Denovo）组装的方法进行组装。测试结果表明SRMA算法具有较高的性能和敏感度,以及良好的应用前景。     

基于图划分的全基因组并行拼接算法

提出了一种基于图划分的全基因组并行拼接算法．该算法巧妙地将数据划分问题转化成图划分的问题,解决了传统数据划分算法中存在的节点负载不平衡的问题．同时,算法在建立关系图时有效地利用了WGS测序中所提供reads之间的长度信息和配对信息,使reads关系图能更准确地反映出数据之间的关系特性,从而提高了数据划分的准确性．实验结果表明,该算法可以准确地划分各种模拟数据、真实数据的数据集,相对于传统数据划分算法划分质量有了明显改善．     

DSRC中一种考虑剩余时间的信道访问退避算法

IEEE 802.11p协议是DSRC技术的下层标准,而该协议采用的仍然是传统的二进制指数退避算法（BEB）。BEB算法虽已广泛使用,但并不能很好地适应DSRC中车载节点的高速移动及其拓扑结构快速变化的特点,易出现信道访问不公平,网络丢包率增加等问题。针对这些问题,提出一种考虑剩余时间的退避算法,由车辆节点的当前速度计算其剩余时间,优化退避机制。实验表明,提出的机制在改善信道访问公平性,提高网络吞吐量等方面均有较好的改善。     

针对短测序片段的基因序列拼接算法

为了获得高效的拼接结果,针对新测序技术产生的较短测序片段,提出了通过对测序片段编码,将其映射到能够快速查找的自定义表中,结合高效位并行字符串模糊匹配算法-BPM,从自定义表中寻找较长连通路径的方法,实现了对短测序片段的快速拼接.实验结果表明,该算法针对500M的高质量源数据,在耗时136s的情况下,准确度可达79％,覆盖度可达82％;针对错误率为0.1％的500M源数据,在耗时150s的情况下,准确度可达72％,覆盖度可达73％.在短时间内较好的完成了拼接任务.     

一种并行的正序变异的混合PSO算法研究与应用

为有效解决粒子群算法在求解路网问题时易陷入局部最优的缺点,根据高校地理数据和多核系统并行处理方式,将自平衡策略和变异思想结合且并行化,提出一种并行求解高校路网问题的正序变异的混合PSO算法。该算法引入适合此问题的自平衡正序变异策略且采用并行处理方式,使其生成相互独立子群体且并行求解,来提高算法求解精度,保证算法多样性及收敛,降低计算时间。实验以Visual Studio 2005中C++编程实现仿真,结果表明此算法不但能有效求解高校路网问题,而且比离散PSO算法、并行自平衡PSO算法的解更优。     

基于MPI的伪随机序列并行加密算法研究

伪随机序列并行加密算法是科学与工程领域中极为重要的问题，拥有广泛的应用领域。而MPI是现在最流行的并行编程的工具，基于MPI的并行计算是现在被关注的热点。伪随机序列并行加密算法存在研究和实现上的困难，主要原因就是没有一个有效对它进行支持的工具。本文将伪随机序列并行加密算法与MPI结合起来，研究如何提高伪随机序列并行加密算法的效率。通过实验模拟和算法分析，证明这是有效的。因此，基于MPI的伪随机序列并行加密算法将会为相关应用和研究领域提供新的方法和方向。