47. OPTIMIZATION OF PRIMER DESIGN FOR DETECTION OF VARIABLE GENOMIC LESIONS IN CANCER
Department: Computer Science & Engineering
Research Institute Affiliation: Graduate Program in Bioinformatics
Faculty Advisor(s):
Vineet Bafna
Primary Student
Name: Ali M. Bashir
Email: abashir@ucsd.edu
Phone: 858-534-8855
Grad Year: 2008
Abstract
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 interactions between primers (such as primer dimers and mispriming primer pairs) and satisfying the physicochemical 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. 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 1Mb and primer input sets exceeding 10,000 primers.
Related Links:
All Content Copyright 2007 Regents of the University of California. All rights reserved.
Official Web page of the University of California, San Diego.
