Bio Molecular Computer

10/25/2008

Outline 2

DNA computing applications

— 1 Introduction — 2 Background

BY: R. SAICHARAN

— 3 Definition — 4 Category — 5 Summary

Saicharan/BSBE/UNit VIII/ DBT/SNIST

1 Introduction

Background

3

4

— An overview and categorization of existing research

in DNA based computation, different computational methods, and applications that will serve the creation of a working Biomolecular Computer.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— The practical possibility of using molecules of DNA

as a medium for computation was first demonstrated by Adleman in 1994 — He successfully solved a directed Hamiltonian path problem using the tools of biomolecular engineering

Saicharan/BSBE/UNit VIII/ DBT/SNIST

1

10/25/2008

Cool picture

About Adleman

6

Leonard Max Adleman born December 31, 1945, is a computer scientist and molecular biologist at the University of Southern California. http://www.usc.edu/dept/molecularscience/fm-adleman.htm

Saicharan/BSBE/UNit VIII/ DBT/SNIST

5

Saicharan/BSBE/UNit VIII/ DBT/SNIST

What is DNA computing

Why DNA computer?

7

— DNA computing is a form of computing which uses

DNA and biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. — DNA computing is fundamentally similar to parallel computing in that it takes advantage of the many different molecules of DNA to try many different possibilities at once.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— Massively Parallel

Processing ¡

8

the ability to handle millions of operations in parallel.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

2

10/25/2008

In detail

4Category

9

10

— Perform millions of operations simultaneously;

— DNA computing research can be described following

three general categories:

— Generate a complete set of potential solutions; — Conduct large parallel searches; — Efficiently handle massive amounts of working

memory.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Classic

Natural

11

— Applications making use of "classic" DNA computing

schemes ¡

— Applications making use

classic computational problems, combinatorial problems, cryptography, playing games, DNA storage systems

of the "natural" capabilities of DNA ¡

Saicharan/BSBE/UNit VIII/ DBT/SNIST

12

natural computing, nanotechnology, smart drugs

Saicharan/BSBE/UNit VIII/ DBT/SNIST

3

10/25/2008

Contributions to fundamental research

Applications of classic DNA computing

13

14

— Contributions to fundamental research within both

computer science and the physical sciences, and especially biomolecular chemistry. ¡

computing devices, DNA chips, self-assembly

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— Classic computational problem << — Cryptography — Game play — DNA storage systems

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Applications of classic DNA computing 16

classic computational problems

— Cryptography <<

— Try to solve NP-

— Game play

complete and other hard computational problems using DNA computing tools ¡

15

— Classic computational problem

— DNA storage systems

Hamiltonian Graph problem

Saicharan/BSBE/UNit VIII/ DBT/SNIST Saicharan/BSBE/UNit VIII/ DBT/SNIST

4

10/25/2008

Cryptography

Solution

17

18

The problem: — Communication between two users in a secure manner — User A is transmitting a message to user B such that any other user C can’t decipher

— DNA-Stenography

— only the users that posses the private key can decode the

Stenography = hiding data among other data; the actual message is not modified — DNA-Cryptography Cryptography = makes a reversible change on the message à ciphertext

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— use of a private key to encode the message

message

DNA-Stenography

Example

19

— GOAL: Hide the message within DNA — Algorithm: ÷ Encode the

message as a DNA strand ÷ Attach two primers before and after ¢ These primers will act as private key ÷ Add other “junk DNA” ÷ The decoder will use the primers to get back the message ¡

the task of finding the right DNA sequence is “hard” if one doesn’t know the primers

Saicharan/BSBE/UNit VIII/ DBT/SNIST

20

— Message: “HELLO” — Each letter è 3 bases

HELLO = CGC GGC TGC TGC GGA Add 20 bases before and after CTGCTGGCACCCTTACGTCGCGGCTGCTGCGGACGAATCGAATTTGC CCAT — Add “junk DNA” to this sequence — Private key (CTGCTGGCACCCTTACGT,CGAATCGAATTTGCCCAT) — Finding the sequence without knowing the primers è need to analyze 420 primers è brute force on the DNA

Saicharan/BSBE/UNit VIII/ DBT/SNIST

5

10/25/2008

Cryptography algorithm 22

Cryptography

— A key k is used only once to encrypt/decrypt. — It is unbreakable.

Algorithm: Sender : Use k to encrypt the plaintext then destroy k Receiver: Use k to decrypt the plaintext then destroy k — Drawback: The users must know what key are using

Saicharan/BSBE/UNit VIII/ DBT/SNIST

21

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Cryptography algorithm cont.

Applications of classic DNA computing

23

24

— Classic computational problem — Cryptography — Game play << — DNA storage systems

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

6

10/25/2008

Game theory computation 25

Game strategy

— In a game, players make finite sequences of choices

restricted only by a set of rules. — A game strategy must

provide decisions for every possible game situation.

— Players receive payoffs depending on their choices

and the choices of others, including chance events.

— A strategy may use

deterministic decisions (a pure strategy) or, more generally and more powerfully, probabilistic decisions

— — — — — — — — — —

Saicharan/BSBE/UNit VIII/ DBT/SNIST

26

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Poker game rule

Poker game

27

28

1. Each of the three players starts by contributing a euros to the pot. 2. Each player is dealt a hand consisting of one card, with high and low cards being equally probable. 3. The players take turns in rotation. 4. The game ends if all players pass or when one player has bet (putting b euros into the pot) and each of the other players have chosen to call (putting b euros into the pot) or to fold (no additional cost). 5. Antes are retrieved if all players have passed. 6. Otherwise, the pot is divided equally among the highest hands of all players who have not folded.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

7

10/25/2008

Find game strategy

Solution with DNA computing

29

— DNA computing can be useful for seeking strategies

that maximize expected payoffs. — In particular, the strategies we seek depend on the

strategies of the other players, who have no incentive to reveal them.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

30

We show DNA can be used to address these aspects of game theory computations: — (1) Strategies can be individually encoded, yet pair off with opponents in game tournaments — (2) Decisions discriminating among many alternatives can be made — (3) Massive populations of strategies offer special advantages for game theory.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Applications of classic DNA computing 31

DNA storage systems

— Classic computational problem — Cryptography

— DNA is a good medium

— Game play

for storing information an a compact and stable way.

— DNA storage systems <<

Saicharan/BSBE/UNit VIII/ DBT/SNIST

32

Saicharan/BSBE/UNit VIII/ DBT/SNIST

8

10/25/2008

Advantage 33

DNA storage systems cont.

— In a standard silicon-based chip, information

processing is limited by the distance between units that process and store information.

— Double stranded DNA is

quite stable, contains redundancy, and can be maintained in vitro with error correcting enzymes

— With DNA scaffolding, we can lay out devices closely,

so the interconnections are very short and the performance very high.

— When acting as a static

storage medium, double stranded DNA tends to maintain its integrity. It is, though, vulnerable to hydrolysis reactions. Saicharan/BSBE/UNit VIII/ DBT/SNIST

34

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Error rate

Why DNA storage

— When DNA is amplified by

A gram of DNA à 1021 DNA bases = 108 terra-bytes

PCR it is subject to errors when being duplicated by polymerase. Taq polymerase, commonly used in PCR has an in vitro error rate of 1/9000 — This error rate is still reasonable, A compact disc with scratches on the surface has a much much larger error rate than this 35

(1 terabyte = 1 024GB) ¡

A few grams of DNA can hold all data stored in the world 18 terra-bytes hard drive

Saicharan/BSBE/UNit VIII/ DBT/SNIST

36

Saicharan/BSBE/UNit VIII/ DBT/SNIST

9

10/25/2008

4.2 Applications of Natural DNA computing

Nanotechnology

37

38

— Nanotechnology <<

— Nanotechnology is a field of applied science and

technology covering a broad range of topics.

— Smart drugs

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

DNA Nanomachines

DNA motors

39

40

The following applications are based on DNA nanotechnology: 1. Smart scissors, to cut DNA 2. Small DNA “Robots” which can perform several tasks 3. DNA Motors

— DNA motors can be used to pick up molecules and

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

move them around on microscopic computer chips

10

10/25/2008

4.2 Applications of Natural DNA computing 42

DNA motors

— Nanotechnology

— The motor looks like a pair of

— Smart drugs <<

tweezers. — The tweezers are made up of two strands of DNA that are attached at one end by a third strand that acts as a hinge. At the other end, the two strands each have a single-stranded handle. — Scientists open and close the tweezers by adding another strand of DNA that fuels the device. The fuel strand attaches to the handles, pulling the two strands together Saicharan/BSBE/UNit VIII/ DBT/SNIST

41

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Smart drugs 43

Smart drugs

— One of the most impressing applications for DNA

computing — DNA computer based smart drugs would be inserted into body and automatically recognize and treat diseases and other malfunction

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— Imagine having a nanoscaled

intelligent “doctor” sitting inside every cell in your body waiting for things to go wrong. — As soon as something goes wrong, the doctor diagnoses the problem and has the intelligence to take appropriate action, such as releasing a drug. 44

Saicharan/BSBE/UNit VIII/ DBT/SNIST

11

10/25/2008

Saicharan/BSBE/UNit VIII/ DBT/SNIST

45

Saicharan/BSBE/UNit VIII/ DBT/SNIST

46

DNA chips 47

Example

— Definition By wikipedia — A DNA microarray (also commonly known as gene or

genome chip, DNA chip, or gene array) is a collection of microscopic DNA spots attached to a solid surface, such as glass, plastic or silicon chip forming an array for the purpose of expression profiling, monitoring expression levels for thousands of genes simultaneously, or for comparative genomic hybridization.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— Example of an

approximately 40,000 probe spotted oligo microarray with enlarged inset to show detail.

48

Saicharan/BSBE/UNit VIII/ DBT/SNIST

12

10/25/2008

Usage

Demo

49

50

— DNA chip is relevant to many areas of biology and

— http://www.sumanasinc.com/webcontent/anisampl

medicine, such as studying treatments, disease, and developmental stages. — For example, microarrays can be used to identify disease genes by comparing gene expression in diseased and normal cells.

Saicharan/BSBE/UNit VIII/ DBT/SNIST

es/majorsbiology/dnachips.html

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Self-assembly 51

Example tiling

— Definition

Simply put, we're talking about collections of objects that put themselves together

Saicharan/BSBE/UNit VIII/ DBT/SNIST

— The idea of algorithmic

self-assembly arose from the combination of DNA computing (Adleman, 1994), the theory of tilings

52

Saicharan/BSBE/UNit VIII/ DBT/SNIST

13

10/25/2008

Conclusion 54

demo

— similarities and differences between "classic" and

"natural" areas of DNA computing — many areas computer science, mathematics, natural

science, and engineering

Saicharan/BSBE/UNit VIII/ DBT/SNIST

53

Saicharan/BSBE/UNit VIII/ DBT/SNIST

Saicharan/BSBE/UNit VIII/ DBT/SNIST

55

14