随机引物序列选择的快速算法

摘要

设基因组序列S={T1,T2,…,Tk},其中Ti为DNA序列,是由A、G、C、T四种字符组成的序列,这里称为主串.任意两个主串均不相同,Ti≠Tj,i≠j.记S的总长度为L.所谓引物是指与待扩增核酸片段两端互补的寡核苷酸,即其也是由四种碱基组成的序列.在引物设计中,随机引物序列的出现次数是指引物在多少个基因中出现,这里定义为引物次数,用p来表示.pi意为ui在S中的pi个主串中出现,如图1所示,u在S中的引物次数为3.本文根据随机引物序列选择这一实际问题，以最简单直接的算法为基础，提出了基干 Hash的快速、简单的统计算法，并在数据结构上进行了进一步优化，为生物学研究中的引物选择提供了有力的工具。经多次实验验证，本文提出的优化算法稳定、高效，对类似于子串查找和统计的问题具有重要价值。