{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:17:59Z","timestamp":1763662679117},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"21","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Primer approximation multiplex PCR (PAMP) is a new experimental protocol for efficiently assaying structural variation in genomes. PAMP is particularly suited to cancer genomes where the precise breakpoints of alterations such as deletions or translocations vary between patients. The design of PCR primer sets for PAMP is challenging because a large number of primer pairs are required to detect alterations in the hundreds of kilobases range that can occur in cancer. These sets of primers must achieve high coverage of the region of interest, while avoiding primer dimers and satisfying the physico-chemical constraints of good PCR primers. We describe a natural formulation of these constraints as a combinatorial optimization problem. We show that the PAMP primer design problem is NP-hard, and design algorithms based on simulated annealing and integer programming, that provide good solutions to this problem in practice.<\/jats:p><jats:p>The algorithms are applied to a test region around the known CDKN2A deletion, which show excellent results even in a 1:49 mixture of mutated:wild-type cells. We use these test results to help set design parameters for larger problems. We can achieve near-optimal designs for regions close to 1 Mb.<\/jats:p><jats:p>Contact: \u00a0abashir@ucsd.edu<\/jats:p><jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm390","type":"journal-article","created":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:27:43Z","timestamp":1188606463000},"page":"2807-2815","source":"Crossref","is-referenced-by-count":17,"title":["Optimization of primer design for the detection of variable genomic lesions in cancer"],"prefix":"10.1093","volume":"23","author":[{"given":"Ali","family":"Bashir","sequence":"first","affiliation":[{"name":"1 Bioinformatics Program, 2Department of Computer Science and Engineering, 3Moores Cancer Center, University of California, San Diego and 4Department of Computer Science & Center for Computational Molecular Biology, Brown University, USA"}]},{"given":"Yu-Tsueng","family":"Liu","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Program, 2Department of Computer Science and Engineering, 3Moores Cancer Center, University of California, San Diego and 4Department of Computer Science & Center for Computational Molecular Biology, Brown University, USA"}]},{"given":"Benjamin J.","family":"Raphael","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Program, 2Department of Computer Science and Engineering, 3Moores Cancer Center, University of California, San Diego and 4Department of Computer Science & Center for Computational Molecular Biology, Brown University, USA"}]},{"given":"Dennis","family":"Carson","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Program, 2Department of Computer Science and Engineering, 3Moores Cancer Center, University of California, San Diego and 4Department of Computer Science & Center for Computational Molecular Biology, Brown University, USA"}]},{"given":"Vineet","family":"Bafna","sequence":"additional","affiliation":[{"name":"1 Bioinformatics Program, 2Department of Computer Science and Engineering, 3Moores Cancer Center, University of California, San Diego and 4Department of Computer Science & Center for Computational Molecular Biology, Brown University, USA"}]}],"member":"286","published-online":{"date-parts":[[2007,8,30]]},"reference":[{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1186\/1471-2105-7-172","article-title":"GENOMEMASKER package for designing unique genomic PCR primers","volume":"7","author":"Andreson","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023041107265331300_","first-page":"4868","article-title":"Cdkn2a\/p16 is inactivated in most melanoma cell lines","volume":"57","author":"Castellano","year":"1997","journal-title":"Cancer Res."},{"key":"2023041107265331300_","volume-title":"Hardness of PAMP","author":"Chuzhoy","year":"2007"},{"key":"2023041107265331300_","first-page":"43","article-title":"Greedy algorithms for finding a small set of primers satisfying cover and length resolution conditions in PCR experiments","volume":"8","author":"Doi","year":"1997","journal-title":"Genome Inform Ser Workshop Genome Inform"},{"key":"2023041107265331300_","first-page":"73","article-title":"A greedy algorithm for minimizing the number of primers in multiple PCR experiments","volume":"10","author":"Doi","year":"1999","journal-title":"Genome Inform Ser Workshop Genome Inform"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1038\/nrg1901","article-title":"Highly parallel genomic assays","volume":"7","author":"Fan","year":"2006","journal-title":"Nat. Rev. Genet."},{"key":"2023041107265331300_","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1038\/nrm1987","article-title":"Regulation of the INK4b-ARF-INK4a tumour suppressor locus: all for one or one for all","volume":"7","author":"Gil","year":"2006","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1126\/science.271.5247.350","article-title":"DPC4, a candidate tumor suppressor gene at human chromosome 18q21.1","volume":"271","author":"Hahn","year":"1996","journal-title":"Science"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1038\/ng0997-119","article-title":"Reverse genetics by chemical mutagenesis in Caenorhabditis elegans","volume":"17","author":"Jansen","year":"1997","journal-title":"Nat. Genet."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1101\/gr.229102","article-title":"The human genome browser at UCSC","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1093\/bioinformatics\/17.3.214","article-title":"Efficient primer design algorithms","volume":"17","author":"Kmpke","year":"2001","journal-title":"Bioinformatics"},{"key":"2023041107265331300_","author":"Lipson","year":"2002","journal-title":"Optimization Problems in Design of Oligonucleotides for Hybridization Based Methods. Master's; Thesis."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"e380","DOI":"10.1371\/journal.pone.0000380","article-title":"A novel approach for determining cancer genomic breakpoints in the presence of normal DNA","volume":"2","author":"Liu","year":"2007","journal-title":"PLoS ONE"},{"key":"2023041107265331300_","first-page":"210","article-title":"Selecting optimal oligonucleotide primers for multiplex PCR","volume":"5","author":"Nicodme","year":"1997","journal-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1038\/368753a0","article-title":"Deletions of the cyclin-dependent kinase-4 inhibitor gene in multiple human cancers","volume":"368","author":"Nobori","year":"1994","journal-title":"Nature"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1097\/00005072-199709000-00005","article-title":"Detection of p16 gene deletions in gliomas: a comparison of fluorescence in situ hybridization (FISH) versus quantitative PCR","volume":"56","author":"Perry","year":"1997","journal-title":"J. Neuropathol. Exp. Neurol."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"S11","DOI":"10.1038\/ng1569","article-title":"Array comparative genomic hybridization and its applications in cancer","author":"Pinkel","year":"2005","journal-title":"Nat. Genet."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1186\/1471-2164-6-102","article-title":"Computational tradeoffs in multiplex PCR assay design for SNP genotyping","volume":"6","author":"Rachlin","year":"2005","journal-title":"BMC Genomics"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1002\/gcc.20119","article-title":"Homozygous deletions of CDKN2A caused by alternative mechanisms in various human cancer cell lines","volume":"42","author":"Raschke","year":"2005","journal-title":"Genes Chromosomes Cancer"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1006\/excr.2000.5149","article-title":"p16(MTS-1\/CDKN2\/INK4a) in cancer progression","volume":"264","author":"Rocco","year":"2001","journal-title":"Exp. Cell. Res."},{"key":"2023041107265331300_","first-page":"365","article-title":"Primer3 on the www for general users and for biologist programmers","volume":"132","author":"Rozen","year":"2000","journal-title":"Methods Mol. Biol."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1126\/science.1117679","article-title":"Recurrent fusion of TMPRSS2 and ETS transcription factor genes in prostate cancer","volume":"310","author":"Tomlins","year":"2005","journal-title":"Science"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"226","DOI":"10.2144\/04372ST03","article-title":"Autodimer: a screening tool for primerdimer and hairpin structures","volume":"37","author":"Vallone","year":"2004","journal-title":"Biotechniques"},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1101\/gr.4247306","article-title":"Decoding the fine-scale structure of a breast cancer genome and transcriptome","volume":"16","author":"Volik","year":"2006","journal-title":"Genome Res."},{"key":"2023041107265331300_","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1101\/gr.2885205","article-title":"A genotyping system capable of simultaneously analyzing &gt;1000 single nucleotide polymorphisms in a haploid genome","volume":"15","author":"Wang","year":"2005","journal-title":"Genome Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/21\/2807\/49823479\/bioinformatics_23_21_2807.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/21\/2807\/49823479\/bioinformatics_23_21_2807.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T23:56:50Z","timestamp":1684022210000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/21\/2807\/371536"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,30]]},"references-count":27,"journal-issue":{"issue":"21","published-print":{"date-parts":[[2007,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm390","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,11,1]]},"published":{"date-parts":[[2007,8,30]]}}}