Alain Laferrière, Daniel Gautheret, Robert Cedergren; An RNA pattern matching program with enhanced performance and portability, Bioinformatics, Volume 10,

Abstract This paper presents an application of functional programming: searching a domain for elements which satisfy certain constraints. We give a very general formulation of the problem and describe ‘generate and test’, ‘backtracking’ and ‘forward checking’ algorithms. We then introduce the concept of domain generating functions to capture a common optimization during the search process: using partial solutions to reduce the size of the search space. We compare the efficiency of the original algorithms and those using domain generating functions first with the ‘classical’ n -queens example, and then with a problem having larger domains to search which was inspired by an application in macromolecular structure determination. Using algorithms coded in Miranda, Haskell and Common Lisp, we show that a high order (lazy) functional language is a useful and efficient tool for prototyping search methods in large complex domains.

A convenient pattern-matching program using primary and higher-order structural features has been developed based on a 'backtracking' algorithm. A second implementation of the algorithm uses descriptors of structural features (including primary sequences) to align a list of homologous or highly similar sequences. An application of the pattern matcher to the search for tRNA and group I intron structural motifs in sequence data banks is presented. The design of a highly discriminate tRNA motif, common to all cellular tRNAs and not found in a control sequence bank, was accomplished using the pattern matcher in conjunction with the alignment program.

A major difficulty in the evaluation of secondary and tertiary structures of nucleic acids is the lack of convenient methods for their construction and representation. As a first step in a study of the symbolic representation of biopolymers, we report the development of a structure editor written in Pascal, permitting model construction on the screen of a personal computer. The program calculates energies for helical regions, allows user-defined helices and displays the secondary structure of a nucleic acid based on a user-selected set of helices. Screen and printer outputs can be in the form of a backbone or the letters of the primary sequence. The molecule can then be displayed in a format which simulates its three-dimensional structure. Using appropriate glasses, the molecule can be viewed on the screen in three dimensions. Other options include the manipulation of helices and single-stranded regions which results in changes in the spatial relationship between different regions of the molecule. The editor requires an IBM or compatible PC, 640 kbyte memory and a medium or high resolution graphics card.

In order to study the dynamics of protein and nucleic acid conformations, a molecular folding-unfolding system (FUS written in Lisp) has been developed. Secondary structure features of protein and nucleic acids are graphically represented by cubes in a modified 'Blocks World' paradigm. Modeling of protein and nucleic acid unfolding (denaturation) and folding of their three-dimensional structure is possible by the use of high level 'block' operators which allow displacement of these structural features in space. Due to the flexible nature of this program, FUS is a useful tool for the rapid evaluation of user-defined rules governing conformational changes. The use of FUS to unfold three common proteins (prealbumin, flavodoxin and triose phosphate isomerase) and a tRNA is presented.