图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^[1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.     

On the computational power of insertion-deletion systems

Gene insertion and deletion are basic phenomena found in DNA processing or RNA editing in molecular biology. The genetic mechanism and development based on these evolutionary transformations have been formulated as a formal system with two operations of insertion and deletion, called insertion-deletion systems (Kari and Thierrin, 1996; Kari et al., 1997).We investigate the generative power of insertion-deletion systems (InsDel systems), and show that the family INS ¹ ₁ DEL ¹ ₁ is equal to the family of recursively enumerable languages. This gives a positive answer to an open problem posed in Kari et al. (1997) where it was conjectured contrary. This revised version was published online in June 2006 with corrections to the Cover Date.     

Algorithms for testing that sets of DNA words concatenate without secondary structure

We present an efficient algorithm for determining whether all moleculesin a combinatorial set of DNA or RNA strandsare structure free, and thus availablefor bonding to their Watson-Crick complements.This work is motivated by the goalof testing whether strands used in DNAcomputations or as molecular bar-codesare structure free, where the strands areconcatenations of short words. We alsopresent an algorithm for determining whetherall words in S*, for some finite setS of equi-length words, are structure free. This revised version was published online in June 2006 with corrections to the Cover Date.     

The design of autonomous DNA nano-mechanical devices: Walking and rolling DNA

We provide designs for the first autonomousDNA nanomechanical devices that execute cycles of motion without external environmental changes. These DNA devices translate along a circular strand of ssDNA and rotate simultaneously. The designs use various energy sources to fuel the movements, include (i) ATP consumption by DNA ligase in conjunction with restriction enzyme operations, (ii) DNA hybridization energy in trapped states, and (iii) kinetic (heat) energy. We show that each of these energy sources can be used to fuel random bidirectional movements that acquire after n steps an expected translational deviation of O(√n). For the devices using the first two fuel sources, the rate of stepping is accelerated over the rate of random drift due to kinetic (heat) energy. Our first DNA device, which we call walking DNA, achieves random bidirectional motion around a circular ssDNA strand by use of DNA ligase and two restriction enzymes. Our other DNA device, which we call rolling DNA, achieves random bidirectional motion without use of DNA ligase or any restriction enzyme, and instead using hybridization energy. We also describe how to modify the design for the rolling DNA device to include a ``latching mechanism' that fixes the wheels position at specified location along the road, so as to provide for overall unidirectional translational movement. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于组件的网上教务管理系统

指出目前普通高校教务管理在网络化和集成化程度不高的现象，并针对此情况，提出了一种用COM^ 构筑基于WindowsDNA的教务管理系统开发模式。     

二维条码在制造业信息化中的应用

在讨论二维条码技术及其特点的基础上，具体地介绍二维条码在制造业信息化中的应用。     

DNA分子计算模型

The field of practical DNA computing opened in 1994 with Adleman's paper,in which a laboratory experi-ment involving DNA molecules was used to solve a small instance of the Hamiltonian Path problem. The characteris-tic of this computation is its powerful ability in parallelism,its huge storage and high energy efficiency. This paper mainly introduces the principles of DNA computing and the sticker computing model.     

分析比较Windows DNA支持的数据访问技术

本文在介绍Windows DNA体系结构的基础上，详细分析了WindowsDNA支持的ODBC、OLD DB和ADO三种数据访问的体系结构，应用方法及特点。     

Orphan gene finding—an exon assembly approach

This paper introduces an algorithm for finding eukaryotic genes. It particularly addresses the problem of orphan genes, that is of genes that cannot, based on homology alone, be connected to any known gene family and to which it is therefore not possible to apply traditional gene finding methods. To the best of our knowledge, this is also the first algorithm that attempts to compare in an exact way two DNA sequences that contain both coding (i.e. exonic) and non-coding (i.e. intronic and, possibly, intergenic) parts. The comparison is performed following an algorithmical model of a gene that is as close as possible to the biological one (we consider in this paper the “one ORF, one gene” problem only). A gene is seen as a set of exons that are pieces of an assembly and are not independent. The algorithm is efficient enough: although the constants are higher than for usual sequence comparison, its time complexity is proportional to the product of the sequences lengths while its space complexity scales linearly with the length of the smallest sequence.     

基于亚像素边缘检测的二维条码识别

提出了一种基于亚像素边缘检测的二维条码识别算法、能有效地解决边缘模糊对条码识别的影响。以PDF417条码为例研究了基于亚像素边缘检测的二维条码识别算法。首先定位条码位置并在条码中分割出单个码字符号图像。然后根据分割出来的单个码字符号图像讨论r基于亚像素边缘检测的识别算法。实验结果表明基于亚像素边缘检测的识别算法具有良好的性能，显著地提高了条码的识别率，满足了实际使用的要求。