DNA fragment assembly using a grid-based genetic algorithm

In this paper we propose a genetic algorithm (GA) for solving the DNA fragment assembly problem in a computational grid. The algorithm, which is named GrEA, is a steady-state GA which uses a panmitic population, and it is based on computing parallel function evaluations in an asynchronous way. We have implemented GrEA on top of the Condor system, and we have used it to solve the DNA assembly problem. This is an NP-hard combinatorial optimization problem which is growing in importance and complexity as more research centers become involved on sequencing new genomes. While previous works on this problem have usually faced 30 K base pairs (bps) long instances, we have tackled here a 77 K bps long one to show how a grid system can move research forward. After analyzing the basic grid algorithm, we have studied the use of an improvement method to still enhance its scalability. Then, by using a grid composed of up to 150 computers, we have achieved time reductions from tens of days down to a few hours, and we have obtained near optimal solutions when solving the 77 K bps long instance (773 fragments). We conclude that our proposal is a promising approach to take advantage of a grid system to solve large DNA fragment assembly problem instances and also to learn more about grid metaheuristics as a new class of algorithms for really challenging problems.     

面向数据分析的中文问句句法研究

本文以面向数据分析为基本思想,同时结合相似度概率评估技术,实现中文问句句法分析。对于输入问句,首先需要经过词汇层与词性层以及句型和疑问词初选得到片段;然后,基于已构建的数据库,对词汇词性序列的子序列搜索片段,进行片段组合;最后,对输入语句与初选结果进行相似性评估,完成输入语句的组合分析过程。为论证方法有效性,基于200句山西旅游问句做实验。实验结果表明,句法分析的准确率达到96%。     

共享片段自动检测模型

提出了一种可扩展的共享片段自动检测算法,介绍了共享片段自动检测模型的结构和实现方法。该模型可在线运行自动检测算法,将流行度高的网页集合作为检测对象。实验和分析表明,该模型在保证准确率的前提下,能检测出网页集合的最大共享片段集合,提高检测效率。     

基于流场的爆炸分裂效果模拟

通过分析冲击波气流的运动特点,对Navier-Stokes方程进行合理简化。根据简化后的方程所反映出的气流速度变化规律,提出描述冲击波气流运动的扩散模型。基于该模型所定义的流场,对碎片的运动进行控制,实现对冲击波作用下物体碎片飞散效果的模拟。实验结果表明,该方法具有较强的真实感,能够满足实时性要求。     

DNA片段拼接中的预归并重复序列屏蔽方法

针对DNA片段拼接中的重复序列识别及屏蔽问题,提出一种预归并重复序列屏蔽方法。在片段拼接前通过扫描子串标识出可能存在重叠关系的shotgun片段,利用子串归并该相关片段,标识出重复序列的位置信息,达到屏蔽的目的。计算机模拟分析表明,该方法识别重复序列的错误率低,通过预归并有效缩减了shotgun集合的规模,降低了拼接时的计算复杂度。     

Axiomatizing the Monodic Fragment of

As we can show that the two-variable monadic fragment of thefull first-order extension of the propositional branching time logic is not recursively enumerable, we show in thisarticle that the monodic fragment of can be axiomatized.     

藏文自动分词中未登录词处理方法研究

藏文中后接成份出现频率较高,分词中未登录词的后缀单切现象会影响分词的正确率,为此,采用词(语素)+缀归并的方法,将藏文后接成份与前一词(语素)归并为一个切分单位输出。针对藏文中大量人名、地名、单位名等未登录词在分词时出现的碎片切分现象,使用分词碎片整合方法,将多次出现的词条碎片整合为一个切分单位输出。实验结果表明,2种方法能提高藏文自动分词的识别正确率。     

反舰导弹攻击舰船舷侧防护结构过程数值仿真

半穿甲内爆式反舰导弹战斗部对舰船的攻击过程中使用了穿甲效应、爆炸破片效应和爆炸冲击波效应.在研究舰船结构在这种战斗部攻击下的响应和破损时应考虑此3种效应的耦合作用,而目前在这方面只有单独考虑某一效应的研究.该文将一种基于FCT算法的高精度爆炸流体动力学程序与LS DYNA动力学有限元软件相连接,同时考虑了穿甲、爆炸破片和爆炸冲击波的耦合作用,对半穿甲内爆式反舰导弹攻击下舰船舷侧防护结构的响应与破损全过程进行了数值模拟仿真.结果表明该数值仿真方法行之有效.     

BitTorrent类型P2P系统模型研究与性能分析

对BitTorrent（BT）类型的P2P系统进行了建模与性能分析。详细地分析了系统中的peer行为。考虑到文件片段对系统的影响，建立了peer模型和seed模型以及文件片段模型、感兴趣与阻塞模型、peer选择模型等。对peer在BT子系统中对邻居peer的感兴趣概率、被邻居peer阻塞的概率以及选择上传peer的概率进行了分析。应用这个模型对peer的上传行为发生的概率与BT子系统peer总数的关系进行了分析, 结果表明, 上传行为发生的概率随着BT子系统peer总数的增加而减少。