Transcript PUNCH: An Evolutionary Algorithm for Optimizing Bit Set Selection

PUNCH: An Evolutionary Algorithm
for Optimizing Bit Set Selection
Adam J. Ruben, Stephen J. Freeland,
Laura F. Landweber
DNA7, 2001
Summarized by Dongmin Kim
Introduction



A randomly selected bit set may experience some physical
problems during computation
Currently no method exists for finding the “best” bit set.
PUNCH (Princeton University Nucleotide Computing
Heuristic):




It is compatible with various current DNA computing methods
It is useful in selecting bit sets
One should be able to test the limits of current methodology
One suggest new techniques for DNA computing that may works
better
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Program Architecture (1)

The primary functional unit is a three-dimensional array
N : the number of bits in the problem
 B : the number of nucleotides in each bit
 V : the number of variations on each bit set


Algorithm
 Initialize

Generate random integers between 0 and 3 and fills the array
 Assess
Each bit set is assigned the maximum possible score 2w(1  BN  w) 2
 Make a one-dimensional string from a two dimensional array
 A window (size w) fills itself with the first w nucleotides in the string
and scans the entire string, each time it encounters an identical
sequences, subtracts w from the current score
 Repeat this scanning with window which filled by the reverse of their
complements

© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Program Architecture (2)

Algorithm (cont’d)
 Pick and fill with best

Select the bit set with the highest score, and fills entire threedimensional array with that bit set
 Mutate

m represents a mutation rate, mBN(V – 1) bases are randomly
selected and reassigned
 Repeat


Repeat this procedure until each generation fails to improve r times
Modifications
 For certain protocols, the bits are treated as one linear string. since
ignoring inter-bit combinations, the maximum possible score
becomes 2w((1  B  w) N ) 2
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Mutation Rate and comparison
to Monte Carlo Sequences

Best mutation rate is m = 1 / BN

Comparison with randomly generated sequences
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
“Computing on Surfaces”
Using PUNCH


There are two ways to test the usefulness of the scoring function
 Perform an experiment using the bits it suggests
 Assess the bits used in an existing, successful experiment
Perform three analysis
 10,000 randomly generated sequence, the exact sequences Liu et
al. , sequences optimized by PUNCH
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Introducing other scoring
routine

Base Equality
 Now, scoring strategy tends to minimize variation where it matters
least for avoiding reverse-complement penalties.
 Thus, add routine counts the number of each base in a given bit set,
divides it by the total number of bases in the set, and get the
absolute value of its deviance from 0.25. Total the deviance of all
four bases, subtracts the result from 1, and use this value for the
coefficient of score. Thus, having equal amounts of each base is
rewarded

Folding Score
 Similarity to the reverse complements can be replaced with the
scores based on single-stranded DNA folding energy
 Vienna RNA package
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Comparison to another Bit Set

Perform three analysis again
 10,000 random sequences,
Faulhammer et al. sequences,
PUNCH sequences.
 Now, the base equality scoring
routine penalizes three-base
alphabet

Omitting Base Equality
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Multi-Base System
Introduce a new constant “bases” capable of being
defined such that 2 < bases < 9.
 PUNCH can run as though there are only “bases”
bases in existence
 It can work with more than four bases using
unnatural residues as dipropylglycine and
dibutylglycine

© 2001 SNU CSE Artificial Intelligence Lab (SCAI)
Future Directions

Modeling Sexual Evolution
 Flexibility
 Adaptability to various criteria
 Definable constants

Scalability
 PUNCH can help identify which experiments may not
be realistic on a larger scale
© 2001 SNU CSE Artificial Intelligence Lab (SCAI)