Minimum Set Primers and Unique Probes Design Algorithms for

Differential Detection of Symptom-Related Pathogens

HOME
Introduction
Methodology
Computational Results
	MCGA for Set Covering Problem
	MCGA for Primer design
Bio-Experiment
Conclusion
Reference

Table 2. Comparison of primer reduction among two heuristics and MCGA. Linear Time Heuristic a Densest Subgraph Heuristic a MCGA Organism No. of genes b Reduction c Time (s) Reduction c Time (s) Reduction c Time (s) Schistosoma mansoni 817 20.85±0.17% 8.03 24.92±1.18% 30,151.11 24.36±0.20% 1,824.70 Medicago truncatula 4,466 38.61±0.29% 18.52 42.22±1.12% 74,549.02 42.72±0.12% 3,121.42 Hordeum vulgare 11,180 63.31±0.27% 1,069.92 71.80±2.14% 227,001.40 70.57±0.07% 7,294.19 Ciona intestinalis 12,669 55.21±1.65% 1,765.03 63.98±4.59% 467,867.35 68.00±0.10% 12,532.50 a Implemented as described by (Fernandes and Skiena, 2002) . b Number of genes which can be amplified with appropriate primer pairs. c Percent of reduced primers, averaged over 30 repeated runs.        The comparison among LTH, DSH, and MCGA is made in a Pentium 4 2.6 GHz PC running Linux operating system. The melting temperature range for the genome-wide PCR primers is 37~ 43 °C . Each of the three methods have been repeated 30 times. The results average over 30 runs. The average reduction rates, standard deviations, and average time used are summarized in Table 2.      From Table 2 we can see that LTH is the fastest algorithm among the three. MCGA is slower than LTH but faster than DSH over an order of magnitude. The primer reduction rates of DSH and MCGA are comparable, both much better than that of LTH. In the case of Ciona intestinalis , DSH reduced 63.98% of the primers, whereas MCGA reduced 68% of the primers required to amplify 12,669 sequences. MCGA only uses 2.68% of the time used by DSH algorithm. That is, comparing to DSH MCGA saved more than 5 days when applied to Ciona intestinalis .      According to these results, we can conclude that MCGA is agood balance achieving both performance and solution quality. The solution quality of MCGA is much better than that of LTH. With higher performance than and comparable reduction rate to DSH, MCGA is a good alternative to the two heuristics for the design of multiple-use and minimum set primers.