Exact enumeration of three-dimensional lattice proteins

We present an algorithm for the exhaustive enumeration of all monomer sequences and conformations of short lattice proteins as described by the hydrophobic-polar (HP) model. The algorithm is used for an exact identification of all designing sequences of HP proteins consisting of up to 19 monomers whose conformations are represented by interacting self-avoiding walks on the simple cubic lattice. Employing a parallelized implementation on a Linux cluster, we generate the complete set of contact maps of such walks.     

Enumerating syntactical graphs and lattices of derivations

Derivations in phrase-structure grammars are by now well understood, and it is generally considered convenient to study equivalence classes of derivations rather than individual derivations themselves. It has been established that classes can be represented by canonical derivations, syntactical graphs, or derivation words, and the categorical algebra of derivations provides the framework for their study. Regarded in this way, it is known that each derivation induces a distributive lattice of subderivations. In this paper a simple algorithm is given for enumerating this lattice for any derivation. The simplicity of this algorithm depends on the nature of the topological sort which allows a canonical derivation (or derivation word) to be constructed uniquely from a syntactical graph. The enumeration algorithm constructs the members of the lattice directly. In the process a new characterization of the syntactical graphs is given using the concept of a doubly ordered graph. This characterization greatly simplifies some of the previous work in this field. A direct correspondence between these graphs and the symmetric group (set of permutations) is shown.     

格子模型的序列搜索优化算法

在格子模型的穷举搜索算法中，限制大尺寸模型搜索的主要障碍在于计算规模．通过Gray码的调序，相邻的HP序列仅有一个码位不同，利用这一相邻性特征，将原来N次的计算量减少到一次N．同时我们按照Gray码序的二分演化特征构造了链表这种数据结构．经理论分析以及实验验证，该快速Gray码搜索算法利用Gray码特性可使算法达到线性加速比N，同时也极大的减少了所需存储空间．     

Retailoring Box Splines to Lattices for Highly Isotropic Volume Representations

3D box splines are defined by convolving a 1D box function with itself along different directions. In volume visualization, box splines are mainly used as reconstruction kernels that are easy to adapt to various sampling lattices, such as the Cartesian Cubic (CC), Body‐Centered Cubic (BCC), and Face‐Centered Cubic (FCC) lattices. The usual way of tailoring a box spline to a specific lattice is to span the box spline by exactly those principal directions that span the lattice itself. However, in this case, the preferred directions of the box spline and the lattice are the same, amplifying the anisotropic effects of each other. This leads to an anisotropic volume representation with strongly preferred directions. Therefore, in this paper, we retailor box splines to lattices such that the sets of vectors that span the box spline and the lattice are disjoint sets. As the preferred directions of the box spline and the lattice compensate each other, a more isotropic volume representation can be achieved. We demonstrate this by comparing different combinations of box splines and lattices concerning their anisotropic behavior in tomographic reconstruction and volume visualization.     

结合轴对齐包围盒和空间划分的碰撞检测算法

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。     

A label-setting algorithm for finding a quickest path

The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate non-dominated paths with distinct capacity, and then determine a quickest path by comparing their transmission time. In this paper, we propose a label-setting algorithm for finding a quickest path by transforming a network to another network where an important property holds that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-dominated paths whose transmission time is greater than the minimum transmission time. Although the computational complexity of the proposed algorithm is the same as that of existing algorithms, experimental results show that our algorithm is efficient when a network has two or more non-dominated paths.     

用于求解路径交通流量的改进Frank-Wolfe算法

Frank-Wolfe算法是用于求解交通流量分配问题的经典算法,但该算法是基于路段（Link-Based）的交通流量分配算法,无法用于求解路径交通流量。针对此问题,提出一种用于求解路径交通量的改进Frank-Wolfe算法。通过在Frank-Wolfe原算法中增加求解路径交通流量的计算步骤,根据原算法中“全有全无”加载方法获得的步长,更新源-目的（OD）间所有已配流的路径的交通流量,在原算法迭代计算路段流量的同时,同步计算路径流量。通过算例表明,改进算法是一个有效的算法,在Frank-Wolfe原算法的基础上增加少量的时间和空间成本即可求解路径交通流量,避免穷举交通网络中的所有路径,可以很好地用于用户均衡交通流量分配中。     

一种模糊概念格构造算法研究

基于有限L_背景的模糊格在扩展和时空复杂度上有局限。该文定义了广义的模糊概念格和其上的截运算以简化格构造,提出了一种模糊格构造算法。在概念格结点级上定义了两个模糊参数α和δ粎,以避免提取因高偏差导致的无效规则。给出一个实例,说明了从模糊概念格提取不确定规则、计算规则支持度、置信度的原则、方法。实现了构造算法与Godin算法的对比实验,结果表明本算法在时空性能上要优于Godin算法。     

基于构造性形态学神经网络的一种提升算法

构造性形态学神经网络算法（CMNN）是一种数学形态学与传统的神经网络模型相结合的一种非线性神经网络,有较强的实用性。其训练算法根据形态学联想记忆而来,在测试过程中采用形态学算子将测试样本归类于训练得到的超盒之中。由于其测试过程无法正确地将落在超盒外的样本进行分类,后有人提出了一种基于模糊格的形态学神经网络（FL-CMNN）,该算法用样本与超盒的隶属度判断提高了原CMNN算法的分类效果,但增加了算法的复杂程度且分类效果不稳定。这里提出一种基于构造性形态学神经网络算法的提升算法（LCMNN）,该算法继承了原有的形态学算子运算速度快的优点且能够将落在超盒之外的样本进行准确地归类。数值实验表明,基于构造性形态学神经网络算法的提升算法（LCMNN）与其他几种算法相比,能够达到最好的分类效果,而且简单易行,计算时间少。     

基于拓扑映射的点集在凸多边形内外判断算法

通过拓扑映射 ,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题 .首先通过设置中心点 ,获取凸多边形各顶点的拓扑映射点 ,对于每个检测点 ,根据其映射点与顶点拓扑映射点的相对位置关系 ,即可确定检测点位于多边形哪条边的范围内 ;然后将检测点与该边进行包围盒测试 ,对于点在边包围盒外的情况 ,只需根据比较判别即可得到结果 ,对于点在边包围盒边界上或内部的情况 ,则需通过叉积运算进行判别 .该方法几何意义清晰 ,实验结果表明 ,该算法运行可靠 ,对于单个点或多点组成的点集均有较高的检测速度 .     

Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic-polar model and cubic lattice

This paper presents a genetic algorithm applied to the protein structure prediction in a hydrophobic-polar model on a cubic lattice. The proposed genetic algorithm is extended with crowding, clustering, repair, local search and opposition-based mechanisms. The crowding is responsible for maintaining the good solutions to the end of the evolutionary process while the clustering is used to divide a whole population into a number of subpopulations that can locate different good solutions. The repair mechanism transforms infeasible solutions to feasible solutions that do not occupy the lattice point for more than one monomer. In order to improve convergence speed the algorithm uses local search. This mechanism improves the quality of conformations with the local movement of one or two consecutive monomers through the entire conformation. The opposition-based mechanism is introduced to transform conformations to the opposite direction. In this way the algorithm easily improves good solutions on both sides of the sequence. The proposed algorithm was tested on a number of well-known hydrophobic-polar sequences. The obtained results show that the mechanisms employed improve the algorithm's performance and that our algorithm is superior to other state-of-the-art evolutionary and swarm algorithms.     

一种区间值模糊概念格构造方法研究

在区间值模糊形式背景基础上,定义截运算以简化概念格的构造,从而得到区间值模糊概念格.文中给出了区间值模糊概念格构造算法,结合实例进行说明,最后求出了对应的模糊概念格.     

Algorithm optimization in molecular dynamics simulation

Establishing the neighbor list to efficiently calculate the inter-atomic forces consumes the majority of computation time in molecular dynamics (MD) simulation. Several algorithms have been proposed to improve the computation efficiency for short-range interaction in recent years, although an optimized numerical algorithm has not been provided. Based on a rigorous definition of Verlet radius with respect to temperature and list-updating interval in MD simulation, this paper has successfully developed an estimation formula of the computation time for each MD algorithm calculation so as to find an optimized performance for each algorithm. With the formula proposed here, the best algorithm can be chosen based on different total number of atoms, system average density and system average temperature for the MD simulation. It has been shown that the Verlet Cell-linked List (VCL) algorithm is better than other algorithms for a system with a large number of atoms. Furthermore, a generalized VCL algorithm optimized with a list-updating interval and cell-dividing number is analyzed and has been verified to reduce the computation time by 30∼60% in a MD simulation for a two-dimensional lattice system. Due to similarity, the analysis in this study can be extended to other many-particle systems.     

一种基于自适应陷波器的科氏流量计频率解算新方法

为提高科氏流量计信号的初始收敛速度和频率跟踪精度,提出了一种频率解算的新方法:首先采用基于burg算法实现的格型IIR自适应陷波器对信号滤波,并短时间跟踪信号频率,其接近收敛时基于简化梯度算法实现的格型自适应陷波器开始并行工作,待简化梯度算法实现的格型自适应陷波器收敛后,前者停止工作,简化梯度算法实现的格型自适应陷波器持续工作直至结束。仿真及实验结果表明,本方法可以获得更快的收敛速度、更高的频率跟踪精度。     

融合神经网络的布料碰撞检测算法

目的 针对当前在虚拟环境中布料柔体碰撞检测效率慢和准确性低的问题,提出一种根节点双层包围盒树结构和融合OpenNN （open neural networks library）神经网络加速预测碰撞检测的算法。方法 首先改进了碰撞检测常用的包围盒技术,提出根节点双层包围盒算法,减少包围盒的构造时间。其次使用神经网络优化碰撞检测技术,利用神经网络可以处理大量数据的优势,每次可以检测大量基本图元是否发生碰撞,解决了碰撞检测计算复杂性高的问题。最后准确地找到碰撞粒子并做出碰撞响应。结果 在相同的复杂布料模型情况下,根节点双层包围盒算法在运行速度上比传统混合包围盒算法快,耗时缩减了5.51%~11.32%。基于OpenNN算法的总耗时比根节点双层包围盒缩减了11.70%,比融合DNN （deep neural network）的自碰撞检测算法减少了6.62%。随着碰撞检测难度的增大,当布料模型的精度增加84%时,传统物理碰撞检测方法用时增加96%,融合DNN的自碰撞检测算法用时增加90.11%,而本文基于神经网络的算法用时仅增加了68.37%,同时表现出更高的稳定性,满足使用者对实时性的要求。结论 对于模拟场景中简单模型的碰撞,本文提出的根节点双层包围盒算法比传统的包围盒方法耗时短。对于复杂模型,基于OpenNN神经网络的碰撞检测算法在效率上优于传统的包围盒算法和融合DNN的自碰撞检查算法,而且模拟效果的准确性也得以保证,是一种高效的碰撞检测方法。     

一种新的基于混合层次包围盒的碰撞检测算法

为了实现物体间快速精确的碰撞检测,提出了一种新的基于混合层次包围盒的碰撞检测算法,充分利用了包围球计算简单和K-DOPs包围盒紧密性好的优点,来构建物体的混合层次包围盒结构。在包围盒树的上层采用Sphere包围盒,能快速排除不相交的物体,下层采用K-DOPs包围盒,进行更加精确的相交测试,提高了碰撞检测实时性。实验结果表明,该算法是有效可行的,具有较强的实时性及鲁棒性,性能优于传统碰撞检测算法。     

基于包围盒与碰撞的模型填充算法研究

为了将任意模型使用球体进行密实填充,提出了一种基于包围盒与碰撞的模型填充算法。该算法首先生成模型的轴对称包围盒;其次在包围盒内产生任意数量球体并进行刚体碰撞,碰撞后的球体将会在包围盒的范围内均匀分布;最后采用判断法线方向算法筛选出模型内部的球体并保留至最终结果。通过实例证明,该算法能够根据输入的球体填充数量及孔隙率快速生成模型内的紧密填充球体。该算法对于模型的适应性高,生成速度快,具有2,000万三角网格的模型仅需20秒即可生成内部填充球体,为生成点阵结构模型进一步奠定了基础。     

Theoretical underpinnings for maximal clique enumeration on perturbed graphs

The problem of enumerating the maximal cliques of a graph is a computationally expensive problem with applications in a number of different domains. Sometimes the benefit of knowing the maximal clique enumeration (MCE) of a single graph is worth investing the initial computation time. However, when graphs are abstractions of noisy or uncertain data, the MCE of several closely related graphs may need to be found, and the computational cost of doing so becomes prohibitively expensive.Here, we present a method by which the cost of enumerating the set of maximal cliques for related graphs can be reduced. By using the MCE for some baseline graph, the MCE for a modified, or perturbed, graph may be obtained by enumerating only the maximal cliques that are created or destroyed by the perturbation. When the baseline and perturbed graphs are relatively similar, the difference set between the two MCEs can be overshadowed by the maximal cliques common to both. Thus, by enumerating only the difference set between the baseline and perturbed graphs’ MCEs, the computational cost of enumerating the maximal cliques of the perturbed graph can be reduced.We present necessary and sufficient conditions for enumerating difference sets when the perturbed graph is formed by several different types of perturbations. We also present results of an algorithm based on these conditions that demonstrate a speedup over traditional calculations of the MCE of perturbed, real biological networks.     

Calculation of Minkowski-reduced lattice bases

Up to now there has been an algorithm for the calculation of Minkowski-reduced lattice bases to dimensionn=6 or at most ton=7. A new algorithm is presented which is practicable for greater dimensions and requires less computation time.     

时间序列中快速模式发现算法的研究

针对长时间序列,该文提出了一种新的能快速发现序列中时序模式的检索方法。首先将时间序列分成若干等长的子序列;接着从每个子序列中提取特征序列,该特征序列能够反映子序列中数据的变化趋势;然后根据每个特征序列将相应的子序列分配到一系列盒子中,使得不同盒子中的子序列因数据变化趋势不同而不相似,而在同一盒子中的序列由于数据变化趋势相同而有可能相似;最后通过计算每个盒子中任意两个子序列间的欧几里德距离来发现所有的模式。有关实验证明该算法是行之有效的。