 |
    |
String Binding-Blocking Automata*
M. Sakthi Balan
Department of Computer Science and Engineering,
Indian Institute of Technology, Madras
Chennai - 600036, India
sakthi@cs.iitm.ernet.in
Abstract. In a similar way to DNA hybridization, antibodies which specifically recognize peptide sequences can be used for calculation [3,4]. In [4] the concept of peptide computing via peptide-antibody interaction is introduced and an algorithm to solve the satisfiability problem is given. In [3], (1) it is proved that peptide computing is computationally complete and (2) a method to solve two well-known NP-complete problems namely Hamiltonian path problem and exact cover by 3-set problem (a variation of set cover problem) using the interactions between peptides and antibodies is given.
*Financial
support from Infosys Technologies Limited, India is acknowledged
LNCS 2723, p. 425 f.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003