An improved algorithm for nucleic acid secondary structure display

An improved algorithm for the display of nucleic acid secondary structures is presented. It is particularly suitable for large sequence segments and it automatically generates an aesthetically pleasing display of the structure with very limited overlap of strands. Structural similarities in different structures are conserved in the display thus greatly aiding structural homology comparisons. Using the algorithm, we illustrate the effect of ribosome translocation on the secondary structure of a rat neuropeptide messenger 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.     

基于FPGA的细粒度并行CYK算法加速器设计与实现

基于随机上下文无关文法(SCFG)理论模型进行RNA二级结构预测是目前采用计算方法研究RNA二级结构的一种重要途径.由于基于SCFG模型的标准结构预测算法(Coche-Younger-Kasami,CYK)巨大的时空复杂度,对CYK算法进行加速成为计算生物学领域一个极具挑战性的热点问题.CYK的并行性能受限于算法多维度、非一致性的数据依赖关系和较低的计算/通信比,现有的基于通用微处理器结构的大规模并行处理方案不能获得令人满意的加速效果,并且大规模并行计算机系统硬件设备的购置、使用、日常维护的成本高昂,其适用性受到诸多限制.文中在深入分析CYK算法计算特征的基础上,基于FPGA平台提出并实现了一种细粒度的并行CYK算法.设计采用了对三维动态规划矩阵按区域分割和逐层按列并行处理的计算策略实现了多个处理单元间的负载均衡;采用数据预取、滑动窗口和数据传递流水线实现处理单元间的数据重用,有效解决了计算和通信间的平衡问题;设计了一种类似脉动阵列(systolic-like array)结构的主从多PE并行计算阵列,并在目前最大规模的FPGA芯片(Xilinx XC5VLX330)上成功集成了16个处理单元(process...     

Artificial neural networks for molecular sequence analysis

Artificial neural networks provide a unique computing architecture whose potential has attracted interest from researchers across different disciplines. As a technique for computational analysis, neural network technology is very well suited for the analysis of molecular sequence data. It has been applied successfully to a variety of problems, ranging from gene identification, to protein structure prediction and sequence classification. This article provides an overview of major neural network paradigms, discusses design issues, and reviews current applications in DNA/RNA and protein sequence analysis.     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

Visualization of nucleic acid sequence structural information

Several interactive Pascal programs have been written for the analysis and display of structural information in nucleic acid sequences. Layout procedures were developed to display the homology and repeat matrices of a sequence and to predict and display the secondary structure of RNA/DNA molecules free of overlap and to predict and display internal repeats. No special plotting devices are required because the output is adapted to line printers. Sequences from several DNA database systems can be used as input. These programs are part of a general nucleic acid sequence analysis package.     

NP-completeness of the energy barrier problem without pseudoknots and temporary arcs

Knowledge of energy barriers between pairs of secondary structures for a given DNA or RNA molecule is useful, both in understanding RNA function in biological settings and in design of programmed molecular systems. Current heuristics are not guaranteed to find the exact energy barrier, raising the question whether the energy barrier can be calculated efficiently. In this paper, we study the computational complexity of a simple formulation of the energy barrier problem, in which each base pair contributes an energy of −1 and only base pairs in the initial and final structures may be used on a folding pathway from initial to final structure. We show that this problem is NP-complete.     

基于隐Markov模型的RNA二级结构预测新方法

有效预测RNA二级结构是生物信息学中的重要研究领域.提出一种基于隐Markov模型预测RNA二级结构的新方法.首先,应用前后缀匹配算法快速找到所有可能(包括假结)的茎区,建立RNA-HMM,寻找最优的茎区组合方法,得到包含假结的RNA二级结构.实验结果表明,提出的新方法降低了计算复杂性,提高了预测的特异性和敏感性,具有较高的准确率,可以预测RNA的假结结构.     

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.     

Learning probabilistic models of tree edit distance

Nowadays, there is a growing interest in machine learning and pattern recognition for tree-structured data. Trees actually provide a suitable structural representation to deal with complex tasks such as web information extraction, RNA secondary structure prediction, computer music, or conversion of semi-structured data (e.g. XML documents). Many applications in these domains require the calculation of similarities over pairs of trees. In this context, the tree edit distance (ED) has been subject of investigations for many years in order to improve its computational efficiency. However, used in its classical form, the tree ED needs a priori fixed edit costs which are often difficult to tune, that leaves little room for tackling complex problems. In this paper, to overcome this drawback, we focus on the automatic learning of a non-parametric stochastic tree ED. More precisely, we are interested in two kinds of probabilistic approaches. The first one builds a generative model of the tree ED from a joint distribution over the edit operations, while the second works from a conditional distribution providing then a discriminative model. To tackle these tasks, we present an adaptation of the expectation–maximization algorithm for learning these distributions over the primitive edit costs. Two experiments are conducted. The first is achieved on artificial data and confirms the interest to learn a tree ED rather than a priori imposing edit costs; The second is applied to a pattern recognition task aiming to classify handwritten digits.     

Incorporating multiple genomic features with the utilization of interacting domain patterns to improve the prediction of protein-protein interactions

Protein-protein interaction (PPI) networks play an outstanding role in the organization of life. Parallel to the growth of experimental techniques on determining PPIs, the emergence of computational methods has greatly accelerated the time needed for the identification of PPIs on a wide genomic scale. Although experimental approaches have limitations that can be complemented by the computational methods, the results from computational methods still suffer from high false positive rates which contribute to the lack of solid PPI information. Our study introduces the PPI-Filter; a computational framework aimed at improving PPI prediction results. It is a post-prediction process which involves filtration, using information based on three different genomic features; (i) gene ontology annotation (GOA), (ii) homologous interactions and (iii) protein families (PFAM) domain interactions. In the study, we incorporated a protein function prediction method, based on interacting domain patterns, the protein function predictor or PFP (), for the purpose of aiding the GOA. The goal is to improve the robustness of predicted PPI pairs by removing the false positive pairs and sustaining as much true positive pairs as possible, thus achieving a high confidence level of PPI datasets. The PPI-Filter has been proven to be applicable based on the satisfactory results obtained using signal-to-noise ratio (SNR) and strength measurements that were applied on different computational PPI prediction methods.     

基于免疫粒子群集成的RNA二级结构预测算法

RNA二级结构预测在计算生物学中具有重要意义,针对RNA二级结构预测,提出了一种新的免疫粒子群集成算法,根据个体的浓度和适应值概率,利用免疫机制,在粒子群优化算法中设计了免疫替换算子,有效防止了粒子群优化算法易陷入局部最优的缺陷;通过集成技术,充分发挥各种粒子群优化算法的优点,实现协同演化,提高了算法的全局搜索能力。最后用免疫粒子群集成算法去预测RNA二级结构,实验证明了算法的有效性。     

A secondary and tertiary structure editor for nucleic acids

A major difficulty in the evaluation of secondary and tertiary structures of nucleic acids is the lack of convenient methods for their construction and representation. As a first step in a study of the symbolic representation of biopolymers, we report the development of a structure editor written in Pascal, permitting model construction on the screen of a personal computer. The program calculates energies for helical regions, allows user-defined helices and displays the secondary structure of a nucleic acid based on a user-selected set of helices. Screen and printer outputs can be in the form of a backbone or the letters of the primary sequence. The molecule can then be displayed in a format which simulates its three-dimensional structure. Using appropriate glasses, the molecule can be viewed on the screen in three dimensions. Other options include the manipulation of helices and single-stranded regions which results in changes in the spatial relationship between different regions of the molecule. The editor requires an IBM or compatible PC, 640 kbyte memory and a medium or high resolution graphics card.     

RNAStudio,a full-featured object-oriented program for visualizing RNA secondary structures

The function of a RNA molecule relies on the underlying physical mechanisms and geometric properties in terms of secondary or tertiary structure, in which one of the most important properties is topological connectivity. RNAStudio, available at http://rnastudio.51.net, brings the convenience of Windows to the representation of RNA folding topology including the sections mentioned below.     

Predicting RNA Secondary Structure Using Profile Stochastic Context-Free Grammars and Phylogenic Analysis

Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. However, most of existing SCFG-based methods lack explicit phylogenic analysis of homologous RNA sequences, which is probably the reason why these methods are not ideal in practical application. Hence, we present a new SCFG-based method by integrating phylogenic analysis with the newly defined profile SCFG. The method can be summarized as： 1） we define a new profile SCFG, M, to depict consensus secondary structure of multiple RNA sequence alignment; 2） we introduce two distinct hidden Markov models, λ and λ＇, to perform phylogenic analysis of homologous RNA sequences. Here, λ＇ is for non-structural regions of the sequence and λ＇ is for structural regions of the sequence; 3） we merge λ and λ＇ into M to devise a combined model for prediction of RNA secondary structure. We tested our method on data sets constructed from the Rfam database. The sensitivity and specificity of our method are more accurate than those of the predictions by Pfold.     

MMTSB Tool Set: enhanced sampling and multiscale modeling methods for applications in structural biology

We describe the Multiscale Modeling Tools for Structural Biology (MMTSB) Tool Set (https://mmtsb.scripps.edu/software/mmtsbToolSet.html), which is a novel set of utilities and programming libraries that provide new enhanced sampling and multiscale modeling techniques for the simulation of proteins and nucleic acids. The tool set interfaces with the existing molecular modeling packages CHARMM and Amber for classical all-atom simulations, and with MONSSTER for lattice-based low-resolution conformational sampling. In addition, it adds new functionality for the integration and translation between both levels of detail. The replica exchange method is implemented to allow enhanced sampling of both the all-atom and low-resolution models. The tool set aims at applications in structural biology that involve protein or nucleic acid structure prediction, refinement, and/or extended conformational sampling. With structure prediction applications in mind, the tool set also implements a facility that allows the control and application of modeling tasks on a large set of conformations in what we have termed ensemble computing. Ensemble computing encompasses loosely coupled, parallel computation on high-end parallel computers, clustered computational grids and desktop grid environments. This paper describes the design and implementation of the MMTSB Tool Set and illustrates its utility with three typical examples--scoring of a set of predicted protein conformations in order to identify the most native-like structures, ab initio folding of peptides in implicit solvent with the replica exchange method, and the prediction of a missing fragment in a larger protein structure.     

Numerical and experimental LDL transport through arterial wall

Atherosclerosis develops from oxidized low-density lipoprotein molecules (LDL). When oxidized LDL evolves in plaque formations within an artery wall, a series of reactions occur to repair the damage to the artery wall caused by oxidized LDL. Aim of this study was to compare experimental data of LDL transport through isolated blood vessel with computational results of bounding of oxidized LDL receptor-1 (LOX-1) for endothelial cells with numerical discrete methods such as dissipative particle dynamics (DPD) and lattice Boltzmann (LB) method. Experiments of LDL transport were performed on the isolated rabbit common carotid arteries acquired from fifteen rabbits after 12 weeks of high-fat diet. Oxidative LDL molecule is built and used for docking with LOX-1 receptor. Energies that give the best binding are computed, and the energy with greatest probability of attachment for oxidative LDL molecule and glutamine acid is further used in numerical simulations. Simulations using DPD and LB method use the computed binding energy to calculate the force necessary for binding of LDL molecule to the endothelial blood vessel layer. Experimental results have shown large uptake for shear stress below 1 dyn/cm². Computational results for both discrete methods DPD and LB have shown good accuracy with experimental data. Calculation of the interactive molecule forces from computational chemistry open a new avenue for multiscale modeling methods, which will give better insight for the understanding and the prediction of LDL transport through the arterial wall for the medical community.     

基于结构比对的蛋白结合位点预测方法

蛋白质通过结合位点与其他分子产生相互作用, 所以对蛋白结合位点的预测具有重要的意义. 现有许多不同的预测方法, 但是这些方法存在命中率低或计算量大的问题, 本文引入了一种基于结构比对的蛋白质位点预测方法, 同时在结构比对过程中引入同源索引, 找出相应的同源模版, 并与之进行结构比对, 然后将结构相似的模版中的配体映射到目标蛋白质中, 采用聚类方法对位点进行分析. 结果表明, 与其他预测方法相比, 本文的方法降低了计算量, 并提高了预测精度.