No label defined (Q4246782)

The author has for some time been investigating the application of formal language theory to biological macromolecules, primarily nucleic acids because of the relative simplicity of the biochemical structures and interactions. The motivation for this effort was the observation that, while describing and recognizing patterns in sequence data is a key task in biology, this has mainly been done with tools of limited expressive power, such as regular expression search programs, and without regard to well-understood formal underpinnings of computational linguistics. In attempting to characterize the range of phenomena that need to be captured in biological sequences, it was discovered that the tools and techniques of formal language theory offered surprising insights into the structure and behavior of these molecules. After introducing the very simple mathematical foundations for these investigations, this article will review three major lines of research. These can largely be found in more fully developed form in referenced publications, though some new material is also included in each case. The sections below will deal with the use of formal grammars to describe intramolecular interactions, a new class of grammars designed to encompass intermolecular interactions in assemblages of macromolecules, and automata-theoretic approaches to the alignment of lexical strings, and thus their evolutionary structure with respect to each other. For the entire collection see [Zbl 0912.00016].