资源描述：
《随机引物序列选择的快速算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机科学2004Vol.302.10(增刊)随机引物序列选择的快速算法AFastAlgorithmfortheSelectionofRandomPrimer张洪福朱大铭(山东大学计算机科学与技术学院济南250061)AbstractTheselectionofrandomprimersisanimportantresearchtopicinbiology.Generallyrandomprimers，whoselengthisnormally10or11,areselectedfromoligonucleotideswiththe
2、higherfrequencyofoccurrenceincodinggenomeE'3.Inthispaper,wepresentastatisticalalgorithmbasedontheutilizationofHashtablewhichcansolvetheproblemveryefficiently.ByvirtueofestablishingappropriatedatastructuresandHashfunctions,wecancomputethefrequencyofoccurrenceofprimering
3、enomeveryquickly,whichprovidesapowerfulapparatusfortheselectionofprimeringenomics.Forinstance,usingtheprogramwhichimplementthealgorithmwithVC++,wecancomputethe10.4Mbpgenomeofmyxobacter(prokaryoticorganism)in35.28sifthelengthoftheprimeris10,whiletheprogramimplementingth
4、eoldalgorithmscost18.94h.KeywordsGenome,Primer,Base,Hash中频率最高的寡核昔酸中选出。本文着重讨论在随1引言机引物序列设计中如何快速计算一定长度的寡核昔设基因组序列S=(T=T2,-,TO，其中T，为酸的频率。主要通过建立合适的数据结构和HashDNA序列，是由A,G,C,T四种字符组成的序列，函数来减少子串和主串之间的比较次数，只扫描一这里称为主串。任意两个主串均不相同，T;笋T;,i笋遍S，即可求出每一出现子串的引物次数，从而大大1。记S的总长度为L。所谓引物是指与待扩增核酸
5、减少了算法的执行时间。经过对粘球菌(原核生物)片段两端互补的寡核昔酸，即其也是由四种碱基组的多组基因组序列的测试，本算法执行速度快，效率成的序列。在引物设计中，随机引物序列的出现次数高。是指引物在多少个基因中出现，这里定义为引物次本文第2部分介绍了一般性的方法，并讨论了其数，用P来表示。P*意为u‘在S中的P‘个主串中出优缺点。第3部分提出了一快速算法，并对其进行了现，如图1所示，u在S中的引物次数为3,分析。第4部分对算法进行了测试。千2一般方法对于长度为n的碱基序列，共有4”种可能形之S式，即4”种可能子串。最直接的方法是对每一
6、可能!
7、毛子串与所有主串分别进行比较，求出它的引物次数，L一曰......一毛这样的一个过程称为“一轮”。经过40轮便可求出所有出现子串的引物次数，进而得出前m个引物次数最高的子串。该算法描述如下:图1算法1问题:找出m个长为n的随机引物序列U=AlgorithmGeneral-Primer-Get(S){Ultuz}="UM)，其中u;称为子串。要求U是由所有1.While未产生所有子串长为n的子串中在S中引物次数最高的m个组成。2.产生一未计算子串u在文[1]中，对大肠杆菌基因组的原核生物的差3.i=1异显示的PT-PCR的引物
8、设计进行了研究，并提出4.Whilei<=k了随机引物序列设计的几个一般性原则。其中重要5.Ifu在T，中的一条是在引物设计中，引物序列应从编码基因组6.count++张洪福硕士研究生，研究方向:智能并行软件。·125·7.EndIf2.去除引物次数低，不满足要求的子串8.i++在1的过程中，可以同时记录每一子串最多出现9.Endwhile的次数(这并不是问题要求的引物次数)。设计数据10.Endwhile结构如下:11.求出引物次数最高的m个子串分析:该方法思想简单，易于理解，但由于对所StrNumCount无符号整数无符号整数有
9、可能子串都要扫描S，因而执行效率很低。虽然该算法的时间复杂度为O(L)由于n为常数)，但其StrNum:子串对应的整数系数为n4"，执行时间很长。Count:子串出现的次数3改进算法在扫描S的过程中，每获得一子串，和上面一样先判断其是
