A software tool for finding locally optimal alignments in protein and nucleic acid sequences

We describe software for aligning protein or nucleic acid sequencesbased on the concept of match density. This method is especiallyuseful for locating regions of short similarity between twolonger sequences which may be largely dissimilar (e.g. locatingactive site regions in distantly related proteins). Our softwareis able to identify biologically interesting similarities betweentwo sub-regions because it allows the user to control the matchingparameters and the manner in which local alignments are selectedfor display. Furthermore, the collection and ranking of alignmentsfor display uses a novel, highly efficient algorithm. We illustratethese features with several examples. In addition, we show thatthis tool can be used to find a new conserved sequence in severalviral DNA polymerases, which, we suggest, occurs at a functionallyimportant enzymatic site. Received on August 17, 1987; accepted on November 17, 1987     

Graphics of RNA secondary structure; towards an object-oriented algorithm

We present a new algorithm for the display of RNA secondarystructure. The principle of the algorithm is entirely differentfrom those currently in use in that our algorithm is ‘objectoriented’ while currrent algorithms are ‘procedural’.The circular RNA molecule of chrysanthemum stunt viroid wasused as input data for demonstrating the operation of the program.The major interest of this method will be found in its potentialuse in simulation graphics of RNA folding processes. Received on October 9, 1986; accepted on February 17, 1987     

A modified Chou and Fasman protein structure algorithm

A FORTRAN program PRSTRC has been developed for protein secondarystructure prediction, which is a modified Chou and Fasman (1978)analysis. This implementation carries out a running averageof amino acid structure occurrence frequencies, utilizes a simpleset of nucleation conditions, and allows user control over nucleationthreshold and cutoff parameters. The algorithm includes predictionof the newly defined secondary structure elements: omega loops(1986). It also generates a charge distribution and hydropathyprofile. Output includes a simple graphic display for a printer,or a CRT using color addition. Correct structures are predictedfor T. dyscritum hemerythrin and the variable domain of mouseimmunoglobin k-chain. Received on November 17, 1986; accepted on June 10, 1987     

A computer algorithm to determine the recognition site of restriction enzymes

A new algorithm is proposed to determine the type-II restrictionendonucleases' recognition site knowing the digested DNA sequenceand fragment lengths in an actual case. The algorithm is implementedfor the Commodore 64 microcomputer. Received on January 6, 1987; accepted on June 19, 1987     

AUGUR: a program to predict, display and analyze the tertiary structure of B-DNA

A UGUR is a program to predict, display and analyze the three-dimensionalstructure of B-DNA. The user can choose one of six models topredict the helical parameters of a given sequence. These parametersare then used to generate the coordinates of the DNA model inthree-dimensional space (trajectory). The trajectory can bedisplayed and rotated on a graphics terminal The trajectoryand helical parameters can also be searched for bends and structuralhomologues. Received on August 17, 1987; accepted on December 31, 1987     

PARA-SITE: a computer algorithm for rapidly analyzing the physical-chemical properties of amino acid sequences at sites of co- and post-translational protein processing

A new algorithm is presented which can be used to examine thephysical-chemical properties of amino acids at sites of co-orpost-translational processing. This algorithm has been incorporatedinto a computer program known as PARA-SITE. Thirty differentparameters can be studied for amino acids which occupy comparablepositions in naturally occurring proteins. PARA-SITE shouldaid in the design and interpretation of protein engineeringexperiments which seek to dissect structure/ activity relationships. Received on August 17, 1987; accepted on November 23, 1987     

Reiterative RNA folding and occupancy rate analysis for mRNA modelling

We describe computer programs that predict the most energeticallyfavorable secondary structures in growing RNA sequences, generatea sequential display of the growing structures, and monitorthe predicted participation of intramolecular sites in secondarystructure. These programs may provide insight into the relationshipsbetween messenger RNA secondary structure and expressibility. Received on August 10, 1987; accepted on October 17, 1987     

A hidden-line algorithm for graphical reconstruction of serially sectioned objects

An algorithm for hidden-line removal in graphical reconstructionsof serially sectioned biological objects is developed for PC-likecomputer configurations. The aim is to handle complicated structuresdefined by vast numbers of coordinate pairs and intersectionsbetween contours, without requiring excessive computing time.The procedure depends upon a fast searching routine for thelocalization of intersections and visibility. Received on September 8, 1987; accepted on December 21, 1987     

Turbo Tree: a fast algorithm for minimal trees

A branch and bound algorithm is described for searching rapidlyfor minimal length trees from biological data. The algorithmadds characters one at a time, rather than adding taxa, as inprevious branch and bound methods. The algorithm has been programmedand is available from the authors. A worked example is givenwith 33 characters and 15 taxa. About 8 x 10¹² binary treesare possible with 15 taxa but the branch and bound program findsthe minimal tree in <5 min on an IBM PC. Received on January 15, 1987; accepted on February 23, 1987     

An algorithm for discriminating sequences and its application to yeast transfer RNA

We describe an algorithm for finding nucleotide residues stronglycorrelated with the amino acid acceptor functions of transferRNAs. The algorithm exploits the fact that each tRNA acceptsonly one of 20 amino acids. The algorithm is applied to 37 Saccharomycescerevisiae transfer RNAs. Received on January 28, 1987     

An algorithm for simultaneous comparison of several sequences

An algorithm was developed to compare simultaneously severalDNA, RNA or protein sequences. With the algorithm, conservedregions of one sequence are located by doing pairwise comparisonswith other sequences, which is advantageous in planning site-directedmutagenesis studies. The observation matrices filled with scoresof comparisons are superimposed and added together and thosepoints having values greater than or equal to stringency areaccepted. The predicted secondary structural features can alsobe compared. Received on August 21, 1987; accepted on November 20, 1987     

Restriction site mapping is in separation theory

A computer algorithm for restriction-site mapping consists ofa generator of partial maps and a consistency checker. Thispaper examines consistency checking and argues that a methodbased on separation theory extracts the maximum amount of informationfrom fragment lengths in digest data. It results in the minimumnumber of false maps being generated. Received on July 17, 1987; accepted on December 13, 1987     

A computer program to display codon changes caused by mutagenesis

A FORTRAN program for displaying the correspondence betweencodon changes and different possible base changes is presented.Changes of both single bases and dimers are considered. Theuser can specify the mutagenesis spectrum. Additionally, theuser can choose whether or not to consider single or doubleevents in a codon and whether or not to consider the possibilitythat the change of two bases (a dimer) can overlap a codon boundary.Furthermore, a variety of ways may be chosen to display andsummarize the codon changes that can result from the specifiedmutagenesis. A user-supplied sequence or the genetic code tablecan be analyzed. Received on January 27, 1987; accepted on September 4, 1987     

Microcomputer-based three-dimensional stereoscopic macromolecular graphics display

Software which permits an IBM AT and two IBM Professional GraphicsDisplays to be used to display high-quality three-dimensionalspace-filling stereoscopic images of macromol-ecules is described.Stereo image pairs generated on two screens are visually fusedusing a simple mirror system to provide binocular depth perception.Images are colored to identify atomic type, residue type, chargeor hydrophobicity according to user-specified codes and canbe rotated and rescaled. Macro-molecules containing over 16000 atoms can be rapidly drawn using Brookhaven Protein DataBank or user-supplied coordinates. Received on August 7, 1987; accepted on October 21, 1987     

Errors between sites in restriction site mapping

Restriction site mapping programs construct maps by generatingpermutations of fragments and checking for consistency. Unfortunatelymany consistent maps often are obtained within the experimentalerror bounds, even though there is only one actual map. A particularlyefficient algorithm is presented that aims to minimize errorbounds between restriction sites. The method is generalizedfor linear and circular maps. The time complexity is derivedand execution times are given for multiple enzymes and a rangeof error bounds. Received on July 17, 1987; accepted on November 3, 1987     

Construction of restriction maps

A computer program is described, which constructs maps of restrictionendonuclease cleavage sites in linear or circular DNA molecules,given the fragment lengths in single and double digestions withtwo enzymes. The algorithm is based upon a partition methodand a very simple rule to chain fragments. The program is writtenin Prolog II. Received on July 28, 1987; accepted on December 31, 1987     

Locating alignments with k differences for nucleotide and amino acid sequences

Given two sequences, a pattern of length m, a text of lengthn and a positive integer k, we give two algorithms. The firstfinds all occurrences of the pattern in the text as long asthese do not differ from each other by more than k differences.It runs in O(nk) time. The second algorithm finds all subsequencealignments between the pattern and the test with at most k differences.This algorithm runs in O(nmk) time, is very simple and easyto program. Received on August 12, 1987; accepted on December 31, 1987     

Two computer programs for rapid entry of DNA sequence data

Two computer programs for the IBM personal computer are describedfor rapid and accurate entry of DNA sequence data. The DNA sequencefiles produced can be used directly by the DNA sequence manipulationprograms by R. Staden (the DataBase system), the Universityof Wisconsin Genetics Computer Group, DNASTAR, or D. Mount.The first program, DIGISEQ, utilizes a sonic digitizer for semi-automationof sequence entry. To enter the DNA sequence each band of agel reading is touched by the stylus of the sonic digitizer.DIGISEQ corrects for both changes in lane width and lane curvature.The algorithm is extremely efficient and rarely requires re-entenngthe centers of the lanes. The second program, TYPESEQ, usesonly the keyboard for input. The keyboard is reconfigured toplace nucleotides and ambiguity codes under the fingers of onehand, corresponding to the order of the nucleotides on the geldefined by the user Both programs produce individual tones foreach nucleotide, and certain ambiguity codes. This verifiesinput of the correct nucleotide or ambiguity code, and thuseliminates the need to visually check the screen display duringsequence entry. Received on November 16, 1986; accepted on June 16, 1987     

Restriction map construction using a 'complete sentences compatibility' algorithm

We have developed a new algorithm ‘Complete sentencescompatibility’ (CSC) which uses single and double digestionfragments to rapidly determine restriction maps of circularDNA. From possible combinations of fragments of each simpledigestion, which we call ‘sentences of decomposition’,we construct a restriction map which combines the sentenceswhile taking into account compatibility rules. The algorithmcan also deal with experimental errors of fragment weight andcan suggest solutions that account for non-readable bands (fragmentsof zero length or multiple bands) on the gel. Because experimentsusing pairs of restrictive enzymes often result in multiplesolutions, a complementary algorithm tries to reduce the numberof proposed solutions by establishing consensus maps. The restrictionmap construction algorithm was tested on real cases, some containingmore than fifteen fragments. Execution times range from 1 –10 s on an IBM PC compatible microcomputer. Received on July 21, 1987; accepted on December 31, 1987     

The antigenic index: a novel algorithm for predicting antigenic determinants

In this paper, we introduce a computer algorithm which can beused to predict the topological features of a protein directlyfrom its primary amino acid sequence. The computer program generatesvalues for surface accessibility parameters and combines thesevalues with those obtained for regional backbone flexibilityand predicted secondary structure. The output of this algorithm,the antigenic index, is used to create a linear surface contourprofile of the protein. Because most, if not all, antigenicsites are located within surface exposed regions of a protein,the program offers a reliable means of predicting potentialantigenic determinants. We have tested the ability of this programto generate accurate surface contour profiles and predict antigenicsites from the linear amino acid sequences of well-characterizedproteins and found a strong correlation between the predictionsof the antigenic index and known structural and biological data. Received on August 17, 1987; accepted on December 31, 1987