1 Parallel Computation of Simple Arithmetic using Peptide-Antibody InteractionsM. Sakthi Balan Kamala Krithivasan Theoretical Computer Science Lab Department of Computer Science and Engineering Indian Institute of Technology Madras Chennai – TCS Lab, IITM

2 Organization DNA Computing Peptide Computing Proposed ModelAddition Algorithm Subtraction Algorithm Discussion TCS Lab, IITM

3 DNA Computing Uses DNA strands and Watson-Crick Complementarity as operation Highly non-deterministic Massive parallelism Solves NP-Complete Problems quite efficiently TCS Lab, IITM

4 Peptide Computing Uses peptides and antibodiesOperation – binding of antibodies to epitopes in peptides Epitope – The site in peptide recognized by antibody Highly non-deterministic Massive parallelism TCS Lab, IITM

5 Peptide Computing Contd..Peptides – sequence of amino acids Twenty amino acids. Example – Glycine, Valine Connected by covalent bonds TCS Lab, IITM

6 Peptide Computing Contd..Antibodies recognizes epitopes by binding to it Binding of antibodies to epitopes has associated power called affinity Higher priority to the antibody with larger affinity power TCS Lab, IITM

7 Computing DNA Vs PeptideTwenty building blocks (20 amino acids) Example: Glycine, Valine Different antibodies can recognize different epitopes Binding affinity of antibodies can be different Four building blocks Adenine (A), Guanine(G), Cytosine (C), Thiamine (T) Only one reverse complement – Watson-Crick Complement Complement (A) = T and Complement (G) = C TCS Lab, IITM

8 Proposed Model Consists of a peptide and set of antibodiesPeptide sequence has n position specific epitopes Epitopes epi = yi xi zi, yi and zi are switching epitopes for the ith bit. TCS Lab, IITM

9 Peptide Sequence for a 5-bit numbery4 x4 z4 y0 x0 z0 Peptide Sequence for a 5-bit number TCS Lab, IITM

10 Antibodies A = {A0, A1, …, An-1} B = {B0, B1, …, Bn-1}TAB = {TAB0, TAB1, …, TAB(n-1)} TBA = {TBA0, TBA1, …, TBA(n-1)} TCS Lab, IITM

11 Binding Sites xizi yixi For Bi For Ai xi xi xizi > xi yixi > xiTABi Zi TBAi yi TCS Lab, IITM

12 Affinity aff(TABi) > aff(Ai) aff(TBAi) > aff(Bi)aff(TABi) = aff(TBAi) TCS Lab, IITM

13 What it denotes? Ai – denotes ith bit is zeroBi – denotes ith bit is one TABi – used to switch ith bit from zero to one TBAi – used to switch ith bit from one to zero TCS Lab, IITM

14 Representation of Binary NumbersIf the ith bit is 0 then the antibody Ai is bounded to the epitope yixi If the ith bit is 1 then the antibody Bi is bounded to the epitope xizi TCS Lab, IITM

15 Example B4 A3 B2 A1 B0 10101 TCS Lab, IITM

16 Addition of Two Binary NumbersA = an-1an-2 …a0 B = bn-1bn-2 …b0 C = cn cn-1cn-2 …c0 TCS Lab, IITM

17 XOR ai bi ci 1 2 3 4 TCS Lab, IITM

18 Addition (Contd..) First step – guessing equivalent to XOR gate.The bit cn is initialized to zero. Carry propagation. TCS Lab, IITM

19 Addition (Contd..) Carry occurs only when both the bits ai and bi are 1. Carry is propagated to the left until both the bits aj and bj(j > i) are 0. If no such j exists then propagation stops making nth bit 1. j.j-1….i+1 is called the carry block. For each carry block j.j-1….i+1 invert the digits ck (i+1  k  j) TCS Lab, IITM

20 Algorithm Add antibodies Ai where ai = 0 and bi = 0 or ai = 1 and bi = 1. Add antibodies Bi where ai = 0 and bi = 1 or ai = 1 and bi = 0. For all carry block jkjk-1…ik+1 do the following in parallel. For ik +1  s  jk Add antibodies TABs, Add antibodies Bs, Add antibodies TBAs, and Add antibodies As. TCS Lab, IITM

21 Example 10110 10011 + 000101 A5 A4 A3 B2 A1 B0 TCS Lab, IITM

22 Example (Contd..) 101101 B5 A4 B3 B2 A1 B0 TCS Lab, IITM

23 Example (Contd..) 101001 B5 A4 B3 A2 A1 B0 TCS Lab, IITM

24 Algorithm ADD(A,B,C) XOR(A,B,C)BlockInversion(I1,I2,…Ik,C) where Ij are carry blocks and k is the number of carry blocks. TCS Lab, IITM

25 Algorithm - Same(C) Add excess of epitopes yi Add antibodies AiTo get the peptide sequence with antibodies in workable form Add excess of epitopes yi Add antibodies Ai Add excess of eptiopes zi Add antibodies Bi TCS Lab, IITM

26 Algorithm - SubtractionSUB(A,B,C) BlockInversion(I1,, B, B’) where I1 = n-1…0 ADD(B’, ONE, B’’) where ONE = an-1an-2…a11, ai = 0 ADD(A, B’’, C) Inverttozero(C,n) TCS Lab, IITM

27 Algorithm – InverttozeroInverttozero(C,i) Same(C) Add antibody TABi Add antibody Ai TCS Lab, IITM

28 Discussion To extract numbers from this system LimitationsNMR can be used or X-ray crystallography Limitations Obtaining monoclonal antibodies Manual process Implementation ? Universal operations ? TCS Lab, IITM

29 Acknowledgments Authors thank Saravanakumar Narayanan,TU-Munchen, Germany for helpful discussions TCS Lab, IITM

30 “They were built by 3 billion years of evolution, and we’re just beginning to tap their potential to serve non-biological purposes. Nature has given us an incredible toolbox, and we’re starting to explore what we might build” Leonard Adleman Thank You TCS Lab, IITM