（计算机软件与理论专业论文）对pcr引物设计问题的研究.pdf

山东大学硕士学位论文 摘要 核酸体外扩增思想是由k h o r a n a 及其同事于1 9 7 1 年提出，并由美国 p e c e t u s 公司的人类遗传研究室m u l l i s 等人于1 9 8 5 年发明了具有划时代意义 的聚合酶链反应( p o l y m e r a s ec h a i nr e a c t i o n ，p c r ) 后才得以实现。p c r 技术具有 特异、敏感、产率高、快速、简便、重复性好、易自动化等突出优点。由于p c r 方法的方便、快速、有效，很快便得到了广泛的应用，并大大推动了分子生物 学及其相关学科的研究和发展。p c r 技术是生物医学领域中的一项革命性创举 和里程碑。引物是p c r 特异性反应的关键。随着p c r 技术的发展，引物设计 成为一个重要的问题。本文对以往p c r 设计中的问题进行了研究，在介绍莳人 算法的基础上提出了新的算法。 本文首先对p c r 引物设计相关的背景和概念进行了简要介绍，分析了p c r 技术的原理和特点，说明了对引物设计问题进行研究的必要性。然后对p c r 引 物设计问题中的引物选择、简并引物设计和随机引物设计进行了研究 在p c r 试验中的引物选择问题中，证明了对扩展一d n a 序列集合所需的 引物个数进行最小化问题是n p c o m p l e t e ，设计并实现了分支限界算法和启发式 贪婪近似算法。另外还对需要同时最优化引物个数及它们的权值总和的w o p c 问题进行了探讨。 在简并的引物设计问题中，证明了简并引物设计问题和几个简化的简并引 物设计问题都是n p c o r n p l e t e 的，但在一些受限的实例中足多项式可解的。然 后对一种简化的简并引物设计问题提出了多项式近似算法。 在随机引物设计问题中，根掘随机引物设计的一般原则，提出了一种基于 h a s h 思想的统计算法，通过建立合理的数掘结构和子串h a s h 函数，快速计算 出基因组中引物序列的出现频率，从而设计合适的随机引物。为基因组学中的 引物设计提供了有力工具。 关键词： 聚合酶链式反应( p c r ) ，引物设计，简并，分支限界，启发式贪婪算法， h a s h 山东大学硕士学位论文 a b s t r a c t t h ei d e ao ft h eo u t e ra m p l i f i c a t i o no fn u c l e o t i d ew a sf i r s tp r o p o s e db yk h o r a n a a n dh i sc o l l e a g u e si n1 9 7 1 h o w e v e r i tw a st u r n e di n t or e a l i t ya f t e rm u l l i s ，t h e l e a d e ro fh e r e d i t yo fh u m a n i t yl i b r a r yw h i c hb e l o n g e dt ot h ep e c e t u sc o r p o r a t i o n d e v i s e dt h ee p o c h - m a k i n gp o l y m e r a s ec h a i nr e a c t i o n ( p c r ) i n19 8 5 t h e r ea r e m a n yd i s t i n c tm e r i t si nt h ep c rt e c h n o l o g y , s u c ha ss p e c i a l i z a t i o n ，s e n s i t i v i t y , h i g h p r o d u c t i v i t y , c e l e r i t y , c o n v e n i e n c e g o o dr e p r o d u c t i v i t y , a u t o m a t i z a t i o na n ds oo n a sar e s u l t ，p c rh a sb e e nw i d e l ya p p l i e di nm a n yf i e l d s ，w h i c hi nt u r ns t i m u l a t e s r e s e a r c ho fm o l e c u l a rb i o l o g ya n dc o r r e l a t i v ed i s c i p l i n e s f r o ma b o v em e n t i o n e d ，i t w i l ln o tb ep r e s u m p t u o u st os a yt h a tt h et e c h n o l o g yo fp c ri sar e v o l u t i o n a r y i n n o v a t i o na n dl a n d m a r ki nt h ef i e l do fb i o l o g i c a lm e d i c i n e p r i m e ri st h ek e yo f s p e c i f i cr e a c t i o n so fp c r w i t ht h ed e v e l o p m e n to ft h ep c rt e c h n o l o g y , p r i m e r d e s i g nh a sb e c o m e 托i m p o r t a n ti s s u e i nt h i sd i s s e r t a t i o n s o m ep r o b l e m sa n d a l g o r i t h m so fp c rd e s i g na r ed i s c u s s e di nd e t a i la n ds e v e r a le f f e c t i v ea l g o r i t h m sa r e p u tf o r w a r da n dr e a l i z e d t h eb a c k g r o u n da n ds o m ec o n c e p t i o n si n t h e d e s i g no fp c rp r i m e ra r e i n t r o d u c e db r i e f l ya tf i r s t a l s ot h ep r i n c i p l ea n dc h a r a c t e r i s t i c so fp c r t e c h n o l o g y a r ea n a l y z e da n dt h ei m p o r t a n c eo fr e s e a r c ho f p r i m e rd e s i g f ia r ea d d r e s s e d t h e n t h ep r o b l e m ss u c ha st h es e l e c t i o no fp r i m e r , t h ed e g e n e r a t ep r i m e rd e s i g na n dt h e a r b i t r a r yp r i m e rd e s i g na r ei n v e s t i g a t e d o nt h es e l e c t i o no fp r i m e ri np c r e x p e r i m e n t s w ep r o v et h a tm i n i m i z i n gt h e n u m b e ro fp r i m e r sn e e d e df o ra m p l i f i c a t i o no fac o l l e c t i o no fd n as e q u e n c ei s n p 。c o m p l e t e t h e nw ed e s i g na n di m p l e m e n tab r a n c h a n d - b o u n da l g o r i t h ma n da g r e e d yh e u r i s t i ca p p r o x i m a t i o na l g o r i t h m i na d d i t i o n ，w ed i s c u s st h ew o p c p r o b l e mw h i c ho p t i m i z e sn o to n l yt h en u m b e ro fp r i m e r sb u ta l s ot h es u mo ft h e w e i g h t so f t h e s ep r i m e r s o nt h ed e g e n e r a t ep r i m e rd e s i g n , w ep r o v et h a t t h i s p r o b l e ma n ds e v e r a l s i m p l i f i e do n e sa r ea l ln p c o m p l e t e h o w e v e r , t h e s ep r o b l e m sa r ep o l y n o m i a l s o l v a b l ef o rs o m ei n s t a n c e sw i t hl i m i t a t i o n s t h e nap o l y n o m i a la p p r o x i m a t i o n 山东大学硕士学位论文 a l g o r i t h mf o rs o l v i n go n e o f t h es i m p l i f i e dd e g e n e r a t ep r i m e ra r ed e s i g n o nt h ea r b i t r a r i l yp r i m e rd e s i g n ，a c c o r d i n gt ot h eg e n e r a ld e s i g np r i n c i p l e w e p u tf o r w a r dak i n do fs t a t i s t i c a la l g o r i t h mb a s e d o nt h et h o u g h to fh a s h b yv i r t u eo f e s t a b l i s h i n ga p p r o p r i a t e d a t as t r u c t u r e sa n dh a s hf u n c t i o n s ，w ec a nc o m p u t et h e f r e q u e n c yo fo c c o l t e d c e o fp r i m e ri n g e n o m ev e r yq u i c k l y w h i c hp r o v i d e a p o w e r f u la p p a r a t u sf o rt h es e l e c t i o n & p r i m e r i ng e n o m i c s k e y w o r d s ： p c r , p r i m e rd e s i g n , e g e n e r a t e ，b r a n c h a n d b o u n d ，g r e e d yh e u r i s t i ca l g o r i t h m ， h a s h 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 l 的法律责任由本人承担。 论文作者签名：j 蜉日期：皇鲮咝 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 f 保密论文在解密后应遵守此规定) 论文作者签名： 峥师签名： 山东大学硕士学位论文 1 1 研究背景 第一章序论 分子生物学成为- - f j 独立的学科是本世纪生物学领域的一项重大进展。四 十年代以来，人们从分子水平研究了重要的生物物质如蛋白质和核酸的结构， 如果说这些构成了当今最活跃的学科分子生物的基础，那么，近几年来基 因工程研究工作中的新成就，便是分子生物学迅速发展的一个标志。生物新技 术的不断发现、发明和革新( 如s o u t h e r n 印迹法分子克隆等) ，为解决基础和 应用生物学问题阐明了许多新的构思方式。聚合酶链式反应( p o l y m e r a s ec h a i n r e a c t i o n 简称p c r ) 便是一个明显的例子所谓聚合酶链式反应，又称体外辑促 基因扩增，是利用d n a 聚合酶依赖于d n a 模板的特性，模仿体内d n a 的复 制过程，在附加的一对引物之白j 诱导的聚合酶反应。p c r 技术使过去只能在生 物体内细胞分裂增殖时才出现的基因复制能在体外试管内得以实现。特别是与 自动测序技术结合后，成为一种最快、最有效的测定核营酸序列的方法，并在 基础和临床上得到广泛的应用。 1 2p c r 技术的发明 p c r 技术是在核酸研究的基础上发展起来的，早在1 8 6 9 年瑞士的年轻医 生m i e s c h e r 就丌始对核酸进行研究，至今已有一百多年的历史。自1 9 3 0 年正 式提出d n a 和r n a 两种核酸的概念后，人们对核酸的化学组成、结构及其功 能进行了更为深入的研究，特别是1 9 5 3 年w a t s o n 和c r i s k 根据x 射线 ； 了射图 形及各种化学分析数掘提出的d n a 双螺旋结构及其半保留复制模型，是牛物 科学史上的一个飞跃，这使得对基因在体外克隆、表达、调控等方面取得了长 足的进展，并由此拉丌基因工程的序幕。七十年代以柬，人们采用两种思路尝 试建立基因的无性繁殖体系，一是重组d n a 技术，从基因文库中分离出单个 的目标基因，将其拼接到载体中构建成重组d n a ，因载体是具有独立复制能力 的质粒或噬菌体，当重组d n a 引入细菌细胞后，经多次复制便可得到足够数 量的d n a 克隆片断。d n a 的连接酶和限制性内切酶的发现，为重组d n a 技 山东大学硕士学位论文 e m m 1 1 曼! 曼曼曼皇曼皇舅舅曼i 术和基因克隆铺平了道路，现已成为最为常用的基因克隆技术另一种思路是 由k h o r a n a 等在1 9 7 1 年提出的，其观点是：在体外d n a 变性，与适当引物杂 交，再用d n a 聚合酶延伸引物并不断重复该过程便可克隆t d n a 基因。这种核 酸体外扩增的设想由于当时不能合成寡核苷酸的引物和很难进行d n a 测序而 渐渐为人所疏忽。利用k o m b e r g 在1 9 5 8 年发现并分离的d n a 聚合酶( 这是第 一个可在试管中合成的d n a 酶) ，美国c e t u s 公司人类遗传研究室的年轻科学 家k a r y b m u l l i s 在1 9 8 5 年发明了具有划时代意义的聚合酶链式反应( p c r ) ，使 k h o r a n a 的这一设想终于付诸实现。 p c r 的原理类似于d n a 的体内复制，只是在试管中给d n a 的体外合成提 供一种合适的条件模板d n a ，寡核苷酸引物、d n a 聚合酶、m 9 2 + 、合适 的缓冲体系和d n a 变性、复性及延伸的温度与时间等。1 9 8 6 年p e c e t u s 公司 发现并提纯了耐热d n a 聚合酶，1 9 8 7 年推出了p c r 自动化热循环仪，1 9 8 8 年，首先获得了基因工程方法生产的耐热d n a 聚合物，p c r 被评为荚 s c i e n c e 所设的1 9 8 9 年世界重大科技成就。 p c r 技术能快速特异地扩增所希望的目标基因或d n a 片断，并能很容易 地使得微微克( p 曲水平的起始物达到微克( u 曲水平的量i 旧。现已发展成为生命科 学实验室获取某一目标d n a 片断的常规技术，并逐渐被应用于各个领域p i 。它 也必将大大推动分子生物学机器相关科学的研究进展，由于m u l l i s 的杰出贡献 这位年轻的科学家获得了1 9 9 3 年度诺贝尔化学奖。 1 3p c r 技术的原理及优化 1 3 1p c r 的工作原理 p c r 是一种选择性体外扩增d n a 或r n a 片断的方法，实际上是通过试管 反应使极少量的基因组d n a 或r n a 样品中的特定基因片断，在短短几个小时 内扩增上百万倍，p c r 的特异性是由两个人工合成的引物序列决定的。所谓引 物就是与待扩增的d n a 片断两翼互补的寡核苷酸，其本质是s s d n a 片断，待 扩增d n a 模板加热变性后，两引物分别与两条d n a 的两翼序列特异复性此 时，两引物的3 相对，5 相背，在合适的条件下，由耐热d n a 聚合酶催化引 山东大学硕士学位论文 物引导的d n a 合成，即引物的延伸，这个过程是由温度控制的，所以p c r 是 一个在引物介导下反复进行热变性一退火一引物延伸三个步骤而扩增d n a 的 循环过程。 1 热变性 模板基因组d n a 在9 5 c 9 7 c 下加热变性，双螺旋结构解链成为单链。 2 退火 将反应混合物降温，使引物与单链d n a 模板( 或m d n a 逆转录而柬的 e d n a ) 上互补的序列复性，即退火，形成模板一引物复合物。复性的温度决定 于引物的溶解温度t m 值，一般为2 5 - 2 7 c ，退火时间为l 2 分钟。 3 引物延伸 p c r 扩增过程中，链的延伸是有方向性的，是以引物为固定起点，使用耐 热d n a 聚合酶，由5 一3 方向合成d n a ，实验证明：迅速加入t a q d n a 聚合 酶2 单位，混匀，置反应混合物于7 0 ，在酶的作用下，以d n i p 为原料，从 引物的3 端刀= 始，沿5 一3 方向，按照模板链上的序列，合成一条d n a 链， 其序列与模板序列互补，延伸时间决定扩增片段的长度，新链合成的速度非常 快，每秒约可延伸4 0 - - 6 0 个碱基。 经过上述高温变性一低温退火一中温延伸这样一个循环，模板d n a 拷贝 数增加一倍，在以后进行的循环过程中，新合成的d n a 链都起着模板作用， 因此，每经过一个循环，d n a 拷贝数便增加一倍。n 次循环后，拷贝数增加2 “ 倍，进行2 5 - 3 0 个循环，拷贝数即可扩增上百力倍( 1 0 6 ) ，扩增的d n a 片段长 度基本上都限定在两引物5 端以内，在凝胶电泳号显示为一条特定长度的d n a 区带。 1 3 2p c r 反应条件的优化选择 在以上原理的基础上，进行p c r 时还需对其它各方面的条件进行优化，这 些因素在p c r 反应中的作用和影响都极为重要。讨论如下： 1 模板核酸 用于p c r 进行核酸体外扩增的模板可以是d n a ，也可以是r n a ，但r n a 的扩增需要首先逆转录为e d n a 后才能进行正常的p c r 循环。扩增时需将标本 山东大学硕士学位论文 部分纯化，使核酸标本中不合d n a 聚合酶抑制剂。 2 引物 p c r 扩增产物的大小是由特异引物限定的，引物是决定p c r 结果的关键 引物合成的质量要高且需纯化，通常必须经聚丙烯酰胺凝胶电泳或反向高厅液 相层析( h p l c ) 纯化，否则引物中有相当数量的“错误序列”会引起非特异性扩 增和信号强度的降低。 引物的设计原则一般是：引物寡核苷酸长度为1 5 一3 0 b p ，一般为2 0 - - 2 7 b p g + c 含量在4 0 - - 6 0 。引物中四种碱基要随机分佑，应避免3 个连续的聚n 票 呤和聚嘧啶的现象，特别是37 端上的g 和c ，往往使这种引物在g + c 富集序列 区错配。引物自身不应存在3 b p 以上的互补碱基序列，否则容易字符折叠成 发夹结构( 或称引物本身复性) ，这种结构会因空间位阻而影响与模板的配对结 合。两对引物之间不应存在4 个以上连续的同源性或互补性碱基，避免引物 之间互相错配称引物二聚体，尤其使引物3 端的互补重叠。引物与非扩增序 列的同源性不要大于7 0 ，或不要出现连续8 个互补碱基同源。 3 耐热d n a 聚合酶 目前，常用t a qd n a 聚合酶，使用量参考标准是：每1 0 0 p 1 反应含l t 5 u t a q 酶，这样速率可达1 0 0 0 - 4 0 0 0 n “m i n ，有时酶的需要量可依据不同的模扳分子或 引物而变化，需在1 0 0 “1 反应体积中加入o 5 5 u 酶的范围内实验酶浓度，若 酶浓度过高，则琼脂糖凝胶电泳中会出现非特异性扩增带，过低时，则靶序列 产量很低。 除了以上因素外，缓冲液的浓度、m 9 2 + 的浓度、三磷酸脱氧核苷酸( d n t p ) 的浓度等其他因素对p c r 反应也有着重要的影响。 1 4p c r 技术的特点 在众多的基因诊断技术中，以核酸探针杂交技术和p c r 技术应用晟广近 年来，p c r 技术更是以其与众不同的特点而受到人们重视其主要特点足； 1 特异性高 由于碱基中g = c 、a = t 严格配对及耐热d n a 聚合酶合成的忠实性，保 山东大学硕士学位论文 证了p c r 的j 下确性，再通过选择特异性和代表性好的靶d n a 检测区( 一般为高 度保守区) 和合理的引物长度( 2 0 个寡核苷酸左右) 及调整退火温度就可提高l i 而 床诊断结果的特异性。 p c r 检测是以探测基因为目标，属“病因诊断”，因而针对性强，在感染 性疾病诊断中，不仅可以检出正在生长的病原体，也可以检出潜伏的病原体， 既能确定既往感染，也能确定现行感染，对那些现在尚不能在体外培养或难于 培养的病原体( 如梅毒螺旋体、结核丰t 菌、乙肝病毒等) ，p c r 检验特b 0 有效， 与生化和免疫学检验相比，p c r 结果与病原体分离培养结果更为一致，直接反 映病原体的存在与否。 2 灵敏度高 在p c r 扩增中，p c r 产物以指数级迅速增加，样品中极其微量的靶序列在 数小时内即可增加上百万倍，很容易将p g ( 皮克= 1 驴微克) 量级的起始铍检测 物扩增到微克( u g ) 水平，灵敏度极高，可达飞克( f g ) 级，理论上可检出一个细菌 或一个真核细胞的单拷贝基因的存在，这便提高了临床诊断的阳性率和准确性 p c r 方法还可对单一双倍体细胞、一根头发，甚至一个精子进行d n a 扩增。 3 操作简便、速度快捷 在p c r 实验中，由于采用耐高温的z a qd n a 聚合酶，使操作大为简化， 加一次酶即可完成全部循环反应过程，特别是随着由电脑调控的d n a 扩增仪 的发展与普及，使手工操作发展成为仪器自动循环，只需一次件把整个反应系 统配黄好，输入正确的程序，便可自动进行变性、复性，延伸三个反应阶段， 产生正确的p c r 产物。 另外由于t a qd n a 聚合酶掺入单核苷酸的速率较好，p c r 每一周期只需数 分钟，加之商品化试剂盒替代了操作者自配的各种试剂，只需将样品作简邴处 理和加样后即可扩增，因而p c r 检验快速省时，一般在2 4 h 左右即可得出结 果，发出检验报告。 4 。对样品要求低 由于p c r 的高灵敏度和特异性，只要标本中含极微量( p g 或龟) 的孳巴d n a 通过简单去蛋白的处理，即可用于p c r 试验并得出j 下确的结果，标本不需要特 殊采集、贮运、处理条件，甚至低温保存多年的陈旧标本，都可用于p c r 扩增， 山东大学硕士学位论文 一些过去脑脊液、骨髓检查的项目，从检查血、唾液或尿标本同样可得到一致 的结果，这不但为采集标本带来方便，也使检测范围扩大和容易丌展。 6 山东大学硕士学位论文 2 1 引言 第二章p c r 实验中的引物选择问题 聚合酶链式反应( p c r ) 又称无细胞分子克隆系统，是一种体外扩增特异 d n a 片断的技术，1 9 8 5 年出美国c e t u s 公司和加利福尼亚大学联合创建，是 9 0 年代分子生物学领域的一项革命性交破，很快在分子克隆、遗传病的基因诊 断、法医学、考古学等方面得到了广泛应用。 p c r 技术实际上就是在模板d n a ( t e m p l e t ed n a ) b i 物( p f i m e r ) ；和4 种脱氧 核苷酸( d a t p , d g t p , d c t p , d t t p ) 存在的条件下依赖于d n a 聚合酶( t a q s e ) l 拘霉促 合成反应，其效率和特异性取决于两个方面：一是引物与模板的特异；二是聚 合酶对引物的有效延伸。引物与模板的特异结合取决于引物的浓度和引物的设 计。引物的设计对于p c r 极为重要，引物设计的不好。就不会得到待扩增片断。 计算机程序被广泛的用于p c r 引物的设计1 4 。一般的，这些程序都侧重 于设计并优化一对引物来对一个复杂基因组中的一单一序列进行扩增。在这罩， 我们对一待扩增序列的集合的一端设计一引物集合，在实际应用中可以重复这 个过程在另一端设计另一个引物集合。 本章证明了对一给定序列集合对覆盖该集合的引物数目进行最小化问题是 n p c o m p l e t e 的，并给出了一分支限界算法；提出了一有效的近似算法，并证明 了该算法的近似性能比为对数级的。对于带权值的引物集合的最小化问题，也 进行了讨论。 2 2 符号和问题的公式化 在对最小化所需引物个数的问题进行公式化之i j 先引入一些必须的符号。 用斜体小写字母( 如“口”) 来表示字符和字符串。用斜体大写字母( 如“a ”) 表示 集合，用手写体大写字母( 如月) 来表示项的集合。 令s = ( s l , s 2 ，, s n ) 为字母表上的字符串的有限集合字符串u 和v 的连 接已为洲或t l - v 。对任意有限字符集合，用来表示由中字符组成的所有 字符串例如，如果= 口，b ) ，则； 占，口，b 口口，a b ，b a b b ) ，为k 皮 山东大学硕士学位论文 为0 的空串。对于两个字符串“，v ，如果是v 中的一连续部分，则称“ 是v 的子串，记为u v ，即若“v ，则3 x ，y 使得湖少= v 。字行串的长 度记为川。对于一个项的集合月，记u 月= u c c t j 如果一字符串集合的所有字符串含有一长度至少为k 的公共子串则称陔集 合为k 阶的。因此，给定一字符串集合s = ( s l 芦2 ，。) ，如果3 u 且k 。 有sj ，( 1 i 疗) ，则s 为k 阶的，称“生成了s ，s 与“相关。s 的长度为s 中字符串的个数，记为阁。如果s 的子集s 为k 阶的，则记为s 。s 。一个字 符串子集称为最大化的如果它不是任何同阶子集的子集。s 的所有k 阶予集组 成的集合记为s k = ( s i s 鱼s ) 如果一个集合月瓯，且s u 月，则称月 为s 的长为协l 的k 阶覆盖。一个k 阶最优覆盖是具有最小长度的k 阶覆盖。 例如s = c a b _ _ _ _ q c a ，a c a b _ _ _ _ q b ，b b a c a b _ _ m a ) c 口，b ，f 是一个阶为4 的字符串集合。 因为盟照是s 中所有字符串的公共子串s = c a b a _ a ，a c a b a b ，b b a c a b a ) 同样是 一个长为3 的2 阶字符串集合。而s 不是一个5 阶字符串集合，因为s 中的字 符串不存在一个长为5 的公共子串。s 包含一个长为2 的5 阶最大字符串子集 a c a b _ _ _ _ q a b ，b b a c a b a 。字符串子集的集合月= a c a b a b ，b b a c a b a ， c a b a c a ) ) 构 成了s 的一个长为2 的5 阶最优覆盖，而s = ( c a b o c c i ，a c a b _ _ _ _ q b ，b b a c a b a ) 自身构 成了长为1 的4 阶最优覆盖。 现在对问题进行公式化。用一个字符串代表d n a 序列，一个子串代表一 个引物或引物的一部分，并且一个子串的集合对应一个引物的集合。尽管在上 面没有对字母表的长度进行限制，但在生物学应用中，字母表是出4 种碱基： 腺嘌呤( a d e n i n e ) 、胞嘧啶( c y t o s i n e ) 、鸟嘌呤( g u a n i n e ) ，胸腺嘧啶( t h y m i n p ) 组成，即= ( 口，c , g , t ) 对于一个给定的d n a 序列集合( 字符串集合) ，可以选择多种不同的引物 集合( 子串集合) 来扩增( 覆盖) 不同的序列子集( 字符串子集) 。为了保持问题的 实用性，这罩要求所有引物的长度至少为t ，否则可以用一个长度为0 的字 串来覆盖所有的d n a 序列，但这在实际应用中没有任何意义。然而，即使对 山东大学硕士学位论文 l ! i ! 一 i i 鼍曼鼍曼蔓曼皇皇曼曼! s 兰曼皇毫曼曼曼曼! 曼皇皇鼍毫曼! 寰曼蔓曼卑 引物长度设置一个较低的限制( 不大于d n a 序列中最短字符串的长度) ，对任何 d n a 序列集合仍可以用一个简单明显的引物集合每个d n a 序列自身组成 的集合柬覆盖，而这样的一个解是不可能使我们发现新的基因的。因此，对于 给定的d n a 序列集合，需要对特定长度的覆盖该集合的引物个数进行最小化。 最优引物覆盖问题( o p t i m a lp r i m e rc o v e r ( o p c ) p r o b i e m ) ：给定d n a 序列的 有限集合s 和正整数t ，找s 上的一个k 阶最优引物覆盖。 2 3o p c 问题的复杂性 定理2 3 1 ：o p c f 司题是n p c o m p l e t e 证明：显然o p c 的判定问题是n p 的。为了证明o p c 问题为n p c o m p l e t e 的，这罩 把最小集合覆盖问题( m s c ) 多项式变换为o p c i 闻题。m s c f a 3 题定义如下： 最小集合覆盖问题( m i n i m u ms e tc o v e r ( m s c ) p r o b l e m ) 给定一项的集合刑和证 整数h ，妒( m , m 2 ，飙) ，其中m l 劝一有限集合，闯刑中是否存在长度 至多为 的址的覆盖? ( 即是否存在鲋7 州使得阻1 h g t g u m ) 。 下面把m s c 问题的任一实例 ； 给定m s c 问题的任一实例 t 巩胁，令，= h ，= o ，l ，b i ，b 2 , , b l t l ，七= 1 0 9 ：l 州1 ( 6 ，在下面构成蜀时用作分隔符) ，构造上的字符串集合s ，黼- s , e s 对应- - t e t 。对于每一m ，朋构造对应的( o ，1 ) c 艺上的唯一字符串玑，且 i = k 。若7 仅属于集合m 矿m b ，m ( 肘，射) ，则构造母= p ，玎，：b 厂圹b ，( 如 图2 1 ) 。通过这种构造可使得与每一心对应的s 有墨。s ，因为对所有h e m , 对 应的卑有u ，s j 下面证明每一七阶的最大子集s ，必对应于某一m 。 假设存在一t 阶最大子集s 量s ，且不与任何m ，m 相对应。由假设存在“ 与s 相关，且m k 。显然砧l ，因为若“w - l i ，由上面构造知3 m ，与矾对应。 9 l l j 东大学硕士学俊论文 一ml,l,!ll -,-,illlll,i,i,illi i ! l u l l , i i ! ! s s j | i 鸟燧j c 壹应的s ，s 又因为v s ，s ，禽肖分隔笱易，艇岛只出现镪彤中，所以 爱燕最丈毒酚予袋。遨a t - s = s 就与酝对废，扶两# 不等于任僻孙出予女，因 此“一定包含某一分隔符岛，然而缸只出现猩与中，幽假设s 篮。s ，所以眵1 = 1 。 邸s7 z ， 。因为母不为空 l o p 7 lt h e no p t + - 刑 9 i fl e f i - - ot h e l lr e t u r n 1 0 f o r = n e x t t ol 朋1d o 1 1 i fl u 掰l + 蚴i m ，l i o p t lt h e n 1 2 t i l s u b s e t ( m u m ，) ，l e f t - 1 ，件1 ) ， 1 3 e n dp r o c e d u r e 一个确切的集合覆蔫算法t 麻刖分支绷索：遍删硼雌 解覆盖集合冲元素个数最多的被返同 山东大学硕士学位论文 2 5ap r o v a b l y g o o dh e u r i s t i c 由于o p c 问题是n p c o m p l e t e 的，不存在有效的确切算法，因而只能寻找 能获得近似最优解的有效的启发式算法。基于文献【s 】的结果，对于o p c 问题可 以证明不存在近似度低于l n l t i 倍最优解的多项式时间近似算法。因此，所能 4 7。 找到的最好的多项式时间算法有一个理论的执行下界d ( 1 0 9 1 7 1 ) 倍的最优解。 下面来说明用启发式贪婪算法如何来得到这个理论最优解。 一种m s c 问题的贪婪式策略是：每次选择一子集脱，它覆盖剩余未覆盖 元素最多：重复这个过程直到覆盖所有元素。该贪婪式算法可以在o ( i 州l o g ：f 册1 ) 时间完成，或经过稍微的修改可以在线性时日j 完成1 9 l 。一个简单的最坏情况的 例子如图2 3 所示，贪婪策略得出的解长度为( i 0 9 2 叫o p t ) 。 ，、 厂 b i 、 b 4b 3 b 2 a loooooooo a 2 oooopoo9 i b 5 图2 3 产生长度为的覆盖的启发式贪赞算法的例子。圆圈表示要铍覆蔫的元素， a i 、a 2 ，b 1 b 2 、b 3 、b 4 和b 5 代表不同的子集可以看出，最优覆薷为f a i a 2 1 ，而启发式贪婪算法可能选择b l 、b 2 、b 3 、b 4 和b 5 对于集合覆盖问题的启发式贪婪算法，文章佴i l l 0 - 1 2 1 已经进行了广泛的分析。 j o h n s o n 给出了一个例子，此例子中，算法生成长度为( 1 0 9 ，吲o p t ) 的覆盖l 。 l o v a s z 和j o h n s o n 都给出了算法的上限( 1 0 9 ，+ 1 ) o p t 。因此，贪婪算法在性 能上已经接近其它任何多项式时间近似算法的下限。 2 6 带权o p c 问题 上述讨论仅限于说明最小化覆盖的势问题( 即一d n a 序列集合进行p c r 扩 增所需一端的引物个数) 。因此，第4 节和第5 节的算法试图最小化字符串子集 的数目。然而，事实上，实际需要的p c r 引物长度( 1 5 个核苷酸) 使得一个合理 山东大学硕士学位论文 的引物个数( 如5 8 ) 不可能与2 0 或更多个基因家族的不同成员精确匹配。既然 我们希望通过从已知序列得出的适当个数的引物来寻找一个基凶族的新成员， 那就需要考虑如何构造非确切引物。 一种方法是使用简并的寡核苷酸引物。引物合成器可以设置在一次聚合过 程中合并2 个、3 个或4 个核苷酸，因此，可以构造许多不同序列组合的引物。 这种方法的缺点是单个序列的浓度降低了，并且混合的结果可能使这些引物对 目标基因族不再具有特异性。另一种方法，可以构造不与每个序列精确匹配的 引物，但只允许一两个错配。一般情况下，由于p c r 反应的生物化学特征，在 各个引物的一端至少要有长度为5 的公共交集，对于其它部分可以允许简并或 错配。这样，引物选择就成了阶为5 的最优引物覆盖问题，因此同时对于剩余 的i o 个相邻核苷酸就有了覆盖的权值问题所有错配的权值的和。 这罩引入一个权函数阢对于每一引物u ，和它覆盖的字符串子集s 有一个 非负权值。一个覆盖的权值越低则覆盖“质量”越高。把总权值最小的覆盖称 为最优带权覆盖( w o p c ，w e i g h t e d o p t i m a l p r i m e r c o v e r ) 。w o p c 问题的定义如 下： w o p c 问题：给定d n a 序列的有限集合s ，j 下整数k 和一非负权函数， 此权函数为每个字符串子集s 及与之对应的引物珥分配一个权值。求s 上的k 阶覆盖月，使总权值w ( s ，虬) 最小。 s e j 由于o p c 问题是n p c 的，很显然，更一般的w o p c 问题也是n p c 的( 因 o p c 本身是权值为l 的w o v e ) 。接下来，考虑一种更适合于生物上引物选择 问题的权值分配方案。在允许非精确匹配的情况，首先要对引物与序列的匹配 程度进行量化。权函数依赖于引物和单个字符串s s 的不匹配度w ( s ，“) 。 定义引物“和字符串集合s 的不匹百己度为w ( s ，”) = w ( s ，“，) 给定引物和 l t n 字符串岛，定义吣，盯) 为蜀与i , l 不匹配的字符数目。例如，设u = a b b a b ，j i = a b a b b ， 由于“和s 1 只有第3 和第4 个字符不同，所以w ( j i ，u ) - - 2 。 引入了这样一个权值分配方案后，o p c 问题就很自然地扩展成w o p c 问 题。与用最小集合覆盖技术解决o p c 问题一样，也可以用带权最小集合覆盖 ( w m s c ，w e ! i g h t e dm i n i m u ms e tc o v e r ) 技术解决w o p c 问题。w m s c 问题定义 山东大学硕士学位论文 如下： w m s c 问题( w e i g h t e dm i n i m u ms e tc o v e rp r o b l e m ) ：给定有限集合nr 上项的集合舯= m ， 疋，m 期 ，m t ，每个m 对应