多重PCR引物设计的软件开发
目 录
第一章 引 言 ..................................................... 1 1.1 背景知识简介 ............................................... 1 1.1.1多重PCR引物设计简介 ................................... 1 1.1.2 遗传算法简介 ........................................... 2 1.2 相关文献综述 ................................................ 3 1.3 研究目的与成果 .............................................. 4 1.4 本章小结 .................................................... 4 第二章 问题分析 ................................................... 6 2.1 多重PCR引物设计问题的数学模型 .............................. 6 2.2 载体算法的选择 .............................................. 6 2.3 本章小结 .................................................... 7 第三章 相关生物学参数简介及其数学模型 ............................. 8 3.1 单个引物的约束参数 .......................................... 8 3.2 引物间的约束参数 ........................................... 11 3.3 本章小结 ................................................... 12 第四章 引物集评价体系 ............................................ 13 4.1 评价体系的数学模型 ......................................... 13 4.2 权值及其约束对象 ........................................... 14 4.3 本章小结 ................................................... 15
i
第五章 引物设计的遗传算法实现 .................................... 16 5.1 算法结构总览 ............................................... 16 5.2 引物设计问题在遗传算法中的数学表示 ......................... 16 5.3 初始化随机解集 ............................................. 17 5.4解的评估策略与双亲的选择 ................................... 17 5.5 交叉策略及交叉率的选择 ..................................... 18 5.6 变异策略及变异率的选择 ..................................... 19 5.7 收敛条件 ................................................... 20 5.8 本章小结 ................................................... 20 第六章 GAPrimer 简介 ............................................. 21 6.1 软件功能与特点概述 ......................................... 21 6.2 软件操作结构图 ............................................. 21 6.3 软件默认参表 ............................................... 22 6.4 本章小结 ................................................... 23 第七章 实验结果及数据分析 ........................................ 24 7.1 实验结果：三重PCR引物设计 ................................. 24 7.2 数据分析 ................................................... 24 7.3 本章小结 ................................................... 25 第八章 总结与展望 ................................................ 26 参 考 文 献 ....................................................... 27 附 录 ........................................................... 29
ii
第一章 引 言
1.1 背景知识简介
聚合酶链式反应(Polymerase Chain Reaction, PCR)是体外扩增DNA的一种技术；其能够在短时间内根据极微量的模板序列扩增出大量特异性DNA片断，扩增过程类似于核裂变。Mullis博士在1983年发明了该技术，并因此于1993年获得诺贝尔化学奖。PCR技术是现代分子生物学中最有价值的技术之一[1]；例如：人类基因组计划，亲子鉴定，对罪犯DNA的鉴别，都依赖于这一技术。
在聚合酶链式反应中，原始的DNA片段称为模板序列；待复制的DNA片段称为目标序列，它是模板序列的一部分；引导目标序列合成的寡核苷酸片段称为引物，其长度一般在16-27之间。每个反应一般含20至40个循环，每次循环目标序列含量翻一倍；每个循环由三个主要步骤构成：1.变性（90℃-96℃）：双链DNA模板在热作用下，氢键断裂，形成单链DNA；2.退火（25℃-65℃）：系统温度降低，引物与DNA模板结合，形成局部双链；3.延伸（70℃-75℃）：在Taq酶的作用下，以dNTP为原料，从引物的5′端→3′端延伸，合成与模板互补的DNA链。扩增一段目标序列需要两条引物，分别和目标序列的两端相匹配。引物的作用类似于电路里的开关，引物设计不好会导致产物杂乱无章（即扩增失败），因此引物设计是PCR成功的关键之一。引物设计需要综合考虑引物的退火温度，GC含量，引物长度，特异性等。现有的PCR引物设计软件已经非常成熟，可以达到较好的效果, 常用软件有PRIMER 3, PRIMER 5, OLIGO 6.0等。 1.1.1多重PCR引物设计简介
多重聚合酶链式反应（多重PCR）是指在同一试管中同时进行多个PCR，从而一次性扩增多个目标片段，因此节省了大量的时间和金钱，具有巨大的经济和时间效应。由于引物之间以及引物与模板序列之间的相互干扰，一方面导致了多重PCR引物设计考虑因素增加，另一方面极大地增加了计算的空间和时间复杂度。同时多重PCR引物设计问题需要被当作一个整体考虑，不能被分割为多个PCR引物设计问题的简单组合[2]。现尚
1
无完善的理论解决这一问题。综上所述，要实现多重PCR引物设计的自动化，在实践中需要解决两个问题：一、多重PCR引物设计的约束条件与评价标准；二、载体算法的选择。
1.1.2 遗传算法简介
遗传算法是一种随机优化算法，用于求解问题的全局最优解，尤其是对非线性问题的全局搜索和最优化。该算法由美国密歇根大学的John Holland教授于80年代提出，其借鉴了达尔文优胜劣汰的思想，以及遗传过程中的染色体交叉与变异的概念。虽然遗传算法尚未被完全从理论上证明，但遗传算法已得到比较成熟的发展，并广泛地被成功应用于各类实际问题；Schema定理部分证明了该算法的有效性[3]。
遗传算法主要步骤包括初始化，可行解的评估，交叉，变异，和收敛。每个步骤根据问题的性质与规模不同，均有多种策略可以选择。在实践中，要将遗传算法和问题结合需要解决如下几个问题：一、建立问题的数学模型并表示为数据结构；二、初始化策略的选择；三、挑选双亲与交叉策略的选择；四、变异策略的选择；五、收敛条件的选择；六、交叉率，变异率，初始解数目的选择。参见图1.1遗传算法流程图.
定义cost函数，定义变量表达式，选择GA参数
初始化可行解集计算cost(即评估可行解)选择双亲交叉变异No检查是否收敛Yes结束
2
图1.1遗传算法流程图
1.2 相关文献综述
由于多重PCR引物设计问题尚未在算法理论上得到完善解决，根据对文献的总结，一方面、国内对引物设计的自动化问题关注较少，鲜有文献记载；国外近几年已提出一些启发性的算法和相应的软件，例如MultiPLX[4][5]，但尚无宣称成熟的算法与软件。另一方面、为了满足现实需要国外也有比较成熟的大型系统采用常规的算法，使用大量并行计算机以及较长的时间来为大规模多重PCR设计引物，虽然较好地解决了问题，但这需要以大量的时间和金钱为代价，同时也将应用限制在大规模PCR引物设计问题上。例如日本的PrimerStation,使用了100个CPU(SunFire 15K)来为人类全基因扩增问题设计引物，耗时为3个月[6]。
在调查总结文献的基础上，本研究选择了遗传算法作为解决问题的载体，具体思路将在第二章中进行阐述。台湾国立中央大学与国立中山大学共有两篇论文运用了遗传算法进行了多重PCR引物设计的研究[7][8]；随后由李宗南教授总结后几位作者共同在05年国际遗传算法年会上公开提出用遗传算法来解决多重PCR引物设计这一观点[9]。以上两项工作基本类似，因此共同存在三个较大的问题：首先、虽然作者从计算机专家的角度出发强调了遗传算法的应用，但对生物方面的约束条件未进行详细的调查研究而考虑不周全，甚至存在一些生物概念的误解。例如:退火温度TM是设计引物时关键的约束条件之一，而计算TM时作者使用了60年代提出的理论估算公式：TM=(A+T)+4(G+C)，该公式忽略了影响退火温度的许多重要因素，已被实践证明无法准确估算退火温度，甚至无法适应单个PCR引物的设计[2]；又例如：作者将引物自互补和发夹结构两个概念误解为同一个，前者是指完全相同的两条引物互补从而产生二聚物, 而后者是指一条引物折叠后和自身产生互补从而形成发夹二级结构；其次、作者对多重PCR生物参数部分未做较好的建模从而导致了生物定义上的错误；例如：作者因未定义合理的引物评价制度，从而特异性条件无法满足，所以作者自行提出了二次特异性的概念来使条件得到满足，但这是不合理的；又例如：作者只区分了引物的合不合适，却未分出合适的引物之间的好坏。最后，作者虽然提供了三个范围的输入给用户，但未给用户提供反馈接口，实验者只能被动接受计算结果，而无法将信息反馈到机器中来设计合适的产物；此外、作者未
3
对遗传算法各参数和各部分未做较好的选择与调整。以上三个问题，前两个问题导致了程序不能成功地设计可以在实际实验中使用的多重PCR引物；最后一个问题导致了用户缺乏自主权，无法按照实际情况主导程序来选择合适的引物。综上所述，以上两项工作将遗传算法与引物设计问题结合从而给出了解决问题的新方法，但由于忽略了问题的实用方面从而导致问题未能实际解决。
1.3 研究目的与成果
工作目的归纳为：开发适用于中、小规模生物实验室的多重PCR引物设计软件；并将研究目的推广为：归纳总结开发多重PCR引物设计软件的一般性思路，提出启发性的方法，并将以上两项付诸实践检验；最后将研究思路概括为：针对性、实用性和一般性。
为了开发能够在实际生物实验中使用的应用软件，经调查研究后借鉴了应用遗传算法设计多重PCR引物的思想，对多重PCR引物设计软件开发问题的其它部分进行了独立的调查研究与设计。调查总结了多重PCR引物设计中的生物参数，参考了部分成熟的单重PCR引物设计软件，研究了多目标优化算法；最终建立了解决问题的数学模型， 选择了遗传算法作为载体并优化了其各部分的参数和选择计算策略。开发出在个人电脑(DELL INSPRION 630m; CPU: Pentium IV, 1.89GHz; RAM: 512MB)上可运行的多重PCR引物设计软件GAPrimer并撰写了相关用户操作手册；为了使软件在以后能在一个更广泛的领域被应用，以及受到可利用文献资源的限制，开发过程为全英文环境。GAPrimer使用了23个参数来约束14个生物学条件，通过14个权值来控制上述14个条件，并DOS下操作系统给用户提供了简易的人机接口使得以上37个参数均对用户开放；另外，GAPrimer 可以用于对40个引物以下的引物集合评估，还可以用于格式化从网上下载的序列。
1.4 本章小结
本章的目的是为下文建立背景框架：首先回顾了相关的背景知识，随后根据研究目
的和工作情况总结了相关文献，最后阐述了研究目的成果；下文中将以GAPrimer的建立过程为基础，对多重PCR引物设计的软件开发问题进行系统的阐述，并对在本章中提出的问题做出详细的解答。下文将按研究思路发展的顺序分七个章节进行阐述: 问题分析、相关生物学参数简介及其数学模型、引物评价体系、引物设计的遗传算法实现、
4
GAPrimer 简介、实验结果及数据分析、总结与展望。
5
第二章 问题分析
2.1 多重PCR引物设计问题的数学模型
多重PCR引物设计问题是建立在PCR引物设计的基础上的多目标优化问题。一方面需要让每对引物满足单重PCR引物的约束条件，另一方面要考虑引物之间的相互影响；与此同时，多重PCR引物设计问题需要被当作一个整体考虑，不能被分割为多个PCR引物设计问题的简单组合[2]。由此可见，多重PCR引物设计是个全局优化问题，同时也是多目标优化问题。
目前，多重PCR引物设计问题在算法上已被证明为完全非确定多项式(NP-COMPLETE)问题,这意味着解决该问题的高效算法是基本上不存在的[10]。对于NP-COMPLETE问题，找到全局最优解的唯一方法是穷举所有可能的情况，由于多重PCR引物设计考虑因素较多、数据量较大，因此依靠穷举来实现是多重PCR引物设计基本不可能的。
综上所述，可以认为多重PCR引物设计问题的可行数学模型有两个特点：一、该模型应适用于多目标优化算法；二、该模型可以较完整地表达NP-COMPLETE问题；同时从实用角度出发，该模型应允许使用者来定义什么是合适的引物。
2.2 载体算法的选择
选择载体算法主要需要考虑可行性。根据对文献的总结，GAPrimer选择了遗传算法作为解决问题的载体，关于遗传算法的简介和其他相关多重PCR引物设计算法的介绍请参见第一章。选择的原因如下：首先、遗传算法已经比较成熟，并已被成功运用到许多NP-COMPLETE问题上，这和多重PCR引物设计问题性质相符合。其次、遗传算法可利用的方法和参考资料较丰富，这为问题解决提供了更多的途径；再次、遗传算法长于解决全局优化问题，而且多目标优化问题是其主要应用对象之一，这使得该算法能够从全局上解决多重PCR引物设计问题。最后、第一章中提及的两篇相关文献的结果[8][9]证实了遗传算法在多重PCR引物设计问题上的可行性。
6
2.3 本章小结
本章对问题性质进行了分析，并阐述了选择遗传算法的原因，一方面为了启发读者选择并应用新的算法到多重PCR引物设计问题上，从而使问题得到更好的解决。另一方面、本章中仅对问题进行了分析，为下文提供相关背景，关于建立数学模型的具体内容将在三、四两章中进行阐述。遗传算法的应用将在第五章中进行讨论。
7
第三章 相关生物学参数简介及其数学模型
设计多重PCR引物，首先要解决引物评估问题，即回答什么是合适的引物，以及这些引物的相互干扰是否在可接受的范围内。因此多重PCR引物设计问题中要考虑的生物参数分为两部分：首先是确定单个引物的约束参数，据此可以区分引物的优劣；其次是确定引物间的约束参数，据此来评价引物之间的干扰是否在可接受的范围内。下文就以上两部分参数分别进行了讨论，并给出了相应的数学模型。同时，本章也中给出了一些关键生物参数在GAPrimer中的具体评估算法，和对算法的改进意见。
3.1 单个引物的约束参数
根据对文献的总结，GAPrimer对单个引物考虑了如下10个约束条件：引物长度、引物退火温度、引物的GC 含量、二级发夹结构、寡核苷酸长度、自互补、3’端自互补、GC夹[11]、特异性、3’端稳定性[12]。
（1）引物长度(Primer Length)：引物长度指引物上的碱基数目。模型中使用引物长度上界，引物长度下界和引物长度理想值三个参数来约束；默认范围为[18，27]，理想值为20。
（2）引物退火温度(Melting Temperature, TM)：引物退火温度指引物与模板序列结合的温度。模型中使用退火温度上界，退火温度下界和退火温度理想值三个参数来约束。默认范围为[57,63],理想值为60，单位为摄氏度；此外模型中使用了单价阳离子浓度和配对引物浓度两个参数来对退火温度进行盐浓度校正，默认值分别为50mM、50nM[12]。退火温度的计算使用了Nearest Neighbor(NN)模型以及SantaLucia 的NN模型参数及其相应盐浓度校正公式[13]。也有其他NN模型参数可以用来计算退火温度，但根据文献记载，以上NN参数是较新、预测较为准确的模型，因此本程序选择此模型为默认方法。程序中采用了最基础的扫描算法，但也有较高效的算法可以完成这一任务,例如分式编程[14]。
此外，TM的定义是溶液中50%引物与模板发生结合的温度，虽然计算TM是目前最普遍的观点，并且在目前的单重、多重PCR中应用得较好，但事实上更为准确的约束应该是计算引物的熵值(delta G)[2]。因此，为了提高多重PCR引物设计的效果，可以将此项
8
约束转化为引物熵值的计算。
（3）引物GC含量(GC Content)：引物GC含量指引物中含有鸟嘌呤(G)和胞嘧啶(C)的百分比。模型中使用GC含量上界，GC含量下界，GC含量理想值三个参数来约束。默认范围为[40，60]，默认理想值为0，0表示不考虑默认理想值，通过设定一个非零值可以激活次参数。
（4）自互补(Self Complement)：自互补指引物自身和自身发生互补，结果是形成非特异性的二聚物。模型中使用最大互补值这个参数来约束，默认值为7。
GAPrimer借鉴了Primer 3的评分系统来预测形成二聚物的可能性，对于每对互补的碱基对评分为+1，对于每对错配的碱基对，分数为-1，总分不可为负，总分为0表示形成二聚物的可能性很小[12]。图3.1中的总分为2。在这种评分体制下，7分以下（含7分）的引物基本可以成功引导实际多重PCR实验[15]。然而更精确的评分方法是用NN模型估测熵值[16]，但此方法会很大程度加重程序的计算复杂度，现有引物设计软件基本不用。
5' GCTAGCCTGTAGTATTCGTA 3' | × | | × | 3' ATGCTTATGATGTCCGATCG 5'
图3.1引物互补评分体系举例
3'5'5'5'3'5'3'5'5'3'5'3'3'3'3'5'
图3.2引物互补扫描方法
GAPrimer中的算法，按照常规扫描了所有的可能组合，图3.1中引物长度为20，有39种可能组合。引物在程序中按图3.2中的方式移动，取所有可能组合中的最大值作为引物的该项的分数。
（5）3’端自互补(3’End Self Complement)：3’端自互补指引物在其3’端与自身发生互补配对，由于延伸是在3’端开始的，所以应该避免引物间3’端的互补。模型中使用最大末端互补值这个参数来约束。默认值为3。评分体系和扫描算法同第四项（自互补），但3’端自互补仅考虑在3’端开始的不间断的互补。
9
（6）发夹二级结构(Hairpin Secondary Structure)：发夹结构是经引物自身互补折叠后形成，其包括两部分：主干(stem)和环(loop)，参见图 3.3。模型中使用最大发夹结构互补值这个参数来约束，默认值为3。
发夹二级结构的评分体系与自互补相同，图3.2中引物的总分为3。据文献记载，最稳定的发夹结构为环中含有4个或5个碱基的结构，主干中至少含有两对碱基[15]；据此，扫描算法扫描所有可能的环中含4个或5个碱基的结构，例如图3.3中的引物，长度为23，需要比较176次。最后取所有可能组合中的最大值作为该项分数。
loopstem GG GCATGCATGCTGA 5'A | | | × | CT CGTTC 3' stem
图3.3引物发夹二级结构
（7）寡核苷酸长度(Poly X)：寡核苷酸长度指引物中相同碱基连续出现的次数, 例如寡核苷酸片段TTTTT，其长度为5；在设计引物是应避免此现象出现。模型中使用了最大寡核苷酸长度这个参数来约束，默认值为5。
（8）GC夹(GC Clamp)：GC夹指在引物3’端左后几个碱基中含有几个G或C，GC夹可以增加3’端稳定性。模型中使用最少GC夹个数这个参数来约束。默认值0，0代表默认不考虑这一项。GAPrimer中考虑了3’端最后的3个碱基，因此最少GC夹个数最高可设为3。
（9）特异性(Specificity)：特异性指引物在模板上有唯一的结合点，而不会在错误的结合点上和模板发生结合。模型中使用最大误配值这个参数来约束，默认值为9。
评分体系和自互补中的体系相同；扫描算法考虑所有可能的组合情况：引物相对于模板的移动与图3.3引物自互补扫描算法中的类似；取所有可能组合的最大值作为该项的评分。
（10）3’端稳定性(3’End Stability)：3’端稳定性指引物3’端最后5个碱基的熵值，熵值越小代表越稳定。模型中使用最大三端稳定性这个参数来约束。3’端稳定的组合为‘GCGCG’,使用NN模型以及SantaLucia 的NN模型参数计算，可得其熵值为-6.86 kcal/mol[12]。因此取-6.9 kcal/mol为最大三端稳定性默认值，该值不允许用户改变。
10
3.2 引物间的约束参数
根据对文献总结，GAPrimer对多个引物之间，以及引物对的考虑了如下6个约束条件：引物长度差、退火温度差、引物间互补、引物间3’端互补、产物长度、产物间长度差。
（1）引物长度差(Primer Length Difference)：指引物之间的长度差，引物设计需要是所有引物的长度尽量接近。模型中使用引物最大长度差这个参数来约束，默认值为3。算法中需评估所有可能的引物对，最后取所有长度差之和的平均值作为整个引物集的长度差。n重PCR需要2n个引物，因此需评估2n2-n种组合。
（2）退火温度差(TM Difference)：指引物间退火温度之差，由于所有的引物在同一试管中发生反应，因此退火温度要尽可能相似。模型中使用最大退火温度差这个参数来约束，默认值2，单位为摄氏度。算法中需评估所有可能的引物对，最后取所有退火温度差之和的平均值作为整个引物集的退火温度差。n重PCR需要2n个引物，因此需评估2n2-n种组合。
（3）引物间互补(Complement)：引物间互补指不同引物之间的互补，结果是形成二聚物。模型中使用最大互补值这个参数来约束，默认值为7。评估所用评分体系和扫描算法均与评估自互补中所用的相同。
算法需要评估所有可能的引物对，最后取所有互补分数之和加上自互补分数的平均值作为整个引物集的互补分数。n重PCR需要2n个引物，因此需评估2n2-n种组合[17][18]，此外需加上对2n个引物自互补的组合的评估。
（4）引物间3’端互补(End Complement)：引物间3’端互补指不同引物之间的3’端互补，结果是形成二聚物。模型中使用最大末端互补值这个参数来约束，默认值为3。评估所用评分体系和扫描算法均与3’端自互补中所用的相同。
算法需要评估所有可能的引物对，最后取所有3’端互补分数之和加上3’端自互补分数的平均值作为整个引物集的3’端自互补分数。n重PCR需要2n个引物，因此需评估2n2-n种组合，此外需加上对2n个引物3’端自互补的组合的评估。
（5）产物长度(Product Length Difference)：产物长度指最终产生的产物的长度，一方面，产物序列中应该包含目标序列；另一方面，产物越长成本越高，因此需限制产物长度。程序中使用最大产物与目标序列长度差这个参数来约束，默认值为150，代表产物的长度最大超过目标序列长度150个碱基。
11
（6）产物间长度差(Product Length)：多重PCR的产物在同一试管中，为了在凝胶电泳中区分不同的产物，需要使产物间有一定的长度差。模型中使用产物长度差上界和产物长度差下界这两个参数来约束，默认范围是[50,100]。
算法需要评估所有可能的产物对，最终取长度差之和的平均值作为整个引物集的产物间长度差。n重PCR需要需评估(n2-n)/2种组合
3.3 本章小结
本章中介绍了14个独立的生物学约束条件，及其相应的23个约束参数；同时讨论了相关的评估模型与算法；并提出了一些改进意见。这14个约束条件为引物集综合评价体系的建立提供了基础，对引物集的综合评价体系的建立将在第四章中进行讨论。
12
第四章 引物集评价体系
4.1 评价体系的数学模型
首先，由于多重PCR引物设计是多目标优化问题，不能只简单地评价某个引物集是否合适,也基本不可能完全满足每一个条件；一个比较合理的可行方法是评估引物集合所有的属性，然后提供一个综合评价体系框架，然后把决定权交给使用者。其次，遗传算法需要一个宽松的限制条件，这有助于算法搜索到全局的最优解[19]；因此该评价体系应该提供一个约束较小的环境，从而为遗传算法的应用提供基础。GAPrimer中所采用的数学模型首先评估上述14个独立生物学约束条件，然后通过14个权值来平衡这14个约束条件，并依此建立起引物集评价体系。
模型首先对每一个约束条件归一化，给出位于区间[0, 1]的评分Si，参见公式4.1；分数越低表示该项约束条件满足得越好，0代表该项条件完全被满足。为了提供宽松的约束环境，程序并不抛弃某项分数超过1的引物，除非这些引物其它所有约束项综合起来有助于提高整个引物集合的综合质量，否则这些分数超过1的引物会在程序中自动被淘汰。此外，是否保留这样的引物集合最终是由用户通过权值设定来决定的。
在各项分数都给出后，针对每一项模型中给出位于区间[0, 100]的权值Wi，Wi为浮点数，所有14个权值的和为100，参见公式4.1。以上模型代表对于多重PCR引物设计问题的14个约束条件用户给以的考虑程度在整个问题中所占的百分比。例如，Wi=20，代表用户在整个问题用户对i条件给以20%的考虑。从另一个角度理解，实际上用户通过对模型中权值的设定定义了一个平衡点；因此这种模型允许用户来决定什么才是选择的标准。另外，程序允许用户设定的所有权值的和不等于100，程序会将这些权值归一化后放大100倍，从而保证在任何权值系统下所有权值的和均位于区间[0, 100]；无论用户采用何种权值设定，用户永远是在设定整个问题的一个平衡点。
最后，模型综合了权值和各项分数，给出了位于区间[0, 100]的综合分数Score，参见公式4.2。由于对14个约束条件施加了宽松的评价体系，因此某个引物集的综合分数可以超过100，这代表这个引物集不在用户设定得范围内，但这样的引物集一定会在遗
13
传算法中被淘汰，除非它是最优解。综合分数为0的引物集是理想引物集，这样的引物集不存在任何干扰，当然这是基本上不可达到的；综合分数小于100的引物集都是满足条件的引物集，综合分数越低引物集的综合质量越好；例如，引物集的综合分数为40，代表了这个引物集已经达到了理想引物集60%的效果。
根据GAPrimer运行的结果统计，一般分数在50以下的引物集都具有较好的质量，从在理论上而言完全能够成功地引导多重PCR；当然分数低于100的引物集都是满足条件的，但程序的任务是根据用户设定的平衡点找出解决问题的全局最优解。
Si[0,1], Wi[0,100], Wi100 (4.1)
i1n14ScoreWiSi, Score[0,100] (4.2)
in综上所述，GAPrimer所使用的数学模型中满足条件的引物集的分数小于100，分数越低引物集质量越好；模型也帮助用户定义了一个解决多目标优化问题的框架，并通过14个权值使得用户可以设定整个问题的平衡点。在下一届中将对14个权值进行详细的描述，指出其含义及其约束的生物学条件，并给出默认值。
4.2 权值及其约束对象
（1）约束引物长度的权值(Weight for Primer Length) ：默认值为10，提高此权值可以使
引物长度更接近用户设定的引物长度理想值。
（2）约束引物长度差的权值(Weight for Primer Delta Length) ：默认值为10，提高此权
值可以使引物集长度差缩小。
（3）约束退火温度的权值(Weight for Tm) ：默认值为10，提高此权值可以使退火温度
更接近用户设定的退火温度理想值。
（4）约束退火温度差的权值(Weight for Delta Tm) ：默认值为10，提高此权值可以使引
物集退火温度差缩小。
（5）约束GC含量的权值(Weight for GC Content) ：默认值为5。若用户已设定GC含量
理想值，则提高此权值可以使引物GC含量更接近理想值；若用户未设定GC含量理想值，则提高此权值意味着对引物GC含量给以更多的考虑，从而保证引物集中所有引物都落在用户设定的区间内。
14
（6）约束引物间互补与引物自互补的权值(Weight for Complement) ：默认值为10，提高
此权值可以使引物间互补与引物自互补的可能性减小。
（7）约束引物间3’端互补与引物3’端自互补的权值(Weight for End Complement) ：默认
值为10，提高此权值可以使引物间3’端互补与引物3’端自互补的可能性减小。 （8）约束发夹二级结构的权值(Weight for Hairpin Structure) ：默认值为5，提高此权值
可以使引物形成发夹二级结构的可能性减小。
（9）约束GC夹的权值(Weight for GC Clamp) ：默认值为5，提高此权值可以使引物3’
端G/C个数增加，从而增加稳定性。
（10）约束特异性的权值(Weight for Specificity) ：默认值为10，提高此权值可以使引物
非特异性结合的可能性减小，从而更有力地保证引物在整个模板上仅存在唯一的 特异性结合点。
（11）约束寡核苷酸长度的权值(Weight for Poly-X) ：默认值为5，提高此权值可以使引
物含有长寡核苷酸的可能性减小，并使引物上寡合酸的长度减小。
（12）约束3’端稳定性的权值(Weight for End Stability) ：默认值为5，提高此权值可以
使引物3’端稳定性增加。
（13）约束产物长度的权值(Weight for Product Length) ：默认值为2.5，提高此权值可以
使产物长度减小。
（14）约束产物长度差的权值(Weight for Product Delta Length) ：默认值为2.5，提高此
权值可以更有力地保证产物间的长度差落在用户设定的范围内。
（15）反之，由于用户是在通过权值定义解决整个问题平衡点，是在定义对每个生物学
约束条件给予多少百分比的考虑；因此提高上述任一个权值的同时也意味着用户在其它项上将得到稍差的质量。
4.3 本章小结
本章总结了引物集评价体系的数学模型，介绍了14个权值。至此，生物学方面的工作已基本结束。遗传算法中对引物集的评估将建立在本章和第三章的基础上，在第五章中将具体讨论如何将遗传算法与多重PCR引物设计问题相结合，例如：如何调整遗传算法各参数与如何选择合适的策略。
15
第五章 引物设计的遗传算法实现
5.1 算法结构总览
遗传算法是一种传统穷举算法和带导向的随机搜索算法的结合，属于进化算法的一种[20]，擅长于搜索问题的全局最优解[19]。按约束变量的数目遗传算法有分为单目标优化遗传和多目标优化遗传算法[20]，多重PCR引物设计问题属于多目标优化问题。关于遗传算法的简介请参见第一章，关于遗传算法的流程图请参见图1.1。
将遗传算法应用于多重PCR引物设计问题主要需要解决以下六个问题：一、问题在遗传算法中的表示；二、随机解集的初始化；三、引物集的评估与双亲的选择；四、交叉策略与交叉率的选择；五、变异策略与变异率的选择；六、收敛条件的决定。本章将就以上六个问题在本章中展开讨论，一方面介绍GAPrimer中所采用的解决方法，另一方面提出改进建议。
5.2 引物设计问题在遗传算法中的数学表示
遗传算法根据问题采用的数据结构不同可以分为二进制遗传算法，连续型遗传算法，树型遗传算法等；不同的数据结构的遗传算法的初始化、评估、交叉、变异以及收敛策略都不同；而采用何种数据结构主要取决于所解决问题的性质[21]。本文中采用了实数来表示问题，因此属于连续型遗传算法(Continuous GA)。
设计数据结构一方面要顾及数据所占的空间；另一方面要能充分表达引物的特点，使后续步骤容易进行。每一对引物包含前向引物(Forward Primer)和逆向引物(Reverse Primer)两条引物。唯一确定一条引物至少需要两个独立的条件：一、引物在模板序列上的开始位置；二、引物的长度。
因此GAPrimer采用了四个整数来表示一对引物：前向引物开始位置SF ，前向引物长度LF，逆向引物开始位置SR，以及逆向引物长度LR。n重PCR需要n对引物，因此每一个引物集由4n个整数组成，参见图 5.1。
SF_1LF_1SR_1LR_1SF_iLF_iSR_iLR_iSF_4nLF_4nSR_4nLR_4n
16
图 5.1 数据结构
5.3 初始化随机解集
上一节中解决了问题的数据结构，本节将讨论如何根据这个数据结构初始化随机解集。初始化随机解集需要解决两个问题：一、决定人口数量(Population)，人口数量为n表示引物；二、决定初始化条件。
在一定的程度上增加人口数量可以提高遗传算法的性能，但同时人口数量的增加意味着程序时间效率和空间效率的巨大下降；然而当人口数量达到一定程度时，再提高人口数量并不能显著提高遗传算法性能[3]。因此在实际调试后选择了人口数量为90；这表示在整个人口中将存在90个引物集，每一个引物集都是多重PCR引物设计问题的一个可能解。
在初始化随机解集时应该加以宽松的限制[19]，不应该评价引物集的好坏，质量不好的引物会在程序运行时被淘汰。据此，GAPrimer采用了三个约束条件来完成初始化：一、引物长度应该落在用户设定范围内，即LF、LR是属于[20, 27]的一个随机整数；二、前向引物开始位置SF应小于目标序列的开始位置；三、逆向引物开始位置SR应大于目标序列的结束位置；二、三两个条件保证了最终产物中包含了目标序列。
5.4解的评估策略与双亲的选择
在完成初始化后，本节将讨论遗传算法中评估引物集的策略以及双亲的选择策略。首先需要注意引物集的综合分数(Score)与遗传算法中引物集评估分数(fitness)是不同的概念[22]。前者仅仅表示某个引物集的质量的优劣；而后者则是由前者演变而来，其更准确地表示了引物集之间的差别，并且后者能够保证遗传算法不会过快的收敛到本地最优解上[22]，遗传算法中使用的是后者。fitness有几种计算方法，由引物集的综合分数是大于0的单调函数，而且具有一定线性，因此GAPrimer选择了线性变换法，此方法有助于区别综合分数比较接近的引物集之间的差别[23]。
在计算完fitness之后，整个人口按照各自的Fitness由小到大排序，fitness最小的解代表了本代(generation)中质量最好的引物集。为了保留最优解GAPrimer采用最优解保留策略(elitism), 这个引物集在后续的交叉和变异中将不会被改变，直至在后续的代中出现比其综合分数更小的引物集来取代它。
17
选择双亲有几种方式，但都有两个条件需要满足：一、要使本代中较优秀的性状有更大的概率遗传到下一代中；二、要使性状具有多样性，即fitness较大的引物集应该也有概率被选为双亲。俄罗斯轮盘法建立在概率的基础上，其是遗传算法选择双亲常用的一个标准配置[3]，GAPrimer选择了此法来选择双亲；此方法一方面保证了fitness较小的引物集具有更大的概率被选择为双亲，另一方面也为fitness较大的引物集保留了被选中的可能性，从而满足了上述的两个条件。关于俄罗斯罗盘的具体算法请参见文献[3][22]。
5.5 交叉策略及交叉率的选择
完成双亲的选择后需要对双亲进行交叉和变异来产生新的一代，这也是遗传算法进化的基础。完成交叉首先要决定交叉率(crossover rate, NKEEP)，交叉率位于[0, 1]区间，最终保留的用于挑选双亲的人口数等于交叉率和总人口数的乘积，参见公式5.1。交叉率过大时遗传算法退化为随机穷举算法，交叉率过小时遗传算法不能完成进化；根据文献记载，既能保证有效进化又能保证算法收敛速度的交叉率位于0.5左右[3]，在实际调试后，GAPrimer中选择了交叉率为0.6；上文中提及总人口数为90，因此最终保留的人口数为54，参见公式5.2；其他36个最差的引物集将会被淘汰，双亲将会从这54个保留的引物集中产生。
Nkeep[0,1], POPkeep NkeppPOPsize (5.1) Nkeep0.6, POP POPsize90,keep 54 (5.2)
其次、需要决定交叉策略。交叉策略的选择没有特别的约束，因此可以根据问题自由选择[3]。笔者根据以下这个原则：交叉的目的是将好的性状遗传到下一代，选用了均匀交叉法，以下举例说明均匀交叉法。首先回顾上文中：n重PCR需要n对引物构成引物集，每对引物用4个整数来表示，因此总共需要4n个整数来表示一个引物集，参见图 5.1。均匀交叉法即随机产生4n个等于0或1的随机数；若某一位对应了1则发生交叉，否则不交叉；为简化起见，此处不失一般性设n=2，设双亲分别为F和M，设随机数为mask，设交叉产生的子代为CH1与CH2参见图5.2。
18
maskFM0504012522015414202022031230012327154055302119CH1CH250402225154142202231230027235535402119
图 5.2 均匀交叉
5.6 变异策略及变异率的选择
交叉完成后要需要进行变异，完成变异同样要解决两个问题：一、决定变异率；二、选择变异策略。首先、变异率过小会导致遗传算法退化为本地随机搜索算法，变异率过大会使遗传算法退化为随机穷举算法[19]。据文献记载，一般既保证效率又保证足够多样性的变异率落在区间[0.005, 0.01]内，对于连续遗传算法也有取到0.1的变异率[3]。本次研究中根据实验数据总结发现在一定范围内：交叉率越大，收敛越慢，但多样性越大，得到的最终引物集的质量越好；笔者认为，为了保证实际的生物实验的成功，在引物设计中可以牺牲一定程度的计算速度来取得更好的最优引物集。根据对实验结果的统计，GAPrimer最终使用的变异率为0.06。这表示最终在整个人口中将有8.64*n个整数位要变异，参见公式5.3，公式5.4。
BitNum4n(POPsizePOPkeep)MutRate (5.3) MuteRate0.06, POP, POP, BitNum8.64n (5.4) size90keep54其次、需要决定变异策略。变异策略的选择比较灵活，本文中选用的方法类似于交叉策略。首先产生8.64*n随机的行号与列好，代表要变异的整数位，随后对选中的那一位整数进行变异。此外需要注意两个问题：一、变异时可能是原来的数值超出合理的范围，因此变异后需要检查；二、变异的目的是防止遗传算法收敛到本地最优值，同时为下一代引进新性状。不失一般性假设上述CH1中有两个位整数位被选中发生变异，其变异请参见图5.3。
最后，在交叉和变异都完成后，新的子代需要代替上一代，并重复引物集评估步骤，
19
在评估结束后按fitness由小到大进行排序。后续步骤为判断收敛，将在下一节中讨论。
maskCH1CH1'0505012220015415402020131231802727055355302121
图 5.3 变异策略
5.7 收敛条件
判断收敛条件有较多的方式，例如从多样性判断，当整个人口的综合分数之和的平均值和最优引物集的综合分数小到一定程度时即可收敛；又例如从最大的当前的代数上判断，达到一定的代数后由于进化很慢，于是可以收敛[3]。 GAPrimer中使用的变异率较大，不适合使用多样性来收敛；在参考文献后，笔者采用了两个收敛条件：一、最大代数；二、当前最优引物集持续的代数，这个条件指当n代内最优引物集未被子代中更优秀的引物集所代替，则结束程序。
5.8 本章小结
综上所述，本章中介绍了如何将遗传算法和多重PCR引物设计问题结合的方法。目的是为了提供一个将载体算法和多重PCR引物设计问题结合的一般性思路。GAPrimer所采用的方法只是许多条途径中的一种，更好的途径肯定是存在的，但需要进一步的尝试：引入新方法，尝试各种方法的新途径，调试各途径的新参数。目的是两个：一、是程序搜索全局最优解的能力加强；二、加快程序的运行速度和减少程序运行所需的空间要求，从而使程序可以被推广到更大的应用背景下。至此、所有问题已讨论结束；在第六章中将对GAPrimer进行简单介绍，作为对上文的一个补充；在第七章中将分析一个三重PCR引物设计的结果；最后在第八章中进行总结并提出一些进一步的改进建议。
20
第六章 GAPrimer 简介
6.1 软件功能与特点概述
GAPrimer是适用于中、小规模多重PCR引物设计、物评集估的应用软件。其含有23个生物学参数用于约束14个独立的生物学约束条件，并通过14个权值来平衡这14个生物学约束条件。上述23个参数和14个权值均对用户开发，操作系统为DOS。GAPrimer具有三个主要功能：一、多重PCR引物设计，目前版本最高可处理20重PCR的引物设计问题,此外也可以进行单重PCR引物设计，设计效果将在第七章中进行讨论；二、引物集评估，引物集的评估建立在本文所构建的数学模型上的，目前版本最高可评估含40条引物的集合，此外也可以评估单条引物；三、格式化，从网上下载的序列或者由其他软件产生的模板序列往往格式很多，甚至含有一些非碱基的字符，GAPrimer对输入文件做严格的检查后对序列进行格式化，效果请参见附录1。
6.2 软件操作结构图
在本节中给出了GAPrimer的操作流程图，由于GAPrimer的开发环境为英文环境，为了防止翻译过程中发生误解，此处的操作流程图仍采用英文形式，参见图 6.1。
21
GAPrimerPrimer Design for MP-PCRPrimer checkGeneral SettingAdvanced SettingFormatInput filename of output fileInput primer number1. Primer Length Upper BoundSet penalty weights Input filename of input fileInput target numberInput filename of input file2. Primer Length Lower BoundSet biological parameters Input filename of output fileInput filename of input fileInput filename of output file3.Primer Length OptimalUpdating automaticallyStore result automaticallyDesigning primersChecking Primers4. Primer Tm Upper Bound Store the result automatically Store the result automatically 5. Primer Tm Lower Bound 6. Primer Tm Optimal 7. GC Content Upper Bound 8. GC Content Lower Bound图 6.1 GAPrimer操作流程图
6.3 软件默认参表
在本节中给出了GAPrimer的23个参数和14个权值的统计表，一方面作为软件间接的一部分，另一方面作为对三、四两章的总结和补充。由于GAPrimer的开发环境为英文环境，为了防止翻译过程中发生误解，此处的参数统计表仍采用英文形式，参见表 6.1。关于各参数和权值的解释请参见三、四两章。
22
表 6.1 GAPrimer参数统计表
Biological Parameters Name Primer Length Upper Bound Primer Length Lower Bound Primer Length Optimal
Primer Delta Length Upper Bound Primer Tm Upper Bound Primer Tm Lower Bound Primer Tm Optimal Max Primer Delta Tm GC Content Upper Bound GC Content Lower Bound GC Content Optimal
Product Delta Length Upper Bound Product Delta Length Lower Bound Max Product-Target Delta Length Max Complement
Max 3' End Complement Max Hairpin Complement Least Required GC Clamp
Max Mispriming/Max Specificity Max Allowed Poly X
Max End Stability (kcal/mol) Monovalent Concentration (mM) Annealing Oligo Concentration (nM) Penalty Weights Name
Weight for Primer Length
Weight For Primer Delta Length
Weight for Tm
Weight for Delta Tm
Weight for GC Content
Weight for Product Delta Length Weight for Product Length Weight for Complement Weight for End Complement Weight for Hairpin Structure Weight for GC Clamp Weight for Specificity Weight for Poly X
Weight for End Stability
Total Value 27 18 20 3 63 57 60 2 60 40 0(N/A) 100 50 150 7 3 3 0 9 5 -6.9 50 50 Value 10.0 10.0 10.0 10.0 10.0 2.5 2.5 10.0 5.0 5.0 5.0 10.0 5.0 5.0 100.0 6.4 本章小结
本章中简要介绍了GAPrimer软件，作为一种对上文的总结与补充，关于软件使用的详细介绍请参见笔者编写的用户说明文档。在第七章中将对软件的运行结果进行讨论。
23
第七章 实验结果及数据分析
7.1 实验结果：三重PCR引物设计
由于多重PCR引物设计考虑因素较多，报告较长；为避免附录过长，此处不失一般性选取3重PCR引物设计为例对结果进行讨论。三段模板序列均选自人类耳聋基因（编号NT_024524，来源于GenBank数据库），模板序列均为随机选择；三段目标序列也为任意选择，参见附录1。
第一次运行使用表6.1中的默认设置，结果参见附录2；第二次运行根据第一次的结果调整了5个参数的值，结果参见附录3。上述数据将在下一节中进行分析。
7.2 数据分析
使用默认参数设计出的引物集综合分数为44.8656，由附录2可见该引物集的各项参数都是较好的，但存在三个问题：一、产物长度较长，因此成本较高：三段产物总长度为1600，引物集产物间长度差和的平均值为198。二、部分引物寡核苷酸的长度太长：引物对3的前向引物的POLY X值为7。三、部分引物3’段互补值过大：引物对1的逆向引物的3’端自互补值为4，引物对2的逆向引物的3’端自互补值为4。除了上述三个问题，该引物集的其它项评分都较好地落在用户设定的范围内。
为了解决上述问题，第二次运行调整了参数进行重新设计。从附录2结果可以观察到有两项数据非常接近理想值：一、特异性，其默认最大值为9，而六条引物中特异性的最大值仅为1；二、引物间互补、其默认最大值为7，引物集的平均互补分数仅为1.6。因此笔者认为可以牺牲此两项的一些质量来解决上述问题。此外引物集的综合评分较低，可以考虑牺牲引物集一部分质量来降低产物长度，从而降低实验成本。
据此在第二次运行中调整了如下五个参数：一、将最大产物与目标序列长度差(Max Product-Target Delta Length)由默认值150调整到100，以此来缩短产物的长度；二、将约束特异性的权值(Weight for Specificity)由默认值10减少到8，同时将约束最大寡核苷酸长度的权值(Weight for Poly X)由默认值5增加到7，以此来加强对寡核苷酸长度的约束；
24
三、将约束互补的权值(Weight for Complement)由默认值10下降到7.5，同时将约束最大3’互补的权值(Weight for End Complement)由默认值5增加到7.5，以此来加强对3’端互补的约束。第二次运行结果请参见附录3。
由附录3可见原有的问题已解决，引物集中所有参数已较好地落到默认的范围内。此外虽然该引物集综合分数上升为49.0983，但其综合质量平衡得较好，此外产物总长度也下降了266。
综上所述，由结果可见GAPrimer在理论上已能够成功地设计可以在实际中使用的多重PCR引物。本文提出的数学模型也起到实际作用，用户可以通过生物学参数和权值的设定来调整产物的性质与调整整个问题的平衡点。但上述默认参数仍有待优化。
7.3 本章小结
本章中列举了两次3重PCR引物设计的结果，分别使用默认值和用户设定的值；并通过两次结果证明了GAPrimer的使用价值与本文中建立的数学模型的效果。但也可以观察到，GAPrimer中的各项参数仍有待调整，此外，也许数学模型也需要进一步修正从而来提高GAPrimer的使用价值。
25
第八章 总结与展望
由结果可见，GAPrimer的开发是有实用价值的，同时本文也通过介绍GAPrimer的建立过程归纳出开发多重PCR引物设计软件的一般性思路。以下为可改进之处：
首先、根据对所掌握的文献总结，本文中所提及的生物学约束条件已相对完整，但也可能存在遗漏的方面。此外，从参数种类而言，可替代某些参数来提高引物集的质量，例如：引进熵值来估算热力学参数；从对参数计算方式而言，可以应用更高效的算法来提高程序效率，例如：利用Finite state machine模型来计算引物退火温度。其次、从程序的效率和空间而言，本软件强调了静态空间分配，但也可以更多地应用动态内存分配来提高空间利用率，但此举也会导致时间效率的下降。对于这一点，程序仍需要调整平衡点，从而做到既能节省一定空间来处理更多的引物，又能做到节省时间。再次、遗传算法的参数还可以调整，遗传算法的策略也应该存在更好的选择。生物参数与权值的默认值也有待进一步调整，从而提高程序的效率。此外用户的设置应该可以保存，从而避免重复设定。最后、虽然程序中已进行了大量的输入错误检测，但由于时间的限制，程序的健壮性仍有待加强。
26
参 考 文 献
[1] David Clark. Molecular Biology, Understanding the Genetic Revolution[M]. U.S.A: ELSEVIER Inc., 2005. 52~73, 634~661.
[2] John SantaLucia, Jr. Physical Principles and Visual-OMP Software for Optimal PCR Design[A]. In: Anton Yuryev. Ed. PCR Primer Design (Methods in Molecular Biology)[M]. USA: Humana Press, 2007. 3~33
[3] Randy L. Haupt, Sue Ellen Haupt. Practical Genetic Algorithm[M]. 2nd, Hoboken, New Jersey. John Wiley & Sons, Inc., 2004. 1~65, 95~148.
[4] Lauris Kaplinski, Reidar Andreson, Tarmo Puurand. MultiPLX: automatic grouping and evaluation of PCR primers[J]. Bioinformatics, 2005, 21(8), 701–1702
[5] Lauris Kaplinski, Maido Remm. MultiPLX: Automatic Grouping and Evaluation of PCR Primers [A]. In: Anton Yuryev. Ed. PCR Primer Design (Methods in Molecular Biology)[M]. USA: Humana Press, 2007. 287~303
[6] Tomoyuki Yamada1, Haruhiko Soma, Shinichi Morishita1. PrimerStation: a highly specific multiplex genomic PCR primer design server for the human genome[J]. Nucleic Acids Research, 2006, 34(Web Server issue): W665-W669
[7] His-Yuan Huang. Primer Design for Multiplex PCR Using a Genetic Algorithm[D]. Taiwan: National Central University, 2004
[8] Hong-Long Liang. Multiplex PCR Primer Design Using Genetic Algorithm[D]. Taiwan: National Sun Yat-sen University, 2004
[9] Liang, H.-L., Lee, C. and Wu, J.-S. Multiplex PCR primer design for gene family using genetic algorithm[A]. In: GECCO, Proceedings of the 2005 conference on Genetic and evolutionary computation[C], 2005: 67~74 [10] Richard Souvenir, Jeremy Buhler, Gary Stormo. An Iterative Method for Selecting Degenerate Multiplex
PCR Primers[A]. In: Anton Yuryev. Ed. PCR Primer Design (Methods in Molecular Biology)[M]. USA: Humana Press, 2007. 245~267
[11] F. John Burpo A critical review of PCR primer design algorithm and cross-hybridization case study[Z]. USA:
Stanford University, 2001
[12] Steven Rozen, Helen Skaletsk. Primer3 Input Help (release 0.4.0)[Z]. USA: Whitehead Institute for
Biomedical Research, MIT, 2007
[13] John SantaLucia Jr. A unified view of polymer, dumbbell, and oligonucleotide DNA
nearest-neighbor thermodynamics[J]. PNAS, 1998, 95(4), 1460~1465
[14] Markus Leber1, Lars Kaderali2, A fractional programming approach to efficient DNA melting temperature
calculation[J]. Bioinformatics, 2005, 21(10): 2375~2382
[15] Peter M. Vallone, John M. Butler. AutoDimer: a screening tool for primer-dimer and hairpin structures[J].
BioTechniques, 2004, 37(2), 226-231
[16] Kenneth J. Breslauer, Ronald Frank, Helmut Blocker, Predicting DNA Duplex Stability from the Base
Sequence [J]. PNAS, 1986, 83(11), 1460~1465 [17] Thomas Kämpke. The Reference Point Method in Primer Design[A]. In: Anton Yuryev. Ed. PCR Primer
Design (Methods in Molecular Biology)[M]. USA: Humana Press, 2007. 75~91 [18] Thomas Kämpke1, Markus Kieninger2 and Michael Mecklenburg3. Efficient primer design algorithms[J].
27
Bioinformatics, 2001, 17(3): 214~225.
[19] Edward Keedwell, Ajit Narayanan. Intelligent Bioinformatics[M]. England: John Wiley & Sons Ltd, 2005.
195~217
[20] Sanghamitra Bandyopadhyay, Sankar K. Pal. Classification and Learning Using Genetic Algorithms[M].
Berlin Heidelberg, New York, Springer Press, 2007: 19~51, 181~212
[21] Marek Obitko. Introduction to Genetic Algorithms[Z]. http://www.obitko.com/tutorials/genetic-algorithms/,
1998
[22] Matthew Wall. GAlib: A C++ Library of Genetic Algorithm Components[Z]. USA: MIT, 1996
[23] Amit Banerjee. Fitness Scaling[Z]. Reno NV, USA: University of Nevada, http://www.cse.unr.edu/ .
~banerjee/scaling.htm, 2007
[24] Anton Yuryev. PCR Primer Design Using Statistical Modeling[A]. In: Anton Yuryev. Ed. PCR Primer Design
(Methods in Molecular Biology)[M]. USA: Humana Press, 2007. 93~103
28
附 录
1．输入文件(靶序列)
文件中的模板序列均为随机选择，为人类耳聋基因的一部分（编号NT_024524，来源于GenBank数据库）。靶序列全部为任意选择，在模板序列中用“{ ”和“} ”标出。
文件名：1.txt
1 TACATGACTC CAAATAAGAC TGTTTATAAA ATGGGTTCCA TCCAGTACAA 51 GTTTTTAAAC TACTGTTGTA ACACATAAAT TTGTGCTGCC TCCAACAGCA 101 ATGATTCAAC TGTTAGTCTG ATTACATCAT TCACATTATC ACCAAGTATA 151 TCCTCTAAAG TGTCTAATTA TCACTTTTAT AAAGCACATT CACAAAGTTT 201 TGCATTCATC ACCACTACCC AGTTCCTGTT TGTCTGATTT TTATTATTTA 251 AAAAAATGGA AAAACAAAAG TGCATTTTTC ATTCAATAAA TGTTCCATCC 301 TTATTTAGTT TTGTTGCCGA AAGTGAAGTC CATGACTTTA GAATGATAGC 351 AATTTATCAA CCAAAGAATC CGTCTTCACA CCGTTTCAAT AACTGCAGCA 401 ATTTCCTTGA ACTGTCTGTA GAAATTCTGG AGAGAAAGGG GGAAAATAAT 451 ATTAATTTTG CTTTTAGAAG ATATTTAAGT AGTTATTTTA ATTATATCTG 501 ACTACCGGAG ACTATATAAC ATATTAAGTT TGCATTTTAG TGTTACATTC 551 {TCAATTACTG AAGGTTGCTG TAAGAAATAG GTGCAATTTG GTACTGCAAG 601 CAAAAATACT ACTGTGGGGT TGGATAATTA TCTTATGACT AAACTTTTCA 651 AAAAGCACAT GAGAAAGTCC TTTTAAGATC ACACCAGATT TATTAAATAC 701 TCAGCACTGT CCTAGACACT GAAAATAAAA GCAAAAATAA CAAGTTGGTT 751 CCAGGCCTCA} AAACACTTTC AATCTAGTAA AGGACCGCAT TTCAGTGTGG 801 TAAGGGCTAT CTCATTTAAG ATTATGGGTT CAATTACTAG AAGAGAGATC 851 CAACATTAAC TATGGTTTAT ATGGTAGAAG TTTATTTCTC TGTCATTTAA 901 AAATTAAGCT GGTATAACGG TTCTCCTATA GAAGTCATCT TCTTTTAAAT 951 CTCAGGTAAG AAAGGAATCA AGCAAATTGT TCTTCTGTCT TCTCCTGTAC 1001 CTACCCCAGG AAGCTAGGAG ACAAATTTGA AACTTAACCT TGGCAATCAG
文件名：2.txt
1 GTGGTTAGTT TTAAGCCATG TAAAAACTCT CTTTAAAAGA GTTGCCTCTA 51 ATGAAAATGT TTTTGTGTAT ATTTATATTT AATATGATTA TAATGTATGT 101 CTATATGTAT ATACTATGTA TGTGTATACA TACACACACA ATGGAATATC 151 ACACAGCCAT AAAAAAGAAG GAAATCCTGC CATTTGCAAC AACATGGATG 201 {AACCTGGAGG ACATTGTGCA AAGTGAAATA AGCCAGACAC AGAAAGGCTA 251 ATACTGCGTG ATCTCACTTA TATGTGGAAT CTAAAAAAGT CAAACTCACA 301 GAAGCAGAAA GGAGACTGGA GGTTGCCAGG AGCTGAGGCT GGGGGTCAAT 351 GGGGAAATGT TAGTAAAAAG GTACAAACTT TTGGTTACAA} AATGAGTAAG 401 TCTGAGATCT AATGTACAAT ATGGTGACTA CAGTAATATT GTTATTGTTT
29
451 ACTTGAAATT TGCTAAAAAA CATTTTACAT GCCCTCAGCA CACACACACA 501 CACACACACA CACACACACA TACATGCACA CACTCTCTCC AAAAAAAAAA 551 AAGGTAACTG TGTGGGGGTG GATGTGTTAA TTAGAGTGAC TGTGGTAATC 601 TTTACACAAT GTATATCTTT TATCATATCA TCACATTGTG AAACCTTCAA 651 AATACACAAT TTTGTCAACT GTACCTCAAT AAAGCTGGGG AAAAAAAGTT 701 AATCCAATTG TGATTTTTTT TTTCCTATAG GAAAAAATTT CTAGAGGTGG 751 AATCAGGACA GCACAAATGC TGCACAGAAT AATAACAATT AGGCCAGCAC 801 TGTGAATTAC AAAAAAGACC AAAACGTGTA TTCTCTTTCG AAATTGACTG 851 AGTCCTCATA TTTAGTTGAA TGTTATTCCC ATATCACAAT ATACATTTAT 901 TTCCTTTTCA CTAAGTCTCA GTTCCAAGAC ACTAATCAAT ATTAATAATG 951 TTAAATTTGT GAACATTATT TTTGTTTCAA AGCACGGATA TCTATTTTAA 1001 ATAAAGAAAT CAGGCTGAGC ATGGTGGCTC ACGCCTGTAA TTCCAGCACT 1051 TTGGGAGGCT AAAGTGGACG GATCAACTGA GGTCAGGAGT TTCAGAAGTG
文件名：3.txt
1 TAATCCTGGC ACTTTGGGAG GCCAAGGTGG GTGGATCACA AGGTCAGGAG 51 ATCGAGACCA TCCTGGCTAA CATGGTGAAA CCCCATCTCT ACTAAAAATA 101 CAAATAAATT AGCCAGGCAT GGTGGTGGGC GCCTGTAGTC CCAGCTACTC 151 GGGAGGCTGA GGCAGGAGAA TGGCGTGAAC CCAGGAGGCA GAGCTTGCAG 201 TGAGCCAAGA TCGTGCCACT GCACTCCAGC CTGGGCAACA GAGCGAGACT 251 CCGTCTCAAA AAAAAAAAAA AAAAAAAAAA AAAAGAAAAC CTGATTTATT 301 CCCACCTCCC CCCCACCTTT TATTCCTCCT TGGTTACAGA AAAGAGGTAG 351 AATGA{TAATA TGGTAACATC ACTCTAAACT ACTGAGTTAC TTAAGTCCCT 401 AGCTGATAAA GCCAGCCAAG AGGTACACTT GCTCTGACCT GTCTTTTGTA 451 AACATTATCA GTCAGAAAAT TCAGGGTCAA CACTATTCAA AGATTCATTT 501 AGCTTAACAT TCTTGAATAT TAAGCCCAAA GGAATAAGAA TAAAACATTT 551 AAATGCAAAG TAAATATCCT GCCATTGAA}G ATAAAACTTT CCTAAATATA 601 CTCAGAGAGG AGTACTGTTC AAGCGATCAA ATGGCGCAGT ACACAACTTC 651 AGCACATTAT ATTGAAAATA ATTTATCAAA TTCCCAAAGA AGACAAATTA 701 ATGTCTCTTG CATATACTAC TAGTAAACGT AAAGCATATC AATCTACAAA 751 TAAAAACCAT TAAAGTTTTC CCGTAGAAAG ATTTTATACA TCTTTTTATG
2．三重PCR引物设计结果(使用默认设置)
30
文件名：result_default.txt
******************************************************** The evaluation of the single primer
******************************************************** (Note: All primers are presented from 5' end to 3' end.)
//////////////////////////////////////////////////////// Primer Pair 1
//////////////////////////////////////////////////////// product length: 655 Forward Primer:
Sequence: ACCAAAGAATCCGTCTTCACACCGT Start Position: 360 Length: 25
Tm: 58.6448 GC Content: 48% GC clamp : 2 Poly X: 3 Hairpin: 1 Specificity: 1 Self Complement: 3 3'End Self Complement: 2
3' End stability: -4.83 kcal/mol
Reverse Primer:
Sequence: GCTTCCTGGGGTAGGTACAGGAGAAG Start Position: 1014 Length: 26 Tm: 59.567 GC Content: 57.6923% GC clamp : 1 Poly X: 4 Hairpin: 1 Specificity: 0 Self Complement: 2 3'End Self Complement: 4
3' End stability: -2.85 kcal/mol
//////////////////////////////////////////////////////// Primer Pair 2
//////////////////////////////////////////////////////// product length: 588 Forward Primer:
Sequence: AACAACATGGATGAACCTGGAGGACAT
31
Start Position: 188 Length: 27
Tm: 58.2919 GC Content: 44.4444% GC clamp : 1 Poly X: 2 Hairpin: 2 Specificity: 1 Self Complement: 2 3'End Self Complement: 3
3' End stability: -3.06 kcal/mol
Reverse Primer:
Sequence: GTGCAGCATTTGTGCTGTCCTGATT Start Position: 775 Length: 25
Tm: 58.7741 GC Content: 48% GC clamp : 0 Poly X: 3 Hairpin: 4 Specificity: 1 Self Complement: 4 3'End Self Complement: 1
3' End stability: -2.57 kcal/mol
//////////////////////////////////////////////////////// Primer Pair 3
//////////////////////////////////////////////////////// product length: 357 Forward Primer:
Sequence: CCTGATTTATTCCCACCTCCCCCCC Start Position: 290 Length: 25
Tm: 60.0571 GC Content: 60% GC clamp : 3 Poly X: 7 Hairpin: 0 Specificity: 1 Self Complement: 0 3'End Self Complement: 1
3' End stability: -5.4 kcal/mol
32
Reverse Primer:
Sequence: TTGTGTACTGCGCCATTTGATCGCT Start Position: 646 Length: 25
Tm: 59.7836 GC Content: 48% GC clamp : 2 Poly X: 3 Hairpin: 1 Specificity: 1 Self Complement: 2 3'End Self Complement: 1
3' End stability: -4.93 kcal/mol
******************************************************** The evaluation of the whole primer set:
******************************************************** Total Primer Number: 6
Average Delta Tm: 0.869014 Average Primer Delta Length: 0.866667 Average Max Complement: 1.61905 Average Max End Complement: 2.2381 Average Procuct Delta Length: 198.667 Balanced Score: 44.8656
3．三重PCR引物设计结果(使用用户设置)
文件名：result_revised.txt
******************************************************** The evaluation of the single primer
******************************************************** (Note: All primers are presented from 5' end to 3' end.)
33
//////////////////////////////////////////////////////// Primer Pair 1
//////////////////////////////////////////////////////// product length: 596 Forward Primer:
Sequence: CACCACTACCCAGTTCCTGTTTGTCT Start Position: 210 Length: 26
Tm: 58.4132 GC Content: 50% GC clamp : 1 Poly X: 3 Hairpin: 0 Specificity: 2 Self Complement: 0 3'End Self Complement: 2
3' End stability: -3.41 kcal/mol
Reverse Primer:
Sequence: CCTTACCACACTGAAATGCGGTCCTT Start Position: 805 Length: 26
Tm: 59.2468 GC Content: 50% GC clamp : 1 Poly X: 3 Hairpin: 2 Specificity: 2 Self Complement: 0 3'End Self Complement: 2
3' End stability: -3.36 kcal/mol
//////////////////////////////////////////////////////// Primer Pair 2
//////////////////////////////////////////////////////// product length: 401 Forward Primer:
Sequence: GCCATTTGCAACAACATGGATGAACC Start Position: 179 Length: 26
Tm: 58.1854 GC Content: 46.1538% GC clamp : 2
34
Poly X: 3 Hairpin: 2 Specificity: 2 Self Complement: 3 3'End Self Complement: 2
3' End stability: -3.62 kcal/mol
Reverse Primer:
Sequence: TAACACATCCACCCCCACACAGTTAC Start Position: 579 Length: 26
Tm: 58.4662 GC Content: 50% GC clamp : 1 Poly X: 5 Hairpin: 0 Specificity: 2 Self Complement: 3 3'End Self Complement: 2
3' End stability: -2.5 kcal/mol
//////////////////////////////////////////////////////// Primer Pair 3
//////////////////////////////////////////////////////// product length: 337 Forward Primer:
Sequence: CCCCCACCTTTTATTCCTCCTTGGTT Start Position: 310 Length: 26
Tm: 58.4333 GC Content: 50% GC clamp : 1 Poly X: 5 Hairpin: 0 Specificity: 4 Self Complement: 0 3'End Self Complement: 1
3' End stability: -3.67 kcal/mol
Reverse Primer:
Sequence: TTGTGTACTGCGCCATTTGATCGCT Start Position: 646 Length: 25
Tm: 59.7836
35
GC Content: 48% GC clamp : 2 Poly X: 3 Hairpin: 1 Specificity: 1 Self Complement: 2 3'End Self Complement: 1
3' End stability: -4.93 kcal/mol
******************************************************** The evaluation of the whole primer set:
******************************************************** Total Primer Number: 6
Average Delta Tm: 0.701638 Average Primer Delta Length: 0.333333 Average Max Complement: 1.28571 Average Max End Complement: 1.80952 Average Procuct Delta Length: 172.667 Balanced Score: 49.0983
36
因篇幅问题不能全部显示，请点此查看更多更全内容