新書推薦：
《
钱穆：国史新论
》
售價：NT$
354.0
《
洪武元年：大明开国的罪与罚
》
售價：NT$
302.0
《
大学问·从东方到中亚——19世纪的英俄“冷战”（1821—1907）
》
售價：NT$
411.0
《
元宴
》
售價：NT$
978.0
《
米兰讲稿（翁贝托·埃科作品系列）
》
售價：NT$
1030.0
《
无线重构世界：射频技术的过去、现在与未来
》
售價：NT$
562.0
《
海外中国研究·南方的将军：孙权传
》
售價：NT$
614.0
《
历史的深度
》
售價：NT$
302.0
|
| 編輯推薦： |
|
《DNA计算核酸编码原理及方法》可作为从事DNA计算、纳米结构设计、分子自组装、高性能的计算的研究学者和学生的参考书，对相关专业的教师和科研人员进行科学研究也具有一定的参考价值。
|
| 內容簡介： |
|
DNA计算是借助于分子生物技术进行计算的新方法。凭借着极大的存储密度和高度并行性，DNA计算为求解NP完全问题等复杂组合优化问题提供了一条全新的途径，开创了广阔的应用前景。《DNA计算核酸编码原理及方法》主要介绍DNA计算核酸编码原理及方法，具体包括DNA计算的研究进展和背景、DNA计算的生物化学基础、DNA编码问题及其复杂性分析、DNA二级结构预测和最小自由能模型、隐枚举核酸序列编码算法、DNA编码在图着色DNA计算中的应用。
|
| 目錄：
|
第1章DNA计算的产生与发展
1.1国内外研究进展
1.2DNA计算问题难点
1.3DNA计算编码方法的研究意义
第2章DNA计算的生物化学基础
2.1DNA的分子组成和结构
2.2DNA计算生物化学操作
2.2.1DNA的变性、复性和杂交
2.2.2PCR扩增
2.2.3凝胶电泳分离
2.2.4DNA链的外切
2.2.5DNA链的内切
2.2.6DNA链的连接
2.2.7特定DNA分子的提取
2.2.8DNA序列的测定
2.3DNA分子计算的实现途径
2.3.1基于溶液反应的DNA分子计算
2.3.2基于表面的DNA计算
2.3.3基于DNA芯片的DNA计算
第3章DNA编码问题及其复杂性研究
3.1DNA编码研究的重要意义
3.2DNA编码问题的复杂性分析
3.3DNA编码约束及分析
3.3.1基于汉明距离的编码约束
3.3.2DNA二级结构约束
3.3.3DNA化学特性约束
3.3.4DNA子序列碱基组成约束
3.4DNA序列设计算法
3.5基于热力学和汉明距离编码方法的分析比较
3.5.1限制非特异性杂交的完备性比较
3.5.2汉明距离的编码方法计算量分析
3.5.3基于热力学的编码约束分析
3.5.4核酸编码方法比较
第4章DNA二级结构预测和最小自由能模型
4.1DNA二级结构模型
4.2动态规划DNA二级结构预测算法
4.3改进的动态规划回溯树搜索
4.4近邻热力学模型和最小自由能
4.4.1NearestGNeighbor热力学模型
4.4.2WatsonGCrick堆栈结构及其热力学模型
4.4.3内单核苷酸错配结构及其热力学模型
4.4.4内环结构及其热力学模型
4.4.5凸环结构及其热力学模型
4.4.6发卡结构及其热力学模型
4.4.7悬挂末端结构及其热力学模型
4.4.8多分支环和外环
4.4.9DNA二级结构预测例子
第5章基于遗传算法的DNA平面伪结的预测算法
5.1遗传算法概述
5.2遗传算法的原理与方法
5.2.1产生初始种群
5.2.2根据目标问题构造适应度函数
5.2.3选择适应度高的个体进行杂交和变异
5.2.4若干次迭代后最高适应度值的为最优解
5.3遗传算法和传统搜索算法的比较
5.3.1梯度下降法
5.3.2模拟退火算法
5.3.3遗传算法
5.4遗传算法预测含平面伪结的DNA二级结构
5.4.1适应度函数
5.4.2选择运算
5.4.3交叉运算
5.4.4变异运算
5.4.5算法流程图
5.4.6算法比较与分析
第6章隐枚举核酸序列编码算法
6.1隐枚举核酸序列设计算法
6.1.1生成所有的DNA序列n元组
6.1.2算法思路及步骤
6.2DNA编码约束转换隐枚举评估函数
6.2.1转换汉明距离约束
6.2.2转换相似度约束
6.2.3转换HGmeasure约束及3′端HGmeasure约束
6.2.4转换反补汉明距离约束
6.2.5转换自补汉明距离约束
6.2.6转换单链二级结构约束
6.2.7转换连续性约束
6.2.8转换GC含量约束
6.2.9转换解链温度约束
6.2.10转换最小自由能约束
6.2.11转换限定子序列约束和重叠子序列约束
6.2.12转换模版序列约束
6.2.13多约束的隐枚举评估函数
6.3算法收敛性分析
6.4同其他编码算法的比较
6.4.1隐枚举算法和模板G映射算法的编码比较
6.4.2隐枚举算法和模拟退火算法的编码比较
6.4.3隐枚举算法和遗传算法的编码比较
6.4.4隐枚举算法和最小子串算法的编码比较
6.4.5隐枚举算法和多目标进化算法的编码比较
6.4.6隐枚举算法和动态规划算法的编码比较
第7章DNA编码在图着色DNA计算中的应用
7.1图顶点着色DNA计算算法
7.2DNA编码设计在图着色DNA计算中的应用
第8章DNA二级结构的平面嵌入算法
8.1图
8.1.1有向图
8.1.2可平面图
8.1.3顶点的度和图的度
8.1.4连通图
8.2STG编号平面嵌入算法
8.2.1STG编号算法
8.2.2平面嵌入
8.3DNA二级结构平面嵌入算法
8.3.1布局算法
参考文献
后记
|
| 內容試閱：
|
第1章DNA计算的产生与发展
DNA（deoxyribonucleic acid）计算是借助于分子生物技术进行计算的新方法，凭借极大的存储密度和高度并行性，DNA计算为求解NP完全问题等复杂组合优化问题，提供了一种全新的途径，开创了广阔的应用前景。DNA编码质量的优劣决定了DNA计算的效率，DNA编码数量的多少决定了DNA计算可求解问题的规模，因此核酸编码是DNA计算研究中的重要课题。
随着20世纪70年代初期计算复杂性理论的形成，科学工作者发现并证明了大量来源于实际的组合优化问题是非常难求解的问题，即NP完全问题和NP难问题。20世纪80年代初期，应运而生了一系列现代优化计算方法，如模拟退火算法、遗传算法、蚁群优化算法、粒子群算法和人工神经网络算法等。这类算法中的每一个算法都以自然、人类、生物的行为方式或物质运动形态为背景，经过数学抽象建立算法模型，通过电子计算机来求解组合优化问题。然而，这些基于仿生计算的优化计算方法不能在有效的时间中找到最优解，而用次优可行解来代替最优解；即使算法找到了最优解，算法本身也并不能证明其是最优解。因此这一系列建立在模仿分子运动、遗传学、动物学、神经系统的现代优化算法并不能彻底解决复杂的组合优化问题。
DNA计算是一种基于DNA分子的并行计算模型，是在计算科学和分子生物学的基础上发展起来的一个新颖而极具发展潜力的交叉学科，这种基于生物分子的计算模式在求解NP完全问题时显示出了极大潜力。
1994年，美国南加州大学的Adleman\[1\]用DNA分子进行计算，求解出7个顶点的有向Hamilton路问题，成功地利用现代分子生物技术在DNA溶液的试管中进行了实验。这一研究成果很快引起了计算机、数学、分子生物学等领域的科学家的极大兴趣。它的重要意义不仅在于算法和速度，更在于采用了一种全新的介质作为计算要件，以生物技术来实现电子计算机无法解决的复杂组合优化问题。随后，在1995年召开的第一届国际DNA计算会议上，来自各个国家和地区的200多名科学家共同探讨并充分肯定了DNA计算机的可行性。该领域的专家普遍认为：一旦DNA计算机研制成功，其运算量是目前的传统计算机望尘莫及的，DNA计算是一个极具开发价值的研究领域。与传统的电子计算机相比，DNA计算机具有三个突出的优点：高度并行性、海量的存储能力、极低的能耗。
然而，当前DNA分子的操作技术的发展远不如电子计算机中的集成电路成熟。在DNA计算过程中，DNA分子间会发生非特异性杂交，导致实验出现错误甚至失败，极大降低DNA计算的可靠性和有效性。对DNA序列进行编码设计是DNA计算机研制中最为核心的问题。首先，编码质量的优劣决定了DNA计算的可靠性和有效性，直接影响着DNA计算能否按照预期的设计相互反应；其次，编码数量的多少决定了DNA计算求解问题规模的大小，与DNA计算机研究能否深入发展息息相关。所以，本书在详细分析编码质量和编码数量的主要影响因素的基础上，对DNA计算机中的编码问题及其算法进行了深入研究。
DNA计算的基本思想：DNA计算是以DNA相关的生物酶等作为基本材料，基于生化反应原理的一种新型的分子生物计算方法。利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，然后在生物酶的作用下，按照一定的规则将原始问题的数据运算映射成高度并行的DNA分子链可控的生化反应。最后，利用分子生物技术如聚合酶链反应（PCR）、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需要的运算结果。DNA计算的关键是将经过编码的DNA分子作为输入，在试管内或其他载体上经过一定时间完成可控的生物化学反应，最后提取出代表问题解的DNA分子。
1994年Adleman求解7个顶点有向Hamiltion路的实验解释了DNA计算过程的三个基本步骤，其有向图G如图1.1所示。
图1.1有向图G存在唯一Hamiltan路v0→v1→v2→v3→v4→v5→v6
1 有向图的每一个顶点都编码为唯一的DNA分子，有向图的每一条边用相邻两顶点的DNA分子补链各取一半组成。
2 在一定的反应条件下，代表顶点和代表边的DNA分子相互杂交，相互连接形成长的DNA分子，产生这个有向图的路径。
3最后检测出代表该Hamiltion路的DNA分子。具体计算过程如下。
（1）解的产生。首先将图1.1中各顶点vi用长度为20个碱基的单链DNAOi来代替，vi和Oi一一对应。若顶点vi和vj之间存在边ei，j，再根据Oi，Oj来合成图中各条边Oi→j，Oi→j同样由长度为20个碱基的单链DNA构成，前10个碱基取Oi的3′端10个碱基，后10个碱基取Oj的5′端10个碱基。这种DNA序列设计使得如果存在路径i→j和j→k，通过添加Oj的补链Oj，可以产生路径i→j→k。
如图1.2所示，以产生路径2→3→4为例，O2、O3、O4分别为20个碱基组成的单链DNA，代表v2、v3、v4三个顶点，O3是O3的补链。单链DNAO2→3和O3→4代表该有向图的边e2，3和e3，4。其中O2→3由O2的3′端10个碱基和O3的5′端10个碱基组成，O3→4由O3的3′端10个碱基和O4的5′端10个碱基组成。在O2→3和O3→4共同存在的DNA溶液中，加入一定浓度的O3，则代表路径2→3→4的双链DNA 就产生了。依此类推，当这一步连接反应包括了图1.1中所有的边ei，j时，图1.1中所有随机路径的DNA就可以在一步之间全部产生了。
图1.2产生DNA分子Hamiltion路径2→3→4
（2） 解的分离。在第（1）步中产生了各种路径，首先需要选出起点和终点分别为O0和O6的路径。使用O0和O′6作为引物，利用PCR对第（1）步的结果进行扩增，就能选择性地扩增那些从O0至O6的DNA路径。PCR扩增完毕后，DNA溶液中存在以O0为起点、O6为终点的不同长度的双链DNA，如图1.3所示。
图1.3以0开始6结尾的所有路径
由于从O0开始，每增加一个顶点，该双链DNA的长度就增加20个碱基。通过所有7个顶点的DNA路径，对应的碱基个数必须为140bp。通过凝胶电泳技术，在电镜下观察得到140个碱基对应的谱带，割下这条胶带，浸入双蒸水中提取DNA。（3） 解的检测。第（2）步得到了长度为140bp的DNA溶液，还要选出其中经过每个顶点各一次的DNA路径，如图1.4所示。应用亲和纯化法，选出经过所有顶点至少一次的DNA路径。先将DNA双链解开双螺旋成单链DNA，让其通过接有O1补的磁珠，只有含有O1序列的单链DNA才能由于互补链的结合而被滞留，这个操作分离出了经过O1的DNA。这样依次通过接有O2补、O3补、O4补和O5补的磁珠，最终得到了经过所有顶点至少一次的Hamilton路DNA分子。
图1.4以0开始6结尾的等长DNA链通过磁珠
将第（3）步的产物再进行PCR扩增，通过DNA测序等方法，检测目标DNA是否存在即可。1997年Garzon等\[2\]归纳了使用DNA分子解决计算问题的三个基本步骤：①问题编码encoding，这个步骤将现实计算问题映射转换为DNA分子计算模型；②相互反应interaction，这个步骤将设计好的DNA分子在一定温度、盐度和催化剂的作用下执行核心的生化计算；③解的提取extraction，这个步骤利用生物检测技术将代表解的DNA分子提取出来，使纳米级的DNA分子在宏观世界可见。
1.1国内外研究进展
Adleman实验的成功标志着科学家试图利用生物大分子DNA、RNA、蛋白质等来解决电子计算机无法求解的NP完全问题和构建新型的计算机的设想取得了重要突破，使DNA计算成为一个备受关注的学科，也使构建新型的计算机——DNA计算机成为可能。随后，国内外学者在Adleman 的分子计算模型基础上广泛开展了DNA 计算的研究工作，建立了一系列求解NP完全问题的DNA计算模型，如SAT、图着色、0-1规划、背包问题等计算问题的DNA 计算模型。1995年，受Adleman的启发，Lipton\[3\]提出DNA计算可以解决另一种NP完全问题——可满足性问题SAT。Lipton通过构造一个接触网络图，将SAT问题的解空间映射为通过接触网络图的起点和终点的所有哈密顿路。他首先利用DNA分子表示问题的所有可能解，然后利用生化反应删除非解。1996年，Roweis等介绍了一种新的DNA计算模型——粘贴模型，并用此模型解决了最小集合覆盖问题和数据加密问题。1997年，Ouyang等将另一个NP完全问题——图的最大团问题转化为最大独立集问题，利用并行重叠组装parallel overlap assembly，POA技术在实验室解决了一个6个顶点的最大团问题实例。1998年，Winfree等\[4\]设计出双交叉瓦片（tile分子DX，利用到DNA 分子间的碱基互补配对特性，由几条DNA 单链在特定位置互补，交错位置而形成分子结构，如图1.5所示。Winfree发现以DX分子作为组件可以实现规则结构的自组装。
……
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
