基于汉明距离的DNA编码约束研究

DNA计算是将现实问题进行编码映射到DNA分子上,通过生物实验产生出代表问题的解的DNA分子,最后通过检测技术提取出该DNA分子。高质量的DNA编码可以尽可能避免或减少计算过程中出现的错误,并使检测阶段易于提取出代表问题的解的DNA分子。对DNA编码约束进行了研究,分析了基于汉明距离的编码约束可以有效降低DNA分子间相似程度,减少DNA计算过程中DNA分子间的相互干扰,从而提高DNA计算的有效性和可靠性。还证明了基于汉明距离的编码约束存在等价的序列组合,降低了编码计算的复杂度。     

隐私保护DNA序列汉明距离计算问题

DNA序列承载着人体重要的生物学信息，如何在保护隐私的情况下正确地对不同的DNA序列进行比对，成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度，在保护隐私的情况下，研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。     

基于纠错码编码理论的DNA编码研究*

作为一种新的计算模式,DNA计算有着强大的计算能力,编码问题在DNA计算中占据重要的位置,有效的编码设计能够提高DNA计算的可靠性。基于纠错码编码理论,提出了一种新的DNA编码方法,该方法可以找出具有一定长度且满足汉明距离约束的DNA编码序列。最后,给出了该算法的仿真,结果表明了该算法的有效性。     

基于动态遗传算法的DNA序列集合设计(英文)

DNA编码序列的质量与数量直接影响着DNA计算的可靠性和规模,如何找到尽可能好的及尽可能多的DNA序列用于实际的应用一直是DNA计算的一个核心问题．文中首先介绍了研究DNA编码和DNA序列集合对DNA计算的意义,并给出了DNA序列设计的汉明距离和反汉明距离约束条件的定义．DNA序列集合的研究对DNA计算的可靠性和规模有着重要的影响,因此文中利用遗传算法和动态遗传算法来设计满足上述约束条件的DNA序列集合,通过对两种方法所得结果的比较,证明了动态遗传算法明显优于遗传算法．与此同时,将文中所得到的实验结果与前人的研究成果进行比较可知,文中的结果大幅提高了DNA编码的上界,从而进一步缩小了DNA编码界的取值范围．并且文中所给出的实验结果,对以后DNA编码的理论界的研究以及编码理论中关于4元码界的研究,提供了重要的参考值．     

DNA编码问题及其复杂性研究*

高质量的DNA编码可以避免DNA分子间的非特异性杂交,提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类,分析了各编码约束对编码质量的影响;然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系;最后通过类比DNA编码问题和图的独立集问题,说明了求解最大DNA序列集合问题是NP完全的。     

求解0-1规划问题的DNA计算模型(英文)

DNA计算是以DNA分子作为数据的一种新型计算模式．在DNA计算中首要面对的问题是编码问题．文中提出了一种双编码方法,利用这种编码方法可以使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作．基于该编码方法所建立的DNA计算模型可用于求解0-1规划问题,只需4次PCR反应即可读取问题的可行解．与其他DNA计算模型相比,该模型具有操作简单、易于实现的优点．     

基于部分字的DNA编码设计与分析*

DNA编码问题是DNA计算中的第一步也是最重要的一步,是DNA计算中的一个基本问题。引入部分字与其洞的定义,研究了部分字的洞与沃森—克里克汉明距离的内在联系,得到沃森—克里克汉明距离与DNA编码的关系;通过分析不完全匹配部分字中洞的出现位置,对发生错误匹配的DNA码进行了优化。解决了DNA编码中除去洞分散分布在DNA双链中的不完全匹配问题,有效弥补了杂交过程中出现的假阳性的缺陷,为DNA编码的研究注入了活力。     

基于聚类小生境遗传算法的DNA编码优化

DNA编码优化问题是DNA计算中的核心问题。分析DNA编码优化的约束条件,在单链DNA序列集合上引入h距离,将聚类小生境技术应用于小种群遗传算法的构造,对DNA编码优化问题进行求解。基于h距离定义DNA序列间的相似函数,将碱基字母编码为4进制整数、DNA编码序列作为个体编码为4进制整数向量、种群编码为4进制整数矩阵,基于模4算术运算,构造相应的遗传算子,并给出DNA编码序列的具体计算结果。实验结果表明,与现有DNA编码序列优化结果相比,该算法可得到更好的DNA编码序列且计算效率较高。     

DNA计算中编码序列的优化设计方案*

提出了一种优化设计方案.该方案的各项评价指标均优于根据以往文献提供的方法所能得到的最好结果.尤其是所提出的海明距离测度方法,进一步保证了特异性杂交产生的自由能远大于非特异性杂交所产生的自由能,便于进行DNA编码序列的设计与选择,为可控的DNA计算提供可靠有效的编码序列.     

可满足问题的分子信标计算模型(英文)

分子信标（Molecular Beacon）是一种发夹状的荧光探针,它可以特异地和那些与分子信标的环（Loop）互补的核酸靶序列杂交,具有单个碱基错配的检测能力．肽核酸（Peptide Nucleic Acid）是人工合成的核酸（DNA）的类似物．PNA骨架为酰胺键,与DNA补链杂交更稳定,可以阻止聚合酶延伸反应．文中将可满足问题的约束变量编码于分子信标的环部识别区,通过分子信标与使得给定范式为真的变量的PNA补链杂交,再利用PNA链可以阻止聚合酶延伸反应的性质,用限制性内切酶EcoRI降解对应于非解的分子信标,最后通过加热表面使分子信标构形发生变化,产生荧光读解．提出的可满足问题的分子信标计算模型具有可靠性高、无需观察和记录计算的中间结果、读解简单等优点．     

A completely automated sample preparation instrument and consumable device for isolation and purification of nucleic acids

Molecular diagnostic analysis and life science studies are dependent on the ability to effectively prepare samples for analysis. We report the development of a system that enables robust sample preparation of nucleic acids. To enable completely automated sample preparation, a consumable cartridge and consumable module system were developed to emulate every step of the sample preparation process. This included enzyme and reagent addition, temperature-controlled incubations, noncontact mixing of enzymes and reagents, buffer exchanges, and sample elution. Using this system, completely automated methods were developed for the purification of viral RNA and DNA from plasma and whole blood and of bacterial genomic DNA from water and whole blood. Extracted nucleic acids were detected and quantified using real-time PCR. The data indicate that automated viral DNA extraction was more efficient than sample extractions performed using a manual process, whereas automated total RNA extraction from the same samples was equivalent to controls. Additionally, we found that the process for bacterial genomic DNA extraction from either water or whole blood was equivalent to the manual extraction processes. We conclude the instrument, consumable cartridge, and reagent system enables easy, cost-effective, and robust sample preparation regardless of the experience of the operator.     

DNA一级序列不同编码方法和相似度比较

为了DNA一级序列的相似度计算,本文比较了三种编码方案:单一碱基在DNA序列中的相对位置、二联码即相邻二碱基在序列中的相对位置、编序单一碱基在DNA序列中的相对位置和二联码在序列中的编序相对位置,在此基础上,运用分子连接性指数计算得到序列的不变量,进而,由塔尼莫特法计算得到物种间的相似度。由单一碱基在DNA序列中的相对位置法比较相似度,对于本研究中10个物种,得到了与生物进化树非常相一致的结果。     

DNA逻辑计算模型的研究现状与展望

DNA计算因其优异的计算能力已经成为当前研究热点,DNA逻辑计算模型是DNA计算体系与运算实现的重要依托。按应用技术将现有DNA逻辑计算模型进行分类：基于链置换的DNA逻辑计算模型、基于核酶的DNA逻辑计算模型、基于G-quadruplex的DNA逻辑计算模型、基于DNA自组装的逻辑计算模型、基于其他分子技术和分子材料的DNA逻辑计算模型。首先阐述了DNA逻辑计算的研究背景和研究目的以及现阶段在生物分子检测、疾病诊断、多因素分析和生物成像等领域的应用并简述其相关概念;然后梳理各DNA逻辑计算模型的研究历史和现状,分析各类逻辑计算模型所应用的分子操控技术和分子材料以及优缺点和应用前景;最后归纳总结DNA逻辑计算领域当前研究热点和发展前景,为未来提出全新的计算方式奠定基础,为信息、医疗等领域提供更好的服务。     

Information-Based Evaluation Criterion for Classifier's Performance

In the past few years many systems for learning decision rules from examples were developed. As different systems allow different types of answers when classifying new instances, it is difficult to appropriately evaluate the systems' classification power in comparison with other classification systems or in comparison with human experts. Classification accuracy is usually used as a measure of classification performance. This measure is, however, known to have several defects. A fair evaluation criterion should exclude the influence of the class probabilities which may enable a completely uninformed classifier to trivially achieve high classification accuracy. In this paper a method for evaluating the information score of a classifier's answers is proposed. It excludes the influence of prior probabilities, deals with various types of imperfect or probabilistic answers and can be used also for comparing the performance in different domains.     

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.     

基于句法结构特征分析及分类技术的答案提取算法

由于中文自然语言处理的特点和困难以及相应的语言处理基础资源的相对缺乏,使得国外一些成熟技术和研究成果不能直接应用到中文问答系统中.为此,针对中文事实型问答系统,提出一种新的基于句法结构特征分析及分类技术的答案提取算法,该方法将答案提取问题看成是候选答案的分类问题,即将候选答案分类为正确和错误两类.首先,该方法根据与问题类型所对应的候选答案的类型信息,从文本片断中提取出候选答案及其在句子中的简单特征和句法结构特征;然后利用这些特征训练分类器;最后用训练得到的分类器判别候选答案是否为正确答案.针对中文事实性问题,该方法与目前典型的基于模式匹配的中文答案提取算法相比,准确率提升6.2%,MRR提升9.7%.     

一种基于聚类和统计分析DNA基因芯片图像处理算法

DNA基因芯片可以同时监控成千上万个基因的表达信息。图像分析是基因芯片试验中一个重要的环节,直接影响到其后续的处理、分析和研究,比如鉴别预测具有不同表达信息的基因功能。基因芯片图像分析包括三个步骤:图像网格化,图像分割以及信息抽取。该文主要研究分割和信息抽取问题。首先基于K-Means聚类技术提出了一种新的分割方法;其次基于统计分析文章建议了一种新的背景和前景分割校正方法用于更准确的信息抽取。新方法的优点是对于基因芯片中spot图像没有任何形状限制。实际图像分析结果与目前最流行的基因芯片图像分析软件GenePix对比研究表明该文算法是精确有效的。     

It started with Watson and Crick,but it sure didn't end there: Pitfalls and possibilities beyond the classic double helix

The Watson-Crick double helix is perhaps themost predictable and programmable of allintermolecular interactions. In addition toits biological role in the cell, double helicalDNA is used for DNA-based computation and forDNA nanotechnology. The success of theseapplications has been based on the reliabilityof Watson-Crick base pairing, and, in thelatter case, circumventing the linearity of thedouble helix. We survey some of thealternative base pairing structures that can befound in synthetic systems, indicating motifsthat can be propagated and giving examples ofmispairing that can occur within the doublehelical context. We discuss some of the morecommon covalent modifications of nucleic acids. We also indicate the structural interplay ofspecial sequences and negative supercoiling. In addition to the caveats that wepresent involving unexpected results in nucleicacid systems, we show that the process ofreciprocal exchange and the generalization ofcomplementarity can be used to generatebranched DNA motifs for use in DNAnanotechnology or DNA-based computation. Weshow that these motifs can be used for thedirected construction of DNA objects, for thegeneration of specific designed patterns intwo-dimensional lattices, for computation byself-assembly, and for the fabrication ofDNA-based nanodevices. The use ofnon-Watson-Crick DNA leads inherently both toerrors and to thrilling possibilities. Successfully juggling these aspects ofgeneralized nucleic acid structure is anexciting challenge to investigators in thearea.     

基于DNA计算的分子下推自动机(英文)

DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程．2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究．该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构．文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法．接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输人字符串限制和输入分子形式不统一的问题．计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机．