Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Bio-op Errors in DNA Computing

A Sensitivity Analysis

Daniel Bilar

University of New Orleans

Department of Computer Science

New Orleans, Louisiana, USA

May 27, 2009

ACIS SNPD ’09

Catholic University of Daegu

Daegu, Republic of Korea

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Talk Roadmap

Motivation DNA Computing

Parallelizable combinatorial problems

such as Hamiltonian Path,

DES code breaking and knapsack problems [1, 2, 3] can be solved
Error rates

of biological operation range from 10

−5

to 0.05 [4]

Sensitivity Analysis on DNA Algorithm

Simulate DNA algorithm

for Shortest Common Superstring

Problem
Perform sensitivity analysis

for each step of algorithm

Goal

is to make algorithm error resistant

Tuning the Errors

Good Encoding

focus on input data error-resistance

Multiplexing

focus on operation error-resistance

Constant Volume Transformation

focus on algorithm as a whole

error-resistance

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Chosen Problem

Shortest Common Superstring Problem

NP-Complete Combinatorial Problem

Given an alphabet Σ, a

finite set R of strings from Σ

(the set of all words over Σ) and a

positive integer K, find a string w ∈ Σ

with length |w| ≤ K such that

each string x ∈ R is a substring of w.

Gloor’s Algorithm [5]

1

Encode

all the strings x

1

,

x

2

, . . . ,

x

n

∈ R as DNA strands

2

Generate all possible solutions

which are DNA strands w of

length less than or equal to K

3

Iteratively refine solution

Let x

j

be a string of R. From our

solution population, select only the ones which contain x

j

as a

sub-string. Let this be our new solution population. Repeat this
step for each string x

i

∈ R, 1 ≤ i ≤ n

4

Return result

if our solution population is non-empty, return

’Yes’ and the solution string(s). Otherwise, return ’No’

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Empirical Error Rates

Step

Bio-op

Type I Error

Type II Error

1) Encoding sub-strings

Synthesizing through se-
quential coupling

NA

Wrong letter is bonded
(0.05)

2) Generate solution pop-
ulation

Synthesizing through se-
quential coupling

NA

Wrong letter is bonded
(0.05)

3) Match sub-strings to so-
lution population

Extraction using affinity
purification

Correct match is not rec-
ognized as match (0.05)

Incorrect match is recog-
nized as match (10

−6

)

4) Detect and output final
solution

Sequencing using poly-
merase chain reaction and
gel electrophoresis

Correct match is not rec-
ognized as match (0.05)

Incorrect match is recog-
nized as match (10

−5

)

Table:

Error rates of bio-operations [4][6]

Gloor’s Algorithm [5]

1

Encode

all the strings x

1

,

x

2

, . . . ,

x

n

R

as DNA strands

2

Generate all possible solutions

which are DNA strands w of length less than

or equal to K

3

Iteratively refine solution

Let x

j

be a string of R. From our solution

population, select only the ones which contain x

j

as a sub-string. Let this be our

new solution population. Repeat this step for each string x

i

R

,

1 ≤ i ≤ n

4

Return result

if our solution population is non-empty, return ’Yes’ and the

solution string(s). Otherwise, return ’No’

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Experiment and Results

Step

Type I Error Levels

Type II Error Levels

1) Encoding sub-strings

NA

0.05, 0.005

2) Generate solution pop-
ulation

NA

0.05, 0.005, 0.0005, 0.00005

3) Match sub-strings to so-
lution population

0.05, 0.005, 0.0005, 0.00005

NA

Table:

Bio-op error levels for factorial experiments

Setup

Algorithm implementation

of all possible solutions of length K ≤ 6

and chosen sub-string matches gg, t, cg, tg, tgg
Factorial experiment

varied error rates for three bio-ops

Result

Hit rate

most sensitive to the type II errors in step 1. In conjunction

with lower type I error of step 3, pushed hit rate above the 90% mark
Lesson

is encoding and extraction steps most important

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Targeting Input Data: Good Encoding Overview

Target Input Data

False encoding of search strings most sensitive factor. Practical mechanism
that produces error is hybridization stringency (number of complementary
base pairs that have to match for DNA oligonucleotides to bond)

Deaton’s Upper Bound [7]

Studied Hamiltonian Path Problem
Found upper bound

of number of vertices that can be encoded in

oligonucleotides of length n without producing mismatches

|C|

t

i=0

n
2

i

(q − 1) ≤ q

n
2

where t is the number of errors that occur in hybridization, q is cardinality of
the alphabet (q = 4 for DNA), and |C| is the number of vertices.
Mismatch-free

defined as every codeword being a distance greater than t

from any other codeword
If the Hamming bound satisfied, no type II matching errors

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Targeting Input Data: Good Encoding Discussion

Deaton’s Upper Bound [7]

Upper bound

of number of vertices that can be encoded in oligonucleotides

of length n without producing mismatches

|C|

t

i=0

n
2

i

(q − 1) ≤ q

n
2

where t is the number of errors that occur in hybridization, q is cardinality of
the alphabet (q = 4 for DNA), and |C| is the number of vertices.
Mismatch-free

defined as every codeword being a distance greater than t

from any other codeword
If the Hamming bound satisfied, no type II matching errors

Discussion

Biological pendant of the Hamming error-correcting code
Requires mismatch-free encoding

, may not be possible for a given

problem
Conclusion

Added error flexibility has to be bought with carefully designed

oligonucleotide encoding.

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Targeting Operation: Multiplexing Overview

Target Operations

System rebound from error

assuming a certain number of faulty inputs

von Neumann’s Multiplexing [8]

Given input error rate and operation error rate ǫ, critical level of input must
be determined for a desired output error rate ψ. Interpret group of inputs
higher than critical level δ as a positive state, lower than critical level as
negative

state.

DNA computing adaption

For every bio-op with error rate ǫ, fix your output error rate ψ to a desirable
level by replicating the inputs N times. Given N, find your critical level δ
using

ρ(N) =

1

2

πk

e

k
2

, with k = 0.62

N

Interval zone

(δ, 1 − δ) is one of uncertainty, where the error rate may or

may not have been achieved. If at least the fraction 1 − δ of inputs remains
the same, operation produces a positive result. If at most fraction δ of your
inputs is same, operation produces negative result

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Targeting Operation: Multiplexing Discussion

N

1000

2000

3000

5000

10000

20000

ρ(N)

2

.7 ∗ 10

−2

2

.6 ∗ 10

−3

2

.5 ∗ 10

−4

4

∗ 10

−6

1

.6 ∗ 10

−10

2

.8 ∗ 10

−19

Table:

Given bio-op error rate ǫ = 0.005, probability of uncertainty as a function of N

DNA computing adaption

For every bio-op with error rate ǫ, fix your output error rate ψ to a desirable
level by replicating the inputs N times. Given N, find your critical level δ.
Interval zone

(δ, 1 − δ) is one of uncertainty, where the error rate may or

may not have been achieved. If at least fraction 1 − δ of inputs remains the
same, operation produces positive result. If at most fraction δ, operation
produces negative result

Discussion

N

becomes very large

to decrease the probability of uncertainty

Multiplexing helps stabilize errors in algorithms with little data dependencies.
In some situations, multiplexing amplifies errors

(divide-and-conquer

algorithms)
Suggests reformulation of algorithms to suit m.o. of DNA computing

Overview

Problem Setup And Analysis

Tuning the Errors

Conclusion

Sources

Targeting Algorithm: Constant Volume Overview

Target Algorithm

Previous two approaches concentrated on improving the operand and
statistically improving error rate of operation
Broader view of adapting algorithm to the particularities of DNA computing

Boneh’s Transform Approach [6]

Classify problems as Decreasing Volume’ if number of strings decrease as the
algorithm executes, ‘Constant Volume’ if number remains the same and
‘Mixed’ otherwise. DNA algorithms are ‘Decreasing Volume’, transform into
‘Constant Volume’

Modification of bio-op steps 3 and 4 from Table 1

Step 3*

Let s be the number of extraction steps, and let the initial solution

population be 2

n

strings. Double the solution population every

s

n

steps using

a PCR (a DNA amplification technique) operation.
Step 4*

Pick m strands at random from the final solution population and

check whether at least one of them is the desired solution. If not, report
failure.