Real-Time Primer Design for DNA ChipsUse of primers in PCR and MicroarraysSlide 3Motivation:Technique: The computational modelSlide 6Technique: quantifying hybridization conditionsSlide 8Slide 9Technique: How to apply the modelTechnique: parallelize SCPCR(p,q) calculationTechnique: detailsComplexityEvaluationRelated WorkMore Related WorksObservationsReal-Time Primer Design for DNA ChipsAnnie HuiCMSC 838 PresentationCMSC 838T – PresentationUse of primers in PCR and MicroarraysPCR (polymerase chain reaction:to amplify a particular DNA fragment Use: to test for the presence of nucleotide sequencesLadder: a mixture of fragments of known length Lane 1 : PCR fragment is ~1850 bases long. Lane 2 and 4 : the fragments are ~ 800 bases long. Lane 3 : no product is formed, so the PCR failed. Lane 5 : multiple bands are formed because one of the primers fits on different places. Test of PCR products:CMSC 838T – PresentationUse of primers in PCR and MicroarraysDNA chips (Microarrays):to analyse a large number of genes in parallel.Primers:20 to 100 bases longSynthetically manufacturedAutomated design of primer A computational approachObjective: To find primers that bind well without self-hybridizingCritique: how accurate? Fixed on chipfluorescenceBound to primerCMSC 838T – PresentationMotivation:This group uses the automated NucliSens extraction system (bioMerieux) to develop their primers here.CMSC 838T – Presentation1. Select primers from target sequence two primers P (forward) and Q (reverse) for PCR, one primer for DNA chip (microarray)Using window size W, number of possible primers with length between m and n within 1 window is: Technique: The computational modelnmllWS 1)(CMSC 838T – PresentationTechnique: The computational model2. For each primer pair, or single primer,Quantify 4 hybridization conditions:a. Primer length b. Melting temperaturec. GC contentd. Secondary structurei. Self annealingii. Self end annealingiii. Pair annealingiv. Pair end annealingWe are starting hereCMSC 838T – PresentationTechnique: quantifying hybridization conditionsa. Primer length len(P)Affect melting temperature and hybridizationb. Melting temperature Tm(P)Temperature at which the bonds between primer and gene sequence breakc. CG content CG(P)G-C pairs are more stable than A-T pairs (because of more H-bonds)( )# in # in 100G P C PGC pp+= *( )( )( )( )( )( ),1 0490ln1.987 /50 10237.1521.6mH pT p T tS p Rp primerR cal C molT Ct CH p enthalpyS p entropygg-D= + +D + *== *= �=-=-D =D =oooWhat is this measure good for?( ) ( )( ) ( )111111,,ni iini iiH p H p pS p S p p-+=-+=D = DD = D��CMSC 838T – PresentationTechnique: quantifying hybridization conditionsd. Secondary structureStudy how likely a primer entangles with itself or with another primerP = {p1, p2, …, pn}, Q = {q1, q2, …, qm}, Scoring function:S(pi, qj) = 2 if {pi, qj} = {A, T} = 4 if {pi, qj} = {C, G} = 0 otherwiseExample: P: ...AGCTTTAGCCATAG Q: TCTTAGGATCGC... score S(pi, q1) = 2+4+2+2+4 = 14Position i of primer PCMSC 838T – PresentationTechnique: quantifying hybridization conditionsFour measures of secondary structure:i. Self annealing, SA(P, P’)•P’ = reverse of PPP’P’P’P’P’P’P’ii. Self end annealing, SEA(P, P’)•Like Self annealing•k>=0•Only count longest continuous overlapsPP’P’P’P’iii. Pair annealing, PA(P, Q)•P and Q are the forward and reverse primersiv. Pair end annealing, PEA(P, Q)•similar to self end annealingmikiimmkppsppSA11,...,1)',()',(maxCMSC 838T – PresentationFor PCR:P is forward primer, Q is reverse primerIdeally, no annealing, length, GC and temp of P equals QThe optimization is:For DNA chips (Microarrays):Q doesn’t exist. No pair annealing to study. Only 5 terms left.Technique: How to apply the model( )[ ], ,0 0 0 0 0 00.5 1 1 0.1 0.2 0.5 1 1 0.1 0.2 0.1 0.2ideal p p m p p p m pSCPCR p len G C T len GC Tw� �=� �=( )( ) ( )min( , )PCRpTPCR ideall pwherel p SCPCR p q SCPCR p w� �� �= - �� �� �]),(),()()()()()()()()()()([),(qpPEAqpPAqSEAqSAqTqGCqlenpSEApSApTpGCplenqpSCPCRmmCMSC 838T – PresentationTechnique: parallelize SCPCR(p,q) calculationCalculate Len, GC, Temp, SA and SEA in parallelCompute PA and PEA in parallelCMSC 838T – PresentationMelting temperature and CG content:Simple adder+dividerUse pipelining1st one: O(m)Subsequent cost: O(1)Annealing matrixTechnique: detailsadbdcdabcdefcebeaeafbfcfWhole window: AGCGATATAi-th P primer: GCGATA(i+I)-th P primer: CGATAT• CG(Pi+1) = CG(Pi) - 1• H(Pi+1) = H(Pi) - H(GC) + H(AT), • similar for  SCMSC 838T – PresentationComplexity for sequential algorithm:For PCR:Number of choices of P (window size=Wp):Number of choices of Q (window size=Wq):Each distance SCPCR(P,Q):Total: Complexity for parallel algorithm:For PCR:Distance measure SCPCR(P, Q) = O(1)Total: O(S*T)Similar but simpler for MicroarrayComplexityppnmlplWS 1)(qqnmlqlWT 1)( qpqpllllO 22  qpqpWWWWTSO 22O(S*S*T*T) is a typo in the paperCMSC 838T – PresentationEvaluationExperimental environment512 primer pairs, |Wp| = |Wq| = 161. 500MHz Celeron system with integrated hardware accelerator2. Software implementationEvaluation results1920 secs for software implementation3.41 secs for using hardware acceleratorCMSC 838T – PresentationRelated WorkPrevious approachDOPRIMER Same computational modelDiffer in the way of doing dynamic programming Sequential in natureOther Primer selection softwares Eg: Primer Premier 5, Primer3, PrimerGen, PrimerDesignSimilarities:Criteria: Length, Temp range, GC range, GC Clamp, 3’ end stability, uniqueness of 3’ end base, Dimer/hairpins, Degeneracy, Salt concentration, Annealing Oligo Concentration, etcDifferences:Not a weighed linear sum of all criteriaNeed much expert’s supervision, the numerical criteria are used as a guide onlyCMSC 838T – PresentationMore Related WorksCase studyBurpo did a critical review of PCR primer design algorithmsSubject: saccharomyces cerevisiae deletion strainsConclusion: no suitable program for the task of post-design PCR analysisEspecially in the aspect of accurately predicting non-specific hybridization