核酸体外扩增思想是由Khorana及其同事于1971年提出,并由美国PE-Cetus公司的人类遗传研究室Mullis等人于1985年发明了具有划时代意义的聚合酶链反应(Polymerase Chain Reaction,PCR)后才得以实现。PCR技术具有特异、敏感、产率高、快速、简便、重复性好、易自动化等突出优点。由于PCR方法的方便、快速、有效,很快便得到了广泛的应用,并大大推动了分子生物学及其相关学科的研究和发展。PCR技术是生物医学领域中的一项革命性创举和里程碑。引物是PCR特异性反应的关键。随着PCR技术的发展,引物设计成为一个重要的问题。本文对以往PCR设计中的问题进行了研究,在介绍前人算法的基础上提出了新的算法。 本文首先对PCR引物设计相关的背景和概念进行了简要介绍,分析了PCR技术的原理和特点,说明了对引物设计问题进行研究的必要性。然后对PCR引物设计问题中的引物选择、简并引物设计和随机引物设计进行了研究。 在PCR试验中的引物选择问题中,证明了对扩展—DNA序列集合所需的引物个数进行最小化问题是NP-complete,设计并实现了分支限界算法和启发式贪婪近似算法。另外还对需要同时最优化引物个数及它们的权值总和的WOPC问题进行了探讨。 在简并的引物设计问题中,证明了简并引物设计问题和几个简化的简并引物设计问题都是NP-complete的,但在一些受限的实例中是多项式可解的。然后对一种简化的简并引物设计问题提出了多项式近似算法。 在随机引物设计问题中,根据随机引物设计的一般原则,提出了一种基于Hash思想的统计算法,通过建立合理的数据结构和子串Hash函数,快速计算出基因组中引物序列的出现频率,从而设计合适的随机引物。为基因组学中的引物设计提供了有力工具。