A parallel strategy for biological sequence alignment in restricted memory space

Recently, many organisms had their DNA entirely sequenced, and this reality presents the need for aligning long DNA sequences, which is a challenging task due to its high demands for computational power and memory. The algorithm proposed by Smith–Waterman (SW) is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, quadratic complexity makes the use of this algorithm impractical. In this scenario, parallel computing is a very attractive alternative. In this paper, we propose and evaluate z-align, a parallel exact strategy based on the divergence concept to locally align long biological sequences using an affine gap function. Z-align runs in limited memory space, where the amount of memory used can be defined by the user. The results collected in a cluster with 16 processors presented very good speedups for long real DNA sequences. With z-align, we were able to compare up to 3 MBP (mega base-pairs) DNA sequences. As far as we know, this is the first time 3 MBP sequences are compared with an affine gap exact variation of the SW algorithm. Also, by comparing the results obtained with z-align and the popular BLAST tool, it is clear that z-align is able to produce longer and more significant alignments.     

A design and feasibility study of reactions comprising DNA molecular machine that walks autonomously by using a restriction enzyme

In this paper, we propose an autonomous molecular walking machine using DNA. This molecular machine follows a track of DNA equipped with many single-strand DNA stators arranged in a certain pattern. The molecular machine achieves autonomous walk by using a restriction enzyme as source of power. With a proposed machine we can control its moving direction and we can easily extend walking patterns in two or three dimensions. Combination of multiple legs and ssDNA stators can control the walking pattern. We designed and performed a series of feasibility study with computer simulation and molecular biology experiments.     

一种新的RNA二级结构特征序列表示及相似性分析*

针对目前不同的RNA二级结构可能对应相同特征序列的问题,本文提出了一种新的RNA二级结构特征序列表示法,根据不同的RNA二级结构的子结构类型,分别给出相应的字符表示并由此得到新的特征序列。利用Lempel-Ziv复杂度对两组RNA二级结构进行了相似性分析,实验结果表明了该表示法可以有效的提取RNA二级结构的结构信息,避免了不同RNA二级结构可能对应相同特征序列的问题。     

Unravel four hairpins!

DNA machines consisting of consecutive hairpins, which we have previously described, have various potential applications in DNA computation. In the present study, a 288-base DNA machine containing four consecutive hairpins was successfully constructed by ligation and PCR. PAGE and fluorescence spectroscopy experiments verified that all four hairpins were successfully opened by four opener oligomers, and that hairpin opening was dependent on the proper openers added in the correct order. Quantitative analysis of the final results by fluorescence spectroscopy indicated that all four hairpins were open in about 1/4 to 1/3 of the DNA machines.     

Spatio–Temporal Memories for Machine Learning: A Long-Term Memory Organization

Design of artificial neural structures capable of reliable and flexible long-term spatio-temporal memory is of paramount importance in machine intelligence. To this end, we propose a novel, biologically inspired, long-term memory (LTM) architecture. We intend to use it as a building block of a neuron-level architecture that is able to mimic natural intelligence through learning, anticipation, and goal-driven behavior. A mutual input enhancement and blocking structure is proposed, and its operation is discussed in detail. The paper focuses on a hierarchical memory organization, storage, recognition, and recall mechanisms. Simulation results of the proposed memory show its effectiveness, adaptability, and robustness. Accuracy of the proposed method is compared to other methods including Levenshtein distance method and a Markov chain.     

面向长作业环境中的云调度策略

随着云计算的普及,大量的数据处理选择云服务来完成。现有算法较少考虑异构型系统中虚拟机计算能力的不同,导致某些任务等待时间过长。提出了虚拟机负载大小实时调整的算法。对云计算中资源虚拟化特征,给出一种评估虚拟机计算能力的方法。根据虚拟机能力和运行过程中的状态变化,自适应进行任务量大小调整,满足实时要求。通过任务调度,协调任务完成时间,保持各虚拟机负载的动态均衡,缩短长作业的总执行时间,提高了系统的吞吐量和整体服务能力,提升了效益。实验结果表明,本文算法能自适应地调整任务量大小,进行调度,以维持虚拟机负载均衡。     

DNA自组装的可满足性问题模型

DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.     

A compact hybrid feature vector for an accurate secondary structure prediction

Amino acid propensity score is one of the earliest successful methods used in protein secondary structure prediction. However, the score performs poorly on small-sized datasets and low-identity protein sequences. Based on current in silico method, secondary structure can be predicted from local folds or local protein structure. In biology, the evolution of secondary structure produces local protein structure with different lengths. To precisely predict secondary structures, we propose a derivative feature vector, DPS that utilizes the optimal length of the local protein structure. DPS is the unification of amino acid propensity score and dihedral angle score. This new feature vector is further normalized to level the edges. Prediction is performed by support vector machines (SVM) over the DPS feature vectors with class labels generated by secondary structure assignment method (SSAM) and secondary structure prediction method (SSPM). All experiments are carried out on RS126 sequences. The results from this proposed method also highlight the overall accuracy of our method compared to other state-of-the-art methods. The performance of our method was acceptable specifically in dealing with low number and low identity sequences.     

A DNA-based memory with <Emphasis Type="Italic">in vitro</Emphasis> learning and associative recall

A DNA-based memory was implemented with in vitro learning and associative recall.The learning protocol stored the sequences to which it was exposed, and memories were recalled by sequence content through DNA-to-DNA template annealing reactions. Experiments demonstrated that biological DNA could be learned, that sequences similar to the training DNA were recalled correctly, and that unlike sequences were differentiated. Theoretically, the memory has a pattern separation capability that is very large, and can learn long DNA sequences. The learning and recall protocols are massively parallel, as well as simple, inexpensive, and quick. The memory has several potential applications in detection and classification of biological sequences, as well as a massive storage capacity for non-biological data.     

Studies of frequently recurring substructures in human alpha-like globin mRNA precursors

In general, the results obtained from secondary structure prediction algorithms are often inconsistent with those obtained experimentally. The reason for this disagreement is that the experimentally determined structures have higher free energies (as judged by the currently used "energy rules") than the predicted ones. To overcome this limitation we have developed a new approach which incorporates the frequencies of occurrence of substructures in the growing mRNA chain. This has been accomplished by simulating the folding process of pre-mRNAs. Using this approach we have significantly improved current helical structural prediction for 142 analyzed tRNAs and 16 S rRNA. We have next applied this method to the human alpha-like globins. Comparison of the structures obtained by running the currently used algorithms with those computed by the new method indicates that the final most stable secondary structure contains some infrequently occurring substructures. In addition, some of the frequently recurring substructures are not included in the final structure. Comparison of the simulated folding processes of the human alpha-like globin pre-mRNAs reveals some conserved helices and hairpin loop structures in those frequently recurring substructures. Among these several compensating base changes (transitions and transversions) have been identified.     

Software Tools for DNA Sequence Design

The design of DNA sequences is a key problem for implementing molecular self-assembly with nucleic acid molecules. These molecules must meet several physical, chemical and logical requirements, mainly to avoid mishybridization. Since manual selection of proper sequences is too time-consuming for more than a handful of molecules, the aid of computer programs is advisable. In this paper two software tools for designing DNA sequences are presented, the DNASequenceGenerator and the DNASequenceCompiler. Both employ an approach of sequence dissimilarity based on the uniqueness of overlapping subsequences and a graph based algorithm for sequence generation. Other sequence properties like melting temperature or forbidden subsequences are also regarded, but not secondary structure errors or equilibrium chemistry. Fields of application are DNA computing and DNA-based nanotechnology. In the second part of this paper, sequences generated with the DNASequenceGenerator are compared to those from several publications of other groups, an example application for the DNASequenceCompiler is presented, and the advantages and disadvantages of the presented approach are discussed.     

Automatic detection of conserved base pairing patterns in RNA virus genomes.

Almost all RNA molecules--and consequently also almost all subsequences of a large RNA molecule-form secondary structures. The presence of secondary structure in itself therefore does not indicate any functional significance. In fact, we cannot expect a conserved secondary structure for all parts of a viral genome or a mRNA, even if there is a significant level of sequence conservation. We present a novel method for detecting conserved RNA secondary structures in a family of related RNA sequences. The method is based on combining the prediction of base pair probability matrices and comparative sequence analysis. It can be applied to small sets of long sequences and does not require a prior knowledge of conserved sequence or structure motifs. As such it can be used to scan large amounts of sequence data for regions that warrant further experimental investigation. Applications to complete genomic RNAs of some viruses show that in all cases the known secondary structure features are identified. In addition, we predict a substantial number of conserved structural elements which have not been described so far.     

Parallel strategies for the local biological sequence alignment in a cluster of workstations

Recently, many organisms have had their DNA entirely sequenced. This reality presents the need for comparing long DNA sequences, which is a challenging task due to its high demands for computational power and memory. Sequence comparison is a basic operation in DNA sequencing projects, and most sequence comparison methods currently in use are based on heuristics, which are faster but offer no guarantees of producing the best alignments possible. In order to alleviate this problem, Smith–Waterman proposed an algorithm. This algorithm obtains the best local alignments but at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments involving three strategies to run the Smith–Waterman algorithm in a cluster of workstations using a Distributed Shared Memory System. Our results on an eight-machine cluster presented very good speed-up and indicate that impressive improvements can be achieved depending on the strategy used. In addition, we present a number of theoretical remarks concerning how to reduce the amount of memory used.     

激光雷达集成电路存储单元上电复位状态机设计

为了提高激光雷达集成电路存储单元上电复位的稳定性,提出基于集成DSP的激光雷达集成电路存储单元上电复位状态机设计方法。构建激光雷达集成电路存储单元复位状态机的总体结构模型,采用内核电源电路进行单极点高通滤波控制,通过由DSP集成信息模块等组成的上电复位机控制的方法,进行激光雷达集成电路存储单元的程序加载和基线恢复控制,通过基线恢复器实现激光雷达集成电路存储单元的掉电复位和连通性测试,实现激光雷达集成电路的逻辑时序控制和上电状态机设计,实现激光雷达集成电路存储单元的硬件优化设计。仿真结果表明,设计的激光雷达集成电路存储单元上电复位状态机稳定性较好,集成控制性能较强,提高了激光雷达集成信号采集能力。     

Grid Resource Availability Prediction-Based Scheduling and Task Replication

The frequent and volatile unavailability of volunteer-based Grid computing resources challenges Grid schedulers to make effective job placements. The manner in which host resources become unavailable will have different effects on different jobs, depending on their runtime and their ability to be checkpointed or replicated. A multi-state availability model can help improve scheduling performance by capturing the various ways a resource may be available or unavailable to the Grid. This paper uses a multi-state model and analyzes a machine availability trace in terms of that model. Several prediction techniques then forecast resource transitions into the model’s states. We analyze the accuracy of our predictors, which outperform existing approaches. We also propose and study several classes of schedulers that utilize the predictions, and a method for combining scheduling factors. We characterize the inherent tradeoff between job makespan and the number of evictions due to failure, and demonstrate how our schedulers can navigate this tradeoff under various scenarios. Lastly, we propose job replication techniques, which our schedulers utilize to replicate those jobs that are most likely to fail. Our replication strategies outperform others, as measured by improved makespan and fewer redundant operations. In particular, we define a new metric for replication efficiency, and demonstrate that our multi-state availability predictor can provide information that allows our schedulers to be more efficient than others that blindly replicate all jobs or some static percentage of jobs.     

Execution behavior analysis and performance prediction for a shared-memory implementation of an irregular particle simulation method

Many computational-intensive problems from science and engineering are irregular in nature. This makes it difficult to develop an efficient parallel implementation, even for shared-memory machines. As a typical example, we investigate a parallel implementation of an irregular particle simulation algorithm. We concentrate on the issue which programming and system support is needed to yield an efficient implementation for a large number of processors. As an execution platform we use the SB-PRAM, a shared memory machine with up to 2048 processors. The processors of the SB-PRAM can access the global memory in unit time which is the basis for an exact performance prediction. Common approaches for parallel implementations like lock protection for concurrent accesses and sequential or distributed task queues are replaced by more efficient access mechanisms and data structures which can be realized by the powerful multiprefix operations of the SB-PRAM. Their use simplifies the implementation and yields large speedup values.     

DNA计算中的数据与计算模型

对DNA计算的通用性及单链、双链、粘性末端、发夹、质粒、k-臂DNA分子等各种数据作了简单介绍,并对基于DNA分子结构特性和基于DNA计算机研制过程两个方面的DNA计算模型进行了分析对比。针对各种不同的DNA数据及特性,提出了混合DNA计算模型的研究思路,并从不同角度论述了混合DNA计算模型的可行性。     

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.     

连通度问题的三维DNA结构进化算法

针对求连通度这一难解问题,提出了三维DNA图结构进化算法。并提出了一种由k-臂DNA分子构建的图结构。在所述方法中3、4臂DNA分子的顶点构造块被选择性地用来构建一些不同的图结构。然后通过凝胶电泳分离,图的连通度便可确定。并且通过引入进化算法的思想,避免了解空间的穷举。     

PDSS 虚拟机的设计

本文针对可编程器件仿真系统设计中有关中断处理、I／O端口访问冲突等技术难题,将虚拟机的思想应用于PDSS,完成了PDSS虚拟机的设计。本文在介绍PDSS虚拟机结构及功能模块的基础上对虚拟机设计中有关虚拟内存管理和虚拟中断处理两个技术难题进行了较详细论述,给出了具体的处理方法,较好地解决了可编程器件仿真的问题。