DNA片段拼接中重复序列算法研究

本文主要研究DNA片断拼接中重复序列信息识别算法。包含大量重复信息的DNA序列,其重构是大规模DNA片段拼接所面临的实际困难之一。针对目前大多数拼接算法对于重复段的处理采用效率较低的反复迭代算法的特点,提出了基于k-mer子串的重复段分析方法,充分考虑了拼接中可能的分割点,设计与分析了识别重复序列并提高序列一致性的高效算法。     

一种基于前缀编码的树生成算法

为了使树生成算法更为通用且效率更高,提出一种基于前缀编码的树生成算法.算法中的节点采用前缀编码的数据结构,便于用户对树中节点及其下层子节点上的关联数据进行快速查询和统计.由于在构造树之前已采用先根遍历的方式对节点进行了排序,同时建树过程中记录了最近各层节点的信息,因此无需搜索节点的上下层信息就可直接建立起树,大幅提高了建树效率,算法时间复杂度为O(n).该算法无需额外的数据预处理即可构造任意子树,且不会增加算法复杂度.     

基于裁剪的弱硬实时调度算法

针对当前弱硬实时调度算法无法保证超过窗口长度的执行序列的满足率达到一定比例的问题,基于(m~-,p)弱硬实时约束,提出了一种基于裁剪的调度算法(cut-down based scheduling,简称CDBS).由于判断(m~-,p)约束是否满足需要遍历任务的整个执行序列,因此判断复杂度很大.为此,提出一种高效的裁剪执行序列的算法,同时证明其正确性,并利用适当的数据结构,使得计算复杂度与序列长度无关,通过实验说明其降低计算复杂度的有效性.进一步与其他经典实时调度算法(EDF(earliest deadline first),DBP(distance-based priority),DWCS(dynamic window constraint schedule))进行比较,验证该算法与其他算法具有相当的性能.     

一种优化的生物序列比对算法

序列比对是生物信息学中一种基本的信息处理方法,在序列比对所使用的算法中当前重点解决的问题是如何降低算法的时间和空间复杂度。在介绍基本动态规划原理的基础上,提出了一种基于动态规划思想的优化序列比对算法。对3种算法对比实验表明,该算法在保证其生物敏感性的基础上,有效地降低了时间和空间复杂度。     

从中序遍历及后序遍历构造二叉树

本文给出了一个算法，该算法输入一棵二叉树的中序遍历和后序遍历的结点序列，构造出该二叉树。该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数。     

生物信息学中一个优化的全局双序列比对算法

最早的生物信息学中序列比对算法是基于动态规划思想的Needleman-Wunsch全局双序列比对算法,由于其时间和空间复杂度巨大,不适合实际的生物序列比对.提出了一种优化的基于动态规划思想的全局双序列比对算法.实验结果表明,该算法在保证其生物敏感性的基础上,有效地降低了时间和空间复杂度.     

基于EREW的后序遍历二叉树算法

针对单处理器后序遍历二叉树的时间复杂度为O（n）问题,提出了在EREW PRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。得出了运用该算法将时间复杂度从O（n）减少到O（logn）的结论。     

DNA序列拼接中de Bruijn图结构的研究

基因组测序是生物信息学中最基本的研究方向之一,然而大多数生物的基因组都不可能一次性获得,需要利用序列拼接技术对实验中获得的DNA片段进行拼接操作.目前,测序过程中获得的DNA片段越来越短,基于Euler路径的拼接算法在处理这种短片段拼按时具有优势.在Euler路径算法中,一个关键的步骤是de Bruijn图的构建,一直以来,构建de Bruijn图的方式总是让后一个k-mer与前一个k-mer 之间有k-1个碱基的交叠,相邻的两个k-mer之间相互错开一位.但文中的研究发现,如果有边连接的两个k-mer之间有k-2个或者更少的碱基相交叠,会对de Bruijn图结构复杂性产生重要影响.针对这些影响进行详细分析,并设计实验进行验证,实验结果表明,k-mer之间的错位数变化对de Bruijn图结构复杂性有显著影响.     

基于分支定界的动态树形搜索反碰撞算法

针对RFID系统中最常见的反碰撞问题,论文提出了一种基于分支定界的动态树形搜索反碰撞算法,算法采用分支定界的树形搜索机理,动态调整指令发送长度和发送值,并对一位碰撞进行智能识别.最后利用树的遍历思想予以实现,该算法能高效地识别所有标签,时间复杂度低,在RFID领域有较好的应用前景.     

生物信息挖掘中LIS算法研究*

探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了实现,验证了时间和空间复杂性理论分析的正确性,最后得出了一种高效的LIS算法。     

k-长DNA子序列计数算法研究

基因组的结构与功能存在密切联系，其功能主要通过DNA子序列来表达，因此研究DNA序列结构对于生物信息学来说具有重要的意义。该文研究了k-长DNA子序列在DNA全序列中出现频数的计数问题，设计并实现了k-长DNA子序列内部计数算法和外部计数算法。该算法通过一个哈希函数把k-长DNA子序列映射为整数关键字从而把k-长DNA子序列出现频数的计数问题转化为整数关键字的重复计数问题，使得能够利用经典B树算法来解决k-长DNA子序列的出现频数计数问题。针对所要解决的问题提出3种改进措施以进一步提高算法的性能。     

六元一阶相关免疫函数的新计数算法

若布尔函数的输出不泄漏其输入值的有关信息,则该函数是相关免疫的。该文基于列平衡矩阵研究相关免疫函数的计数问题,利用穷举和统计相结合的方法对2k×6(0≤k≤16)阶定序列平衡矩阵进行计数,给出一种新的六元一阶相关免疫函数的计数算法。与同类算法相比,新算法的复杂度降为(224),大大提高了一阶相关免疫函数的计数效率。     

构造给定k错线性复杂度谱的2~n周期序列

k错线性复杂度是度量序列密码安全性的重要指标之一。基于方体理论和Games-Chan算法的逆向推导提出构造方法,构造了具有给定k错线性复杂度谱的2n周期序列。首先使用标准方体分解算法对k错线性复杂度具有第一下降点k=2、第二下降点k′=6、第三下降点k″=10的2n周期序列进行分类,再讨论每一类序列下降点线性复杂度参数之间的关系,最后给出每种参数关系下序列的计数公式以及构造过程。事实上,所使用的方法可以用于构造具有更多下降点的2n周期序列。     

基于MapReduce的并行频繁项集挖掘算法研究

针对并行MRPrePost(parallel prepost algorithm based on MapReduce)频繁项集挖掘算法在大数据环境存在运行时间长、内存占用量大和节点负载不均衡的问题,提出一种基于DiffNodeset的并行频繁项集挖掘算法(parallel frequent itemsets mining using DiffNodeset,PFIMD).该算法首先采用一种数据结构DiffNodeset,有效地避免了N-list基数过大的问题;此外提出一种双向比较策略(2-way comparison strategy,T-wcs),以减少两个DiffNod-eset在连接过程中的无效计算,极大地降低了算法时间复杂度;最后考虑到集群负载对并行算法效率的影响,进一步提出了一种基于动态分组的负载均衡策略(load balancing strategy based on dynamic grouping,LBSBDG),该策略通过将频繁1项集F-list中的每项进行均匀分组,降低了集群中每个计算节点上PPC-Tree树的规模,进而减少了先序后序遍历PPC-Tree树所需的时间.实验结果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果.     

二叉树遍历的通用递归算法研究与实现

对二叉树先序遍历、中序遍历和后序遍历递归算法进行了分析,给出了三种遍历方法的通用递归算法。该算法只需对二叉树遍历一次,对每个结点的值域（Data）访问三次即可求出三种遍历序列。     

二叉树遍历的通用递归算法研究与实现

对二叉树先序遍历、中序遍历和后序遍历递归算法进行了分析,给出了三种遍历方法的通用递归算法。该算法只需对二叉树遍历一次,对每个结点的值域(Data)访问三次即可求出三种遍历序列。     

基于H.264的立体视频压缩中的快速帧间模式选择算法*

为了在保证PSNR和bitrate的基础上,提高立体视频编码的速度,首先,对立体视频序列各模式进行统计分析,然后进行快速帧间模式选择算法的比对,并最终确定使用基于图像细节程度的快速帧间模式选择算法进行编码。实验结果表明,在图像质量和压缩效率基本不变的情况下,大幅度提高了H.264立体视频编码的速度。     

基于Spark并行的密度峰值聚类算法

针对FSDP聚类算法在计算数据对象的局部密度与最小距离时,由于需要遍历整个数据集而导致算法的整体时间复杂度较高的问题,提出了一种基于Spark的并行FSDP聚类算法SFSDP。首先,通过空间网格划分将待聚类数据集划分成多个数据量相对均衡的数据分区;然后,利用改进的FSDP聚类算法并行地对各个分区内的数据执行聚类分析;最后,通过将分区间的局部簇集合并,生成全局簇集。实验结果表明,SFSDP与FSDP算法相比能够有效地进行大规模数据集的聚类分析,并且算法在准确性和扩展性方面都有很好的表现。     

A Fast Token-Chasing Mutual Exclusion Algorithm in Arbitrary Network Topologies

We present a simple and efficient mutual exclusion algorithm whose optimal message passing complexity isO(N), whereNis the number of processors in the network. The message complexity is measured by counting the number of communication hops in a network for a given topology. This algorithm reduces its message passing complexity by a token-chasing method, and enhances its effectiveness by dynamically adjusting state information stored in each processor. Moreover, this algorithm shortens the request delay by fully taking advantage of the network dynamic status information. The performance of the algorithm is also modeled for analytical evaluation. We have conducted a group of experiments on a network of workstations for comparisons between our algorithm and two other existing mutual exclusion algorithms. The experimental results show the effectiveness of our algorithm, especially when a large number of requests access the critical region in a distributed system. Finally, the token-chasing algorithm is further enhanced for fault tolerance under message loss and link crash conditions.     

A Bayesian plan-view map based approach for multiple-person detection and tracking

This work proposes a novel approach for people detection and tracking in colour-with-depth sequences using a particle filtering approach. Detection and tracking are performed in plan-view maps integrating occupancy and height information with a novel plan-view map representation for colour information. Using the three maps, we propose a multiple particle filtering algorithm for people detection and tracking. The observation model proposed integrates information from the three maps so that people with different coloured clothes are not confused even when they interact at close distances. To avoid the coalescence problem when people with similar coloured clothes approach each other, the weight of particles is modified by an interaction factor that combines colour and position information. The algorithm also avoids the coalescence problem in case of total occlusion by means of an occlusion detection and recovering mechanism. Finally, a solution is proposed to improve the exponential complexity of multiple particle filters so that the algorithm proposed has linear complexity.The approach proposed has been tested in several colour-with-depth sequences where people move and interact freely in the environment. In the sequences, people walk at different distances, cross their paths causing frequent occlusions, jump, run and have close interactions such as shaking hands or embracing each other. The experimental results show that our proposal is able to detect and keep track of every person with a low error and deals with partial and total occlusions. Besides, the detection and tracking techniques presented are appropriate for large tracking problems in real-time applications since their complexity is linear, are suitable for parallel processing and allow the integration of information provided by multiple stereo vision sensors.