Representing Genetic Information with Formal Grammars

David B. SearlsAAAI 1988

In this seminal 1988 paper, David B. Searls argues that DNA is not merely a linear string of data but a sophisticated language governed by a hierarchical syntax. By applying Definite Clause Grammars (DCGs)—a tool from computational linguistics—Searls demonstrates how to parse, analyze, and even simulate complex genetic processes like splicing and gene regulation.

The Linguistic Approach to DNA

By the late 1980s, the explosion of DNA sequencing data had outpaced the tools available for its analysis. Most methods relied on "linear" logic, such as simple pattern matching or homology searches. However, biology is inherently structural. Features like palindromes, which allow DNA to fold into three-dimensional shapes, and splicing, where non-coding regions are removed, are difficult to describe using the "flat" logic of regular expressions.

Searls proposes moving beyond viewing DNA as a simple list of characters, instead treating it as a formal language with a grammar that can be parsed. This allows a gene to be defined declaratively: gene --> upstream, xscript, downstream. Such abstractions enable researchers to reason about biological function without being overwhelmed by raw nucleotide sequences.

Modeling Biological Complexity

The paper utilizes DCGs implemented in Prolog to extend standard context-free grammars. DCGs offer three critical features for biological modeling:

  1. Parameter Passing: Carrying state information (e.g., amino acid identity) through the parse.
  2. Procedural Attachments: Calling arbitrary code to calculate metrics like informational entropy.
  3. Terminal Replacement: A technique where the parser "consumes" a sequence and replaces it, effectively modeling biological transformations.

One of the most elegant applications is modeling RNA splicing as a linguistic transformation. By treating the removal of an intron as a rule-based replacement, the grammar can connect disparate exons while maintaining the integrity of the reading frames.

Modeling RNA splicing as a linguistic transformation

Results: From Parsing to Simulation

To handle the "imperfect matching" common in real-world biology, Searls suggests reordering searches based on Shannon Entropy. By checking the most informative (least likely) base positions first, the parser can fail faster on incorrect matches, significantly improving efficiency.

Beyond pattern recognition, these grammars can simulate dynamic behavior. Searls developed a grammar modeling a feedback-inhibited promoter, which generates a graph of gene product synthesis based on environmental protein concentrations.

Simulation of gene product synthesis over time

Discussion and Future Work

The implementation of a "chart parser" (using memoization) proved highly efficient, outperforming standard DCG parsing after minimal backtracking. While challenges remain—such as the computational complexity of parsing millions of bases and the need for probabilistic grammars to handle evolutionary variability—this work laid the foundation for viewing biological systems through the lens of formal language theory. Future work could extend these models to populations of molecules, potentially serving as scripts for complex automated experiments.

Summary updated

BibTeX
@inproceedings{searls1988representing,
  author = {David B. Searls},
  title = {{Representing Genetic Information with Formal Grammars}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure