DNA序列中弱信号基序查找算法比较与分析

在DNA序列中查找基序是生物信息学中一个重要的计算问题,人们针对这一计算问题提出了多种模型和算法.由于DNA序列数据的复杂性,在其中有许多是比强信号基序更难提取的弱信号基序.而目前植入(ι,d)基序问题(PMP)和扩展植入(ι,d)基序问题(EMP)是较适合模拟弱信号基序查找的问题模型.本文归纳分析了基序查找的基本方法、策略和基序模型,指出了各种策略和模型的优势与不足.在此基础上对现有的基于植入基序查找问题模型的主要弱信号基序查找算法进行了分析和实验评估,为选择计算方法查找弱基序信号提供了参考,并讨论了该方向上尚未解决的问题和发展趋势.     

有效网络资源查找技术研究

分布式非结构化对等网络查找算法近年来正在成为研究的热点,但已有的算法在查找性能方面需要进一步提高.低查找效率会限制当前非结构化对等网络系统的查找可扩展性.本文中,我们提出了一种叫做前向察觉算法,它分别建立了两种覆盖方式,邻居覆盖和朋友覆盖.通过结合两种覆盖方式的优点,以较小的负载代价,明显提高了网络查找性能.     

基于OLPP符号表示的时间序列分类算法

基于符号表示的时间序列分类方法是时间序列数据挖掘的关键技术。大部分现有方法主要针对单个时间序列样本进行符号表示,没有考虑样本间的近邻关系对符号化分类的影响。对此提出一种基于正交局部保持映射(Orthogonal Locality Preserving Projection,OLPP)的时间序列符号表示方法。使用OLPP对原始数据集进行维数约减,利用信息增益寻找维数约减后数据的最佳符号投影区间,采用多重系数分箱技术(Multiple Coefficient Binning,MCB)将降维后数据表示成符号序列。该算法在20个时间序列数据集上的分类效果好于已有方法,有效利用样本间的近邻关系能够显著提高算法的分类性能。     

Web访问序列模式挖掘算法的研究

针对现有Web访问序列模式挖掘算法和PrefixSpan算法存在的问题,提出一种基于投影位置的Web访问序列模式挖掘算法(PWSPM)。该算法通过序列模式分析,发现用户的行为模式,预测用户对网页的访问模式,进而改进站点的性能和组织结构,提高用户查找信息的质量和效率,以及对用户开展个性化的信息服务。实验和应用结果表明,提出的算法具有更好的执行效率,适用于Web日志挖掘,可用于构建智能化Web站点和解决个性化的信息服务问题。     

基于粒子群优化算法和UniformLBP特征的分块跟踪

针对鲁棒分块跟踪采用穷举的搜索策略以及对光照敏感等问题,提出了一种基于粒子群优化算法和Uniform LBP特征的分块跟踪方法。利用统一的局部二值模式(Uniform Local Binary Pattern)特征对光照的不变性以及计算效率高的特点,在原鲁棒分块跟踪方法以灰度积分直方图作为特征的基础上,添加了Uniform LBP特征;利用粒子群优化算法具有精度高,收敛快的特点,将PSO算法运用到对候选目标的搜索中。实验结果表明,在不降低算法运行速度的情况下,以及光照变化较大,短时间目标完全遮挡的跟踪环境下,该算法鲁棒性显著增强。     

桌面网格计算平台在多序列比对算法中的运用

提出了一种多序列比对ClustalW算法并行化处理的新方法ParaClustalW,该方法使用桌面网格计算平台作为高性能编程环境和运行平台.分析了多序列比对算法在桌面网格平台上的任务划分方式、并行化策略和实现技术.ParaClustalW策略考虑到序列的数目与序列的长度等因素,实现任务划分的均衡性.经实验证明,Para...     

网格资源查找方法的分析与比较

在网格环境下,如何快速进行资源查找定位是影响网格性能和QoS的重要因素.本文分析了目前已有的两种用于网格资源发现的资源查找算法(集中式查找算法、分布式查找算法)的优劣,并参照网络路由器的路由转发策略,提出了改进的基于路由转发的资源查找算法.     

基于CPRIP—Tree的伴生模式挖掘算法

现有的大多数空间伴生模式挖掘算法采用类似Apriori生成方法,通过自底向上,逐层检验的方式挖掘频繁模式。本文提出了一种新的基于伴生模式行实例投影树CPRIP—Tree（Co—location Pattern Row_Instance Projection Tree）的挖掘算法,该算法通过实例查找方式生成伴生模式行实例以构建CPRIP—Tree,并在其基础上上直接挖掘频繁模式。最后通过模拟数据实例分析证明了该算法较基于Apriori算法具有更高的挖掘效率。     

基于分割的字符串相似性查找算法

字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找。目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的。基于该框架提出了PBsearch算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数。在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法。其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模。最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性。     

投影深度向量分解融合PEMS的视角不变人体动作识别

针对摄像机内部参数的不确定性和投影平面选择难的问题,提出一种新的投影深度算法用于视角不变的动作识别,该算法采用对称镜面提取平面(PEMS)策略,有效解决了投影平面选择难的问题。首先通过摄像机组观察获得3D动作姿势,然后运用PEMS策略从场景中提取平面,相对于提取平面估计身体点的投影深度,最后使用这个信息进行动作识别。该算法的核心是投影平面的提取和投影深度组成向量的求解。利用本文算法在CMU MoCap数据集、TUM数据集和多视图IXMAS数据集上进行测试,精度可分别高达94%、91%和90%,且在较少动作实例情况下,仍然能够准确定义新动作。比较表明,本文算法的人体动作识别性能明显优于其他几种较新的算法。     

Compressed Hierarchical Mining of Frequent Closed Patterns from Dense Data Sets

This paper addresses the problem of finding frequent closed patterns (FCPs) from very dense data sets. We introduce two compressed hierarchical FCP mining algorithms: C-Miner and B-Miner. The two algorithms compress the original mining space, hierarchically partition the whole mining task into independent subtasks, and mine each subtask progressively. The two algorithms adopt different task partitioning strategies: C-Miner partitions the mining task based on Compact Matrix Division, whereas B-Miner partitions the task based on Base Rows Projection. The compressed hierarchical mining algorithms enhance the mining efficiency and facilitate a progressive refinement of results. Moreover, because the subtasks can be mined independently, C-Miner and B-Miner can be readily paralleled without incurring significant communication overhead. We have implemented C-Miner and B-Miner, and our performance study on synthetic data sets and real dense microarray data sets shows their effectiveness over existing schemes. We also report experimental results on parallel versions of these two methods.     

2维最大类间平均离差阈值选取快速递推算法

阈值分割是广泛使用的最为有效的图像分割方法之一。阈值选取是阈值分割的关键。Otsu提出的基于L2范数的最大类间方差法是备受关注的一种方法,而基于L1范数的最大类间平均离差法则更为简捷,效果很好。2维最大类间平均离差阈值选取方法分割精确、抗噪性能好,其效果优于2维最大类间方差法,但存在计算量大、难以实用等缺点。提出了2维最大类间平均离差阈值选取的两种不同的快速递推算法,都可将计算复杂性由O(L4)减少为O(L2)。给出了2维最大类间平均离差两种快速递推算法的分割结果及运行时间,并与原始算法及原有的快速算法进行了分析和比较。实验结果表明,这两种递推算法都可以大幅度地提高运算速度,运行时间可减少到原始算法的0.1%,使2维最大类间平均离差阈值分割方法更为实用,目前已被应用于红外目标、车牌、指纹等自动识别系统中。     

基于LPP的工业过程故障检测

针对传统的降维算法在降维过程中存在着丢失数据的局部邻域信息的问题,一种基于局部保持投影(LPP)用于工业工程数据检测的方法被应用。LPP算法的思想是通过构造数据样本点之间的亲疏关系,并且在投影降维的同时保留数据样本点的这种局部邻域结构,从而保留数据的局部信息。论文将LPP算法与传统的降维算法-主元分析法(P CA)在田纳西-伊斯曼过程(T EP)仿真系统上进行检测对比,结果表明,LPP算法具有更加优越的检测性能。     

一种基于双端队列的交通网络最短路径Pallottino优化算法

最短路径算法是计算机科学与地理信息科学领域的研究热点，而标号算法则是最短路径算法中的重要一族。长期以来，对于最短路径的算法实现，绝大多数都是围绕以Dijkstra算法为核心的标号设定算法来展开，而对标号改正算法的研究与应用却非常少见。为了对交通网络最短路径进行更有效、更快速的计算，通过对标号改正算法思想的深入分析，针对其中最具代表性的Pallottino算法，从存储结构和运行结构两方面进行了算法的优化改进，同时分析了该算法的时间复杂度和空间复杂度，并利用实际的大规模城市交通网络进行了效率测试。结果显示，与目前公认最优的标号设定算法中基于逼近桶结构的Dijkstra算法相比，该改进的标号改正Pallottino算法具有更好的适用性和更高的运行效率，因此在交通网络最短路径分析应用中具有很高的应用价值。     

基于项目属性和项目度的BGPR算法

传统二部图投影和排序(BGPR)算法的推荐精度不高。为此,提出一种基于项目属性和项目度的BGPR算法。分析二部图投影和随机游走的特点,引入项目属性和项目度2个影响因子,通过对初始化向量和项目相似性的优化,设计个性化推荐算法。实验结果表明,该算法的推荐精度较高。     

基于混合梯度的硬阈值追踪算法

针对压缩感知（CS）中迭代硬阈值类算法迭代次数多、重构时间长的问题,提出了一种基于混合梯度的硬阈值追踪（HGHTP）算法。首先,在每次迭代中计算当前迭代点处的梯度和共轭梯度,将梯度域与共轭梯度域下的支撑集混合取并集作为下一次迭代的候选支撑集,充分利用共轭梯度在支撑集选择策略中的有用信息,优化支撑集选择策略;然后,采用最小二乘法对候选支撑集进行二次筛选,快速精确地定位正确的支撑并更新稀疏系数。一维随机信号重构实验结果表明,HGHTP算法相较于同类迭代硬阈值算法,在保证重构成功率的前提下,需要的迭代次数更少。二维图像重构实验结果表明,HGHTP算法的重构精度和抗噪性能优于同类迭代阈值类算法,在保证重构精度的情况下,HGHTP算法的重构时间相比同类算法减少了32%以上。     

Gray level difference-based transition region extraction and thresholding

Thresholding method based on transition region is a newly developed approach for image segmentation in recent years. In this paper, a novel transition region extraction and thresholding method based on gray level difference is proposed by analyzing properties of transition region. The gray level difference can effectively represent the essence of transition region. Hence, the proposed algorithm can accurately extract transition region of an image and get ideal segmentation result. The proposed algorithm was compared with two classic transition region-based methods on a variety of synthetic and real world images, and the experimental results show the effectiveness and efficiency of the algorithm.     

Multistart Iterated Tabu Search for Bandwidth Coloring Problem

This paper presents a Multistart Iterated Tabu Search (MITS) algorithm for solving Bandwidth Coloring Problem (BCP) and Bandwidth MultiColoring Problem (BMCP). The proposed MITS algorithm exhibits several distinguishing features, such as integrating an Iterated Tabu Search (ITS) algorithm with a multistart method and a problem specific perturbation operator. Tested on two sets of 66 public benchmark instances widely used in the literature, the MITS algorithm achieves highly competitive results compared with the best performing algorithms, improving the previous best known results for 22 instances while matching the previous best known results for 39 ones. Furthermore, two important features of the proposed algorithm are analyzed.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

Implementation and Complexity of the Watershed-from-Markers Algorithm Computed as a Minimal Cost Forest

The watershed algorithm belongs to classical algorithms in mathematical morphology. Lotufo et al. ¹ published a principle of the watershed computation by means of an iterative forest transform (IFT), which computes a shortest path forest from given markers. The algorithm itself was described for a 2D case (image) without a detailed discussion of its computation and memory demands for real datasets.
As IFT cleverly solves the problem of plateaus and as it gives precise results when thin objects have to be segmented, it is obvious to use this algorithm for 3D datasets taking in mind the minimizing of a higher memory consumption for the 3D case without loosing low asymptotical time complexity of O ( m + C )(and also the real computation speed). The main goal of this paper is an implementation of the IFT algorithm with a priority queue with buckets and careful tuning of this implementation to reach as minimal memory consumption as possible.
The paper presents five possible modifications and methods of implementation of the IFT algorithm. All presented implementations keep the time complexity of the standard priority queue with buckets but the best one minimizes the costly memory allocation and needs only 19–45% of memory for typical 3D medical imaging datasets.
Memory saving was reached by an IFT algorithm simplification, which stores more elements in temporary structures but these elements are simpler and thus need less memory.The best presented modification allows segmentation of large 3D medical datasets (up to 512 × 512 × 680 voxels) with 12- or 16-bits per voxel on currently available PC based workstations.