Re: Optimization algorithm help needed

Bryan <bcc@xxxxxxxxxx> writes:

Hi,

I'm doing a little bioinformatics work, and could use some advice on a
problem. Im posting it here becuase it really is an optimization issue
(I think).

Given a sequence, I can design multiple sets of primers that will
amplify parts of this sequence with PCR. The region of the sequence
amplified between the primers is the product.

So I might have something like this:

Seq: AAGGGCCTTTGGAAGGGCCCTGCGGTTCTCTAAGGCCGCGGCTTTA
P1 >>>> <<<<<
P2 >>>> <<<<<
P3 >>>>> <<<<
P4 >>>> <<<<<<<
P5 >>>> <<<<
P6 >>> <<<<

So, here's where the optimization starts... each primer set (P1-P6) is
ranked by a score as to how well it will work with the PCR. I also
need to favor longer products, as these primers cost money and the less
of them I have to order the better. I also need to cover the entire
sequence with primers.

So is there a way to pick the ideal set of primers, optimizing for:
1. Score
2. Length
3. Coverage

I think this is not an unusual problem, maybe there are papers that do
something like this? Or maybe even exactly this?

Maybe more info is needed?

Any suggestions are appreciated!

It looks to me like a weighted "Set Covering Problem". See e.g.
<http://en.wikipedia.org/wiki/Set_covering_problem>. Set covering is
NP-complete, but in practice I think these problems tend to be relatively
easy to solve. If there aren't too many possible primers, integer linear
programming (e.g. using Lindo) might be able to handle it.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Optimization algorithm help needed
    ... I'm doing a little bioinformatics work, and could use some advice on a problem. ... Im posting it here becuase it really is an optimization issue. ... Given a sequence, I can design multiple sets of primers that will amplify parts of this sequence with PCR. ...
    (sci.math)
  • Re: Optimization algorithm help needed
    ... Given a sequence, I can design multiple sets of primers that will ... here's where the optimization starts... ... ranked by a score as to how well it will work with the PCR. ...
    (sci.math)
  • Re: Optimization algorithm help needed
    ... I just started with python, and have a for loop question ... Im posting it here becuase it really is an optimization issue. ... Given a sequence, I can design multiple sets of primers that will amplify parts of this sequence with PCR. ...
    (sci.math)
  • Re: Optimization algorithm help needed
    ... a specific sequence and snips the part between two ... No. Primers are pairs of short DNA sequences which will amplify the sequence of DNA between them in PCR. ... Would the primer snip the whole strand into ... P1 in your drawing above is to snip ...
    (sci.math)
Quantcast