DNA序列中基于适应性后缀树的重复体识别算法

现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致.     

基于K-D树的多维数据分布方法

系统地介绍了基于并行化k-d树的多维数据分布方法。给出了几种构造k-d树的策 略和相应算法，并从理论上分析和比较了各种策略的通信花费及其应用范围。     

自适应蚁群算法在序列比对中的应用

序列比对是生物信息学的重要研究工具。蚁群算法是一种新型的模拟进化算法,并被成功地应用于旅行商问题(TSP)等组合优化问题中。该文将蚁群算法应用于序列比对,并提出基于自适应调整信息素的改进算法。仿真结果表明这种新的比对算法是有效的,而它的改进算法的效果更为理想。     

超立方体上所有点对之间的最短路径

超立方体上所有点对之间的最短路径霍红卫，庄心谷（西安电子科技大学计算机科学系西安７１００７１）ＡＬＬＰＡＩＲＳＳＨＯＲＴＥＳＴＰＡＴＨＳＯＮＡＨＹＰＥＲＣＵＢＥＭＵＬＴＩＰＲＯＣＥＳＳＯＲ￥ＨｕｏＨｏｎｇｗｅｉａｎｄＺｈｕａｎｇＸｉｎｇｕ（Ｄｅｐａｒ...     

快速排序算法研究

排序是计算机科学中最重要的研究问题之一，2000年被列为20世纪对科学和工程计算的研究与实践影响最大的10大问题之一。文章介绍了基本的快速排序算法及三种枢轴元素的选取方法，全面深入地分析了快速排序算法最坏情况下的时间复杂度，平均情况下的时间复杂度，随机情况下的时间复杂度，并对快速排序算法和堆排序算法进行了比较，理论和实验结果表明，快速排序算法仍然是目前最好的排序算法之一。     

基于高阶逻辑的硬件验证方法

本文讨论了如何利用高阶逻辑描述硬件的行为及结构，提出了硬件验证的一般方法，高阶逻辑不仅可以作为一种描述语言用来描述硬件的行为及结构，而且可以作为证明系统用来验证硬件设计的正确性。文中给出的用以说明描述及验证的例子包括ＣＭＯＳ反相器、复位的奇偶校验器。     

算法到脉动阵列处理器的映射

文中讨论了将含有循环的算法映射到脉动阵列的一般方法。这一映射方法是建立在下标集和数据相关向量的数学变换基础上，并给出了带有常数据相关的算法中存在有效变换的充要条件。最后给出了许所有点对之间最短路径问题的映射过程。     

生物序列模体的混合Gibbs抽样识别算法

针对生物序列模体的识别问题,提出了一个新的混合Gibbs抽样识别算法.算法基于混合模体模型学习,采用贪心策略,通过似然度最大化,逐次将新的模体加入到混合模型中.算法中设计了位点抽样和模体抽样两种抽样方法,这两种抽样方法交替进行.为了加速搜索过程,对输入数据集采用了基于kd-trees的分层划分策略.实验结果表明,该算法对序列家族大量模体特征的识别具有显著优势,并且可建立更具统计特征的模体模型,从而提高序列分类的准确性.     

基于最大权值路径算法的DNA多序列比对方法

针对生物序列分析中的多序列比对问题,当输入数据量比较大时,人们提出了很多启发式的算法来改善计算速度和比对结果.提出了用于进行全局DNA多序列比对的一种方法:MWPAlign(maximum weighted path alignment).该算法把序列信息用de Bruijn图的形式表示,并将输入序列的信息记录在图的边上,这样,就将求调和序列的问题转化为求图的最大权值路径问题,使多序列比对问题的时间复杂度降低到几乎线性.实验结果显示:MWPAlign是可行的多序列比对算法,尤其对于变异率低于5.2%的大量序列数据,相对于CLUSTALW(cluster alignments weight),T-Coffee和HMMT(hidden Markov model training)有较好的比对结果和运算性能.     

超立方体上0／1背包问题的并行算法

文中提出了在超立方体计算机上解０／１背包问题的并行算法。如果Ｐ表示超立方体上处理器地的数目，Ｔ是在一个处理器上解决给定问题所需要的时间，那私这一算法的时间特性为）（Ｔ／Ｐ）。