基于GPU的大规模基因片段并行匹配的方法

后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.     

基于动态字典的增量更新算法

为减少软件更新中增量包的大小,提出了基于动态字典的增量更新算法DICDIFF。该算法使用后缀排序方法预处理新老版本文件,将预处理的结果以后缀数组和名次数组的形式存储为字典目录,基于该字典目录能够快速查找字典数据集与待编码数据之间的相同数据段。随着编码进度的推进,动态扩展字典数据集能够使用更多已知数据段用于构造待编码数据。通过选取多款软件的新旧版本作为实验样本,DICDIFF在平均情况下能够节省68.9%的网络流量,高于现有其他增量更新算法。实验结果表明,该算法能够进一步减少增量更新过程中的网络流量。     

利用水平分割法计算给定串中的所有Maximal(NE/SNE) Repeats

提出一种利用给定符号串x［1…n］的后缀数组和最 长公共前缀数组求x所有最大重复的新方法〖CD2〗水平分割法. 通过对x的最大不可扩展重复和最大超级不可扩展重复所有可能出现的位置以及判定条件的提炼, 分别给出仅由x的后缀数组和最长公共前缀数组求x的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复的算法. 该算法克服了除后缀数组和最长公共前缀数组外, 还需利用其他辅助数组的缺陷, 降低了空间开销, 且时间复杂度没有增加, 并可以在对最长公共前缀数组仅进行一次扫描的情况下求出给定串的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复.     

一种基于后缀数组的无词典分词方法

提出一种基于后缀数组的无词典分词算法. 该算法通过后缀数组和利用散列表获得汉字的结合模式, 通过置信度筛选词. 实验表明, 在无需词典和语料库的前提下, 该算法能够快速准确地抽取文档中的中、 高频词. 适用于对词条频度敏感、 对计算速度要求高的中文信息处理.     

基于改进哈夫曼编码的全文索引结构压缩算法

为解决全文索引的索引结构压缩问题,提出了文本的基于正规哈夫曼编码小波树形式,并将该结构与后缀数组结合,实现了基于正规哈夫曼编码的小波树和高效构造算法.实验结果表明,在不降低运行效率的前提下,存储空间得到有效的压缩,从而证明了改进方法的有效性.     

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·     

基于后缀树的图像识别研究

分析了后缀树在一维和二维字符串处理方面的优势．以后缀树为索引，将后缀树和最低公共祖先问题相结合，提出了一个在仅考虑平移变换操作的条件下．进行图像精确识别的算法，并从时间复杂度上证明了其优于传统的二：维精确模式匹配算法。     

基于后缀数组的XML搜索技术

在对XML文档建立索引机制的基础上,采用基于后缀数组的快速排序算法产生有序索引,并以实验证明了该方法的有效性,为开发基于XML文档的WEB搜索引擎提供了一种可行的方法.     

基于后缀树思想构造Web生物数据搜索的数据模型

针对Web上的公共生物学数据资源,提出一种适合于在线搜索生物学数据的数据模型.该模型基于后缀树思想,通过建立生物体的DNA、RNA、蛋白质序列数据的后缀树结构,并将之转化为更加空间有效的后缀数组,然后搜索数组以找到查询序列的近似匹配.结果表明,这种数据模型比常规的线性搜索模型在时间和空间开销上更加高效.     

A Hybrid Algorithm for Optimizing Multi-Modal Functions

0 IntroductionThmeo rsei m epxlteen gseivneeltiyc sailngcoeri itth mw(asSG pAro)p iosse adp pbliye dJ .mHor.eH aonl-dland[1]in 1970’s . SGAis an opti mization method based onpopulation by emulating the evolvement disciplinarian of thenature.It has showedthe great advantage of quick search foropti mal solutions while applied in the opti mization of single-modal functions . But as we know many problems in realitybelong to the opti mization of multi-modal function, and ifSGAis appliedto sol…     

一种简单的变步长自适应α—LMS滤波算法

提出了一种简单的变步长α-LMS算法(vα-LMS),并给出了它的设计方法。导出了描述α-LMS算法收敛过程的动态方程,并据此讨论了α-LMS算法的算法性能。与vα-NLMS算法相比,Vα-LMS算法的优点是简单易行、计算量小,但它对输入信噪比的稳健性(RObustncss)却劣于Vα—NLMS算法。Vα-LMS算法的性能将优于Dα-LMS算法。计算机模拟结果与理论分析结果吻合较好.     

基于人工智能原理的考试系统

基于遗传算法的智能化考试系统是在传统的组卷算法基础上提出的一种新方法,用于解决应用本算法的试题模型的实际问题。     

一种基于Dijkstra的海量空间数据最短路径算法

为了解决海量空间数据的快速网络分析,在分析Dijkstra算法缺点的基础上,提出并详细介绍了一种基于Dijkstra算法的优化算法-邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,结果表明:该优化算法可以节约大量的内存,适合海量数据的网络分析.实践证明,该算法对于结点数比较大的网络具有较好的适用性.     

基于遗传算法的图像模糊边缘检测快速算法

全面分析了Pal.King模糊边缘检测算法的缺陷,提出了一种新的快速模糊边缘检测算法。该算法简化了Pal.King复杂的变换和逆变换,并采用了新的增强算子,针对Pal.King算法中对隶属度阈值的设置存在的不足,提出了利用遗传算法确定最佳隶属度阈值的方法。仿真表明,该算法检测的边缘细、连贯,适用面广,很有实用价值。     

FSFIS问题的基于随机kick的ILS&TS混合算法

提出了一种基于随机kick的迭代局域搜索算法(ILS)求解存储容量受限的流水车间问题(FSFIS)·该算法使用新颖的多对不交叉的交换移动构成kick移动,并采用回溯机制保证搜索在有利的空间内进行·通过应用4种邻域结构,每种情况下产生480组随机数据的试验证明该新型算法是快速有效的近优算法·设计了一种在原有的静态禁忌搜索算法中引入了基于随机kick的迭代局域搜索算法的混和算法,这种混合算法可以充分发挥原有的2种算法的各自优势,使目标函数进一步改进·     

时延约束的最小费用路由选择算法

如何找到效率高、性能优的路由算法成为了一个热点。QoS路由算法的实质就是求解多约束整数规划问题,这类问题通常都是NP-hard问题。针对满足两个度量的路由选择,利用Lagrange松弛和剪切网络的方法,给出了一个从源点到宿点满足给定时延门限值求解最小费用路由的启发式算法。仿真结果表明了算法是有效的。     

基于老化算法的分布式文件缓存算法

为提升数据检索读的性能, 基于老化算法采取Cache方法, 通过设计合理的缓存结构, 给出一种新的分布式文件缓存算法. 该算法在缓存实现部分, 使用了LRU算法中常用的老化算法, 并将其由一个页面置换算法改进为一个文件缓存替换算法, 且在该过程中完好地继承了老化算法的优点. 评测结果显示了改进方法的有效性.     

改进的SPECCORR方法的TDOA估计

使用SPECCORR（周期谱相关比）方法进行了多径环境下的TDOA估计。分析了该方法的可行性及它的内在局限性，给出了估计结果的正误判断标准，并提出了一种改进的SPECCORR方法－区间分割算法。模拟结果表明，改进后的方法在存在多路多径信号并且多径信号幅度较大时仍能够给出正确的TDOA估计值。     

基于数值分析理论的低复杂度MED算法

经典的最大特征值检测（MED）算法在检测相关信号时具有优异的性能.然而,随着信号维度的不断增大,MED算法面临着严重的感知判决量和判决门限计算的效率和实现问题,从而极大地限制了该算法在现代认知通信系统中的进一步应用.为此,提出了一种基于数值分析理论框架的低复杂度MED频谱感知算法.所提算法利用Rayleigh商加速幂法迭代地计算感知判决量,与经典的幂法相比,在检测高维信号时具有更快的收敛速度;此外,不同于经典的查表法,新算法基于三次样条插值法快速、准确地确定任意给定目标虚警概率所对应的感知判决门限.所提MED算法在保持原有算法检测性能的同时,有效提升了计算效率,降低了算法实现复杂度;其对于高维条件下的频谱感知问题尤其具有吸引力.最后,仿真结果证明了所提算法的有效性.