An improved algorithm for nucleic acid secondary structure display

An improved algorithm for the display of nucleic acid secondarystructures is presented. It is particularly suitable for largesequence segments and it automatically generates an aestheticallypleasing display of the structure with very limited overlapof strands. Structural similarities in different structuresare conserved in the display thus greatly aiding structuralhomology comparisons. Using the algorithm, we illustrate theeffect of ribosome translocation on the secondary structureof a rat neuropeptide messenger RNA. Received on September 21, 1987; accepted on October 22, 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     

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     

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     

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     

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     

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     

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     

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     

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     

Optimal alignments in linear space

Space, not time, is often the limiting factor when computingoptimal sequence alignments, and a number of recent papers inthe biology literature have proposed space-saving strategies.However, a 1975 computer science paper by Hirschberg presenteda method that is superior to the new proposals, both in theoryand in practice. The goal of this paper is to give Hirschberg'sidea the visibility it deserves by developing a linear-spaceversion of Gotoh's algorithm, which accommodates affine gappenalties. A portable C-software package implementing this algorithmis available on the BIONET free of charge. Received on October 14, 1987; accepted on December 19, 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     

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     

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     

Multiple sequence alignment by a pairwise algorithm

An algorithm is described that processes the results of a conventionalpairwise sequence alignment program to automatically producean unambiguous multiple alignment of many sequences. Unlikeother, more complex, multiple alignment programs, the methoddescribed here is fast enough to be used on almost any multiplesequence alignment problem. Received on September 25, 1986; accepted on January 29, 1987     

A program for template matching of protein sequences

The matching of a template to a protein sequence is simplifiedby treating it as a special case of sequence alignment. Restrictionof the distances between motifs in the template controls againstspurious matches within very long sequences. The program usingthis algorithm is fast enough to be used in scanning large databasesfor sequences matching a complex template. Received on August 17, 1987; accepted on January 11, 1988     

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     

Simultaneous modeling of pharmacokinetics and pharmacodynamics: an improved algorithm

An algorithm and computer program is presented that fits a largelynon-parametric model to pharmacokinetic (PK) and pharmacodynamic(PD) data; it is an extension of a recently proposed approach.A PK model relates dose to plasma concentrations (Cp), a linkmodel relates plasma concentrations to the concentration inthe effect site (C_e), a PD model relates Ce to the effect. Boththe PK and the PD model are non-parametric, but the link modelis parametric. The extension presented here allows modelingof PK/PD data arising from non-steady-state experiments afterarbitrary dosage. In addition, several data sets from the sameindividual (or from different individuals) can now be analyzedsimultaneously, assuming the same link model for all, but allowingeither all the PD models to be the same, or all to be different. Received on March 15, 1987; accepted on July 27, 1987     

A real time learning algorithm for recurrent analog neural networks

A new learning algorithm is described for a general class of recurrent analog neural networks which ultimately settle down to a steady state. Recently, Pineda (Pineda 1987; Almeida 1987; Ikeda et al. 1988) has introduced a learning rule for the recurrent net in which the connection weights are adjusted so that the distance between the stable outputs of the current system and the desired outputs will be maximally decreased. In this method, many cycles are needed in order to get a target system. In each cycle, the recurrent net is run until it reaches a stable state. After that, the weight change is calculated by using a linearized recurrent net which receives the current error of the system as a bias input. In the new algorithm the weights are changed so that the total error of neuron outputs over the entire trajectory is minimized. The weights are adjusted in real time when the network is running. In this method, the trajectory to the target system can be controlled, whereas Pineda's algorithm only controls the position of the fixed point. The relation to the back propagation method (Hinton et al. 1986) is also discussed.     

Algorithms versus models for analyzing data that contain misclassification errors.

Espeland and Hui (1987, Biometrics 43, 1001-1012) propose a methodology for analysing epidemiologic data contaminated by misclassification. They explicate their algorithm by a data set concerning cervical cancer and circumcision. We reanalyse these data using a conditional independence assumption different from theirs, and reach radically different conclusions. Espeland and Hui's methodology is a form of correlation analysis. We propose an alternative methodology based on the logic of regression analysis.