A Formal Language Model of DNA Polymerase Enzymatic Activity

Issue title: Special issue in memoriam of Yurii Rogozhin

Article type: Research Article

Authors: Enaganti, Srujan Kumar | Kari, Lila | Kopecki, Steffen

Affiliations: Department of Computer Science, The University of Western Ontario, London, ON N6A 5B7, Canada. [email protected]; [email protected]; [email protected]

Note: [] Address for correspondence: Department of Computer Science, The University of Western Ontario, London, ON, Canada This research was supported by a Natural Science and Engineering Council of Canada (NSERC) Discovery Grant and a University of Western Ontario Grant to L.K.

Abstract: We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: a template language L1 and a primer language L2. We call this language operation L1-directed extension of L2 and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question.

DOI: 10.3233/FI-2015-1206

Journal: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 179-192, 2015