STRING VARIABLE GRAMMAR - A LOGIC GRAMMAR FORMALISM FOR THE BIOLOGICAL LANGUAGE OF DNA

Building upon Definite Clause Grammar (DCG), a number of logic grammar systems have been developed that are well-suited to phenomena in natu ral language. We have proposed an extension called String,Variable Gra mmar (SVG), specifically tailored to the biological language of DNA. W e here rigorously define and characterize this formalism, showing that it specifies a class of languages that properly contains the context- free languages, but is properly contained in the indexed languages. Pi e give a number of mathematical- and biological examples, and use an S VG variant to propose a new abstraction of the process of gene:express ion. A practical implementation called GENLANG is described, and some recent results in parsing genes and other high-level features of DNA s equences are summarized.