A multiple minima genetic algorithm for protein structure prediction

Protein structure prediction (PSP) has a large potential for valuable biotechnological applications. However the prediction itself encompasses a difficult optimization problem with thousands of degrees of freedom and is associated with extremely complex energy landscapes. In this work a simplified three-dimensional protein model (hydrophobic-polar model, HP in a cubic lattice) was used in order to allow for the fast development of a robust and efficient genetic algorithm based methodology. The new methodology employs a phenotype based crowding mechanism for the maintenance of useful diversity within the populations, which resulted in increased performance and granted the algorithm multiple solutions capabilities. Tests against several benchmark HP sequences and comparative results showed that the proposed genetic algorithm is superior to other evolutionary algorithms. The proposed algorithm was then successfully adapted to an all-atom protein model and tested on poly-alanines. The native structure, an alpha helix, was found in all test cases as a local or a global minimum, in addition to other conformations with similar energies. The results showed that optimization strategies with multiple solutions capability present two advantages for PSP applications. The first one is a more efficient investigation of complex energy landscapes; the second one is an increase in the probability of finding native structures, even when they are not at the global optimum.     

基于茎区组合的RNA二级结构预测算法

RNA二级结构预测是生物信息学的研究热点和难点,特别是对于含假结的RNA二级结构的预测,已经被证明是NP问题。根据RNA折叠的特点,提出了一种基于茎区组合的智能优化算法来预测RNA 的二级结构。该算法以RNA的茎区为基本单元,结合图论思想,通过二元关系的基本理论,依据自由能最小原则获取茎区的最优组合。该算法的时间复杂度为O(n3),空间复杂度为O(n2),而且可以发现假结。实验结果证明了算法的有效性。     

Goal seeking in the problem of folding RNA tertiary structures

It is demonstrated that the problem of ribonucleic acid (RNA) molecule folding can be represented as the optimal decision making problem of the game theory. The difference is that it is impossible to simulate (calculate) all the possible conformations (states) of the RNA chain since the problem is NP complete. Therefore, it is necessary to perform goal selection: which states should and which should not be calculated. It is proposed to use the “X-tuning” method for this purpose; this method, based on the closest to final state actions (moves, rotations), essentially reduces the search. In spite of the fact that this method does not guarantee obtaining a global minimum, it provides a group of acceptable solutions, which is often sufficient in practice. It is shown that X-tuning can be applied in games with an opponent and in the problem of RNA folding (a game in nature).     

Graphics of RNA secondary structure; towards an object-oriented algorithm

We present a new algorithm for the display of RNA secondary structure. The principle of the algorithm is entirely different from those currently in use in that our algorithm is 'object oriented' while current algorithms are 'procedural'. The circular RNA molecule of chrysanthemum stunt viroid was used as input data for demonstrating the operation of the program. The major interest of this method will be found in its potential use in simulation graphics of RNA folding processes.     

改进的免疫粒子群优化算法预测RNA二级结构

针对RNA二级结构预测问题,在SetPSO算法的基础上提出了一种改进的免疫粒子群优化算法,根据RNA折叠的特点,启用免疫记忆算子增加粒子群多样性,有效防止了原方法易陷入局部最优的缺陷。仿真结果表明改进算法能在更短的时间内达到更高的预测精度。     

一种光线与三角形求交算法的硬件架构设计

为了实现实时性的光线追踪平台,提出了一种光线与三角形求交算法的硬件架构设计。首先介绍了一种光线与三角形求交的简洁算法。该算法与其它算法相比使用存储空间最少,却具有相似的性能,便于硬件实现。根据此算法,提出了相应的硬件架构,在架构设计过程中,通过折叠、资源共享、以及多线程等硬件架构设计方法来提高硬件使用率,使有限的硬件资源达到最高的性能。实验结果表明,与现有方案相比,本文硬件架构平台在速度和芯片面积两个方面都存在着较大的提高。为实时光线追踪的实现提供了依据。     

An improved secondary structure computation method and its application to intervening sequence in the human alpha-like globin mRNA precursors

Current secondary structure prediction computations have a serious drawback. The calculated thermodynamically most stable structure often differs from that observed in solution or in crystal form. In this paper we suggest a way to partially over-come some of these limitations by simulating the RNA folding process and calculating the frequencies of occurrence of the various substructures obtained. The frequently recurring substructures are then selected to construct the secondary structure of the whole RNA. 142 tRNA molecules and an E. coli 16S rRNA molecule have been examined by this method. The percentage of successful prediction of the correct helices are significantly higher than those calculated previously. The secondary structures of intervening sequences (IVSs) excised from human alpha-like globin pre-mRNAs are also computed. Thus, in this method the secondary structures obtained are composed of the statistically more significant substructures. This has also been demonstrated by using randomly shuffled sequences. The secondary structures of each of the randomized sequences are computed and their mean and standard deviations are used in evaluating the significance of the substructures obtained in the folding of the biological sequence. Some potentially appealing structural features aligning adjacent exons for ligation have been found.     

Simulation of coupled folding and binding of an intrinsically disordered protein in explicit solvent with metadynamics

The C-terminal domain of measles virus nucleoprotein is an intrinsically disordered protein that could bind to the X domain (XD) of phosphoprotein P to exert its physiological function. Experiments reveal that the minimal binding unit is a 21-residue α-helical molecular recognition element (α-MoRE-MeV), which adopts a fully helical conformation upon binding to XD. Due to currently limited computing power, direct simulation of this coupled folding and binding process with atomic force field in explicit solvent cannot be achieved. In this work, two advanced sampling methods, metadynamics and parallel tempering, are combined to characterize the free energy surface of this process and investigate the underlying mechanism. Starting from an unbound and partially folded state of α-MoRE-MeV, multiple folding and binding events are observed during the simulation and the energy landscape was well estimated. The results demonstrate that the isolated α-MoRE-MeV resembles a molten globule and rapidly interconverts between random coil and multiple partially helical states in solution. The coupled folding and binding process occurs through the induced fit mechanism, with the residual helical conformations providing the initial binding sites. Upon binding, α-MoRE-MeV can easily fold into helical conformation without obvious energy barriers. Two mechanisms, namely, the system tending to adopt the structure in which the free energy of isolated α-MoRE-MeV is the minimum, and the binding energy of α-MoRE-MeV to its partner protein XD tending to the minimum, jointly dominate the coupled folding and binding process. With the advanced sampling approach, more IDP systems could be simulated and common mechanisms concerning the coupled folding and binding process could be investigated in the future.     

Automatically obtaining a cellular automaton scheme for modeling protein folding using the FCC model

This paper proposes to model protein folding as an emergent process, using machine learning to infer the folding modeling only from information of known protein structures. Using the face-centered cubic lattice for protein conformation representation, the dynamic nature of protein folding is captured with an evolved neural cellular automaton that defines the amino acids moves along the protein chain and across time. The results of the final folded conformations are compared, using different protein benchmarks, with other methods used in the traditional protein structure prediction problem, highlighting the capabilities and problems found with this modeling.

     

基于混合蚁群遗传算法的RNA二级结构预测

RNA二级结构预测是生物信息学的重要研究领域.本文提出一种新的基于混合蚁群遗传算法的RNA二级结构预测方法.充分利用茎区和茎区之间的关系信息和累积的信息,通过蚁群算法产生初始种群和新的个体,进而替换遗传算法中的变异算子.构造蚁群算法中的启发式信息、初始信息素矩阵、下一茎区的选取规则和信息素的更新机制,给出遗传算法中交叉...     

肌巨蛋白PEVK多肽片段中模型分子EVPK的构象研究

为探讨肌巨蛋白中PEVK多肽片段对肌巨蛋白的弹性贡献,本文采用分子力学随机构象搜索法、分子动力学模拟退火法和混合Monte Carlo方法,对PEVK多肽片段中的模型分子EVPK进行构象搜索和构象稳定性研究。结果表明,构象搜索所得低能构象集中,以分子动力学模拟退火所得的构象能量最低,构象中分子呈折叠式且稳定性较好。在拉力作用下构象被拉伸,在宏观上表现出弹性,为解释PEVK多肽片段是肌巨蛋白弹性的来源提供理论依据。     

Computational prediction of nucleic acid secondary structure: Methods,applications, and challenges

RNA molecules are crucial in different levels of cellular function, ranging from translation and regulating genes to coding for proteins. Additionally, nucleic acids (RNA and DNA molecules) are designed for novel applications in biotechnology. Understanding the structure of a molecule is important in inferring its function, and computational methods for structure prediction have captured the interest of many researchers.Some functions of RNA molecules in cells, such as gene regulation, result from the binding of one RNA molecule to another, so-called target RNA molecule. This has led to recent interest in prediction of the secondary structure formed from interacting molecules. In this paper, we provide a brief overview of methods, applications, and challenges in computational prediction of nucleic acid secondary structure, both for single strands and for interacting strands.     

多目标优化的非编码RNA比对及预测

为更好地优化多个代价函数,提出一种多目标模拟退化算法,在运算过程中对多目标进行优化,从而得到边界上不同方向的最优解,介绍进化过程中的非编码RNA结构,并在此基础上提出RNA多重比对及预测并行模型。实验结果表明,该模型能有效提高解的精度和多样性。     

Automatic source-code parallelization using HICOR objects

We show that by using an intermediate representation, which supports a formalized interface on which to construct parallelization tools, the mapping of the representation onto parallel architectures can be performed quickly and efficiently. An intermediate representation called HICOR (Hierarchical Intermediate Code Object Representation) is shown to facilitate the exploitation of parallel operations by providing an abstraction layer for performing high-level intermediate code analysis, scheduling, and code generation. An object-oriented design approach has been employed in the development of HICOR and associated tools. Source language constructs are transformed into specialized object classes. Inheritance properties provided by the object-oriented paradigm are utilized to provide a common interface to each object in the HICOR representation. It is this interface that provides the needed consistency and flexibility in which to construct tools that has since been lacking. In particular, a tool to performCompile-Time Scheduling is presented. The scheduling algorithm employed differs from traditional scheduling problems in that merging of tasks is performed to reduce both task creation and communication costs in determining the final schedule. Architectural parameters are provided as input to the heuristic allowing the scheduler to produce near-optimal results for a wide variety of MIMD architectures. Once the final schedule is determined theTarget Code Generator, also presented, is used to generate the corresponding target code. A prototype system has been implemented in C++ which incorporates the HICOR intermediate representation with the tools described. The target architectures include the Sun 630 MP/4, Sequent Symmetry S81, and Stardent Titan.     

InsideInsights: Integrating Data‐Driven Reporting in Collaborative Visual Analytics

Analyzing complex data is a non‐linear process that alternates between identifying discrete facts and developing overall assessments and conclusions. In addition, data analysis rarely occurs in solitude; multiple collaborators can be engaged in the same analysis, or intermediate results can be reported to stakeholders. However, current data‐driven communication tools are detached from the analysis process and promote linear stories that forego the hierarchical and branching nature of data analysis, which leads to either too much or too little detail in the final report. We propose a conceptual design for integrated data‐driven reporting that allows for iterative structuring of insights into hierarchies linked to analytic provenance and chosen analysis views. The hierarchies become dynamic and interactive reports where collaborators can review and modify the analysis at a desired level of detail. Our web‐based Inside Insights system provides interaction techniques to annotate states of analytic components, structure annotations, and link them to appropriate presentation views. We demonstrate the generality and usefulness of our system with two use cases and a qualitative expert review.     

Graph-cut based interactive segmentation of 3D materials-science images

Segmenting materials’ images is a laborious and time-consuming process, and automatic image segmentation algorithms usually contain imperfections and errors. Interactive segmentation is a growing topic in the areas of image processing and computer vision, which seeks to find a balance between fully automatic methods and fully-manual segmentation processes. By allowing minimal and simplistic interaction from the user in an otherwise automatic algorithm, interactive segmentation is able to simultaneously reduce the time taken to segment an image while achieving better segmentation results. Given the specialized structure of materials’ images and level of segmentation quality required, we show an interactive segmentation framework for materials’ images that has three key contributions: (1) a multi-labeling approach that can handle a large number of structures while still quickly and conveniently allowing manual addition and removal of segments in real-time, (2) multiple extensions to the interactive tools which increase the simplicity of the interaction, and (3) a web interface for using the interactive tools in a client/server architecture. We show a full formulation of each of these contributions and example results from their application.     

联合注意力机制与目标点信息的车辆轨迹预测

对周围环境中运动物体未来状态的准确预测是影响自动驾驶车辆做出准确决策的重要影响因素,车辆是最常见也是最需要关注的运动物体之一。针对结构化道路下周围车辆轨迹预测的多模态输入问题,提出了基于注意力机制的深度预测网络。提出交互模块以提取目标车辆与周围车辆及车道线信息存在的交互特征;结合车道线信息对车辆运动的指引作用,加入目标点预测模块以预测目标车辆可能到达的目标点,增加预测准确性。在Argoverse公开数据集上进行实验,所提轨迹预测网络在3秒预测时长实现了1.45m最小平均距离误差及3.21m最小最终距离误差的预测精度,优于当前主流的预测算法。     

An algorithm for comparing multiple RNA secondary structures

A new distributed computational procedure is presented for rapidly determining the similarity of multiple conformations of RNA secondary structures. A data abstraction scheme is utilized to reduce the quantity of data that must be handled to determine the degree of similarity among multiple structures. The method has been used to compare 200 structures with easy visualization of both those structures and substructures that are similar and those that are vastly different. It has the capability of processing many more conformations as a function of research requirements. The algorithm is described as well as some suggestions for future uses and extensions.     

An interactive approach for multiple criteria selection problem

In this study, we develop an interactive algorithm for the multiple criteria selection problem that aims to find the most preferred alternative among a set of known alternatives evaluated on multiple criteria. We assume the decision maker (DM) has a quasi-concave value function that represents his/her preferences. The interactive algorithm selects the pairs of alternatives to be asked to the DM based on the estimated likelihood that one alternative is preferred to another. After the DM selects the preferred alternative, a convex cone is generated based on this preference information and the alternatives dominated by the cone are eliminated. Then, the algorithm updates the likelihood information for the unselected pairwise questions. The aim of the algorithm is to detect the most preferred alternative by performing as few pairwise comparisons as possible. We present the algorithm on an illustrative example problem. We also develop a mathematical model that finds the minimum number of questions that can be asked to the DM to determine the most preferred alternative under perfect information. We use the minimum number of questions to develop strategies for interactive algorithm and measure its performance.