BACKGROUND: The discovery and mapping of genomic variants is an essential step in most analysis done using sequencing reads. There are a number of mature software packages and associated pipelines that can identify single nucleotide polymorphisms (SNPs) with a high degree of concordance. However, the same cannot be said for tools that are used to identify the other types of variants. Indels represent the second most frequent class of variants in the human genome, after single nucleotide polymorphisms. The reliable detection of indels is still a challenging problem, especially for variants that are longer than a few bases. RESULTS: We have developed a set of algorithms and heuristics collectively called indelMINER to identify indels from whole genome resequencing datasets using paired-end reads. indelMINER uses a split-read approach to identify the precise breakpoints for indels of size less than a user specified threshold, and supplements that with a paired-end approach to identify larger variants that are frequently missed with the split-read approach. We use simulated and real datasets to show that an implementation of the algorithm performs favorably when compared to several existing tools. CONCLUSIONS: indelMINER can be used effectively to identify indels in whole-genome resequencing projects. The output is provided in the VCF format along with additional information about the variant, including information about its presence or absence in another sample. The source code and documentation for indelMINER can be freely downloaded from www.bx.psu.edu/miller_lab/indelMINER.tar.gz .

BACKGROUND: Gene clusters are genetically important, but their analysis poses significant computational challenges. One of the major reasons for these difficulties is gene conversion among the duplicated regions of the cluster, which can obscure their true relationships. Many computational methods for detecting gene conversion events have been released, but their performance has not been assessed for wide deployment in evolutionary history studies due to a lack of accurate evaluation methods. RESULTS: We designed a new method that simulates gene cluster evolution, including large-scale events of duplication, deletion, and conversion as well as small mutations. We used this simulation data to evaluate several different programs for detecting gene conversion events. CONCLUSIONS: Our evaluation identifies strengths and weaknesses of several methods for detecting gene conversion, which can contribute to more accurate analysis of gene cluster evolution.

BACKGROUND: The most common application for the next-generation sequencing technologies is resequencing, where short reads from the genome of an individual are aligned to a reference genome sequence for the same species. These mappings can then be used to identify genetic differences among individuals in a population, and perhaps ultimately to explain phenotypic variation. Many algorithms capable of aligning short reads to the reference, and determining differences between them have been reported. Much less has been reported on how to use these technologies to determine genetic differences among individuals of a species for which a reference sequence is not available, which drastically limits the number of species that can easily benefit from these new technologies. RESULTS: We describe a computational pipeline, called DIAL (De novo Identification of Alleles), for identifying single-base substitutions between two closely related genomes without the help of a reference genome. The method works even when the depth of coverage is insufficient for de novo assembly, and it can be extended to determine small insertions/deletions. We evaluate the software's effectiveness using published Roche/454 sequence data from the genome of Dr. James Watson (to detect heterozygous positions) and recent Illumina data from orangutan, in each case comparing our results to those from computational analysis that uses a reference genome assembly. We also illustrate the use of DIAL to identify nucleotide differences among transcriptome sequences. CONCLUSIONS: DIAL can be used for identification of nucleotide differences in species for which no reference sequence is available. Our main motivation is to use this tool to survey the genetic diversity of endangered species as the identified sequence differences can be used to design genotyping arrays to assist in the species' management. The DIAL source code is freely available at http://www.bx.psu.edu/miller_lab/.

UNLABELLED: MicroRNAs (miRNAs) are approximately 20- to 22-nt long endogenous RNA sequences that play a critical role in the regulation of gene expression in eukaryotic genomes. Confident identification of miRNA targets is vital to understand their functions. Currently available computational algorithms for miRNA target prediction have diverse degrees of sensitivity and specificity and as a consequence each predicted target generally requires experimental confirmation. miRNAs and other small RNAs that direct endonucleolytic cleavage of target mRNAs produce diagnostic uncapped, polyadenylated mRNA fragments. Degradome sequencing [also known as PARE (parallel analysis of RNA ends) and GMUCT (genome-wide mapping of uncapped transcripts)] samples the 5'-ends of uncapped mRNAs and can be used to discover in vivo miRNA targets independent of computational predictions. Here, we describe a generalizable computational pipeline, CleaveLand, for the detection of cleaved miRNA targets from degradome data. CleaveLand takes as input degradome sequences, small RNAs and an mRNA database and outputs small RNA targets. CleaveLand can thus be applied to degradome data from any species provided a set of mRNA transcripts and a set of query miRNAs or other small RNAs are available. AVAILABILITY: The code and documentation for CleaveLand is freely available under a GNU license at http://www.bio.psu.edu/people/faculty/Axtell/AxtellLab/Software.html

This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) There is a polynomial-time approximation scheme for planar graphs; (2) there is a polynomial-time $\frac{3}{5}$-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio $\frac{259}{260} + \epsilon$ for graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time $\frac{1}{2}$-approximation algorithm for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region.

The discoveries of microRNAs and riboswitches, among others, have shown functional RNAs to be biologically more important and genomically more prevalent than previously anticipated. We have developed a general comparative genomics method based on phylogenetic stochastic context-free grammars for identifying functional RNAs encoded in the human genome and used it to survey an eight-way genome-wide alignment of the human, chimpanzee, mouse, rat, dog, chicken, zebra-fish, and puffer-fish genomes for deeply conserved functional RNAs. At a loose threshold for acceptance, this search resulted in a set of 48,479 candidate RNA structures. This screen finds a large number of known functional RNAs, including 195 miRNAs, 62 histone 3'UTR stem loops, and various types of known genetic recoding elements. Among the highest-scoring new predictions are 169 new miRNA candidates, as well as new candidate selenocysteine insertion sites, RNA editing hairpins, RNAs involved in transcript auto regulation, and many folds that form singletons or small functional RNA families of completely unknown function. While the rate of false positives in the overall set is difficult to estimate and is likely to be substantial, the results nevertheless provide evidence for many new human functional RNAs and present specific predictions to facilitate their further characterization.

MOTIVATION: The gene expression intensity information conveyed by (EST) Expressed Sequence Tag data can be used to infer important cDNA library properties, such as gene number and expression patterns. However, EST clustering errors, which often lead to greatly inflated estimates of obtained unique genes, have become a major obstacle in the analyses. The EST clustering error structure, the relationship between clustering error and clustering criteria, and possible error correction methods need to be systematically investigated. RESULTS: We identify and quantify two types of EST clustering error, namely, Type I and II in EST clustering using CAP3 assembling program. A Type I error occurs when ESTs from the same gene do not form a cluster whereas a Type II error occurs when ESTs from distinct genes are falsely clustered together. While the Type II error rate is <1.5% for both 5' and 3' EST clustering, the Type I error in the 5' EST case is approximately 10 times higher than the 3' EST case (30% versus 3%). An over-stringent identity rule, e.g., P >/= 95%, may even inflate the Type I error in both cases. We demonstrate that approximately 80% of the Type I error is due to insufficient overlap among sibling ESTs (ISO error) in 5' EST clustering. A novel statistical approach is proposed to correct ISO error to provide more accurate estimates of the true gene cluster profile.

We develop techniques to estimate the statistical significance of gap-free alignments between two genomic DNA sequences, using human-mouse alignments as an example. The sequences are assumed to be sufficiently similar that some but not all of the neutrally evolving regions (i.e., those under no evolutionary constraint) can be reliably aligned. Our goal is to model the situation in which the neutral rate of evolution, and hence the extent of the aligning intervals, varies across the genome. In some cases, this permits the weaker of two matches to be judged as less likely to have arisen by chance, provided it lies in a genomic interval with a high level of background divergence. We employ a Hidden Markov Model to capture variations in divergence rates, and assign probability values to gap-free alignments using techniques related to those used for the same purpose by Blast. Our methods are illustrated in detail using a 1.49 Mb genomic region. Preliminary results using all of human chromosome 22 indicate that these techniques will work for the entire human genome.

MOTIVATION: The DNA sequences of entire genomes are being determined at a rapid rate. Whereas initial genome sequencing efforts were for organisms chosen to be widely spaced in the tree of life, there is a growing emphasis on projects to sequence a species that is sufficiently similar to an already-sequenced species to allow direct comparison of those two DNA sequences. This and other changes in genome sequencing strategies have created a strong need for new methods to compare genomic sequences. RESULTS: We sketch the current state of software for comparing genomic DNA sequences and outline research directions that we believe are likely to result in important advances in practice.

An important computational technique for extracting the wealth of information hidden in human genomic sequence data is to compare the sequence with that from the corresponding region of the mouse genome, looking for segments that are conserved over evolutionary time. Moreover, the approach generalises to comparison of sequences from any two related species. The underlying rationale (which is abundantly confirmed by observation) is that a random mutation in a functional region is usually deleterious to the organism, and hence unlikely to become fixed in the population, whereas mutations in a non-functional region are free to accumulate over time. The potential value of this approach is so attractive that the public and private projects to sequence the human genome are now turning to sequencing the mouse, and you will soon be able to compare the human and mouse sequences of your favourite genomic region. We are currently witnessing an explosion of computer tools for comparative analysis of two genomic sequences. Here the capabilities of two new network servers for comparing genomic sequences from any pair of closely related species are sketched. The Syntenic Gene Prediction Program SGP-I utilises sequence comparisons to enhance the ability to locate protein coding segments in genomic data. PipMaker attempts to determine all conserved genomic regions, regardless of their function.

In database searches for sequence similarity, matches to a distinct sequence region (e.g. protein domain) are frequently obscured by numerous matches to another region of the same sequence.In order to cope with this problem, algorithms are developed to discard redundant matches.One model for this problem begins with a list of intervals, each with an associated score; each interval gives the range of positions in the query sequence that align to a database sequence, and the score is that of the alignment.If interval I is contained in interval J, and I's score is less than J's, then I is said to be dominated by J.The problem is then to identify each interval that is dominated by at least K other intervals, where K is a given level of "tolerable redundancy."An algorithm is developed to solve the problem in O(N log N) time and O(N*) space, where N is the number of intervals and N' is a precisely defined value that never exceeds N and is frequently much smaller.This criterion for discarding database hits has been implemented in the Blast program, as illustrated herein with examples.Several variations and extensions of this approach are also described.

MOTIVATION: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. RESULTS: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.

Given a strong match be%een regions of txvo sequences, horn far can the match be meaningfully extended if gaps are all04 in the resdtinrc aknment?The aim is to aviod sear&ix bwond the point th\t asuseful extension of the a&mm& is l&ly to be found.Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem.Given two sequences and a fixed X > 0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X.Our results indicate that computing an optimal alignment under this constraint is very expensive.However, less rigorous conditions on the alignment can be guaranked by quite eiiicient algorithms.One of these variants has been implemented in a new release of the Blast suite of database search programs.a b C Figure 1: Graph model of a simple alignment problem.Dark edges (corresponding to aligning identical letters) score 1, and all other edges score -1.

A progressive alignment algorithm produces a multi-alignment of a set of sequences by repeatedly aligning pairs of sequences and/or previously generated alignments. We describe a method for guaranteeing that the alignment generated by a progressive alignment strategy satisfies a user-specified collection of constraints about where certain sequence positions should appear relative to others. Given a collection of C constraints over K sequences whose total length is N , our algorithm takes O(K(N 2 +KC)) time. An alignment of the fi-like globin gene clusters of several mammals illustrates the practicality of the method. Key words: Multiplesequence alignment, constrained alignment, dynamic programming 1 Introduction It is straightforward to extend the dynamic programming alignment algorithm (Needleman and Wunsch 1970) to the simultaneous alignment of K ? 2 sequences. However, the O(2 K N K ) execution time for sequences of length N makes it impractical to align more than three seque...

We develop several algorithms for the problem of aligning a DNA sequence with a protein sequence.Our methods account for frameshift errors, but not for introns in the DNA sequence.Thus, they are particularly appropriate for comparing a cDNA sequence that contains sequencing errors with an amino acid sequence or a protein sequence database.We describe techniques for efficient implementation, verify sufficient conditions for equivalenceof several definitions of alignment, and discuss experience with these ideas in a new release of the fasta suite of database-searching programs.

Results: We have produced a computer program, named sim3, that solves the following computational problem. Two DNA sequences are given, where the shorter sequence is very similar to some contiguous region of the longer sequence. Sim3 determines such a similar region of the longer sequence, and then computes an optimal set of single-nucleotide changes (i.e. insertions, deletions or substitutions) that will convert the shorter sequence to that region. Thus, the alignment scoring scheme is designed to model sequencing errors, rather than evolutionary processes. The program can align a 100 kb sequence to a 1 megabase sequence in a few seconds on a workstation, provided that there are very few differences between the shorter sequence and some region in the longer sequence. The program has been used to assemble sequence data for the Genomes Division at the National Center for Biotechnology Information. Availability: A version of sim3 for UNIX machines can be obtained by anonymous ftp from ncbi. nlm. nih. gov, in the pub/sim3 directory. Contact: For portable versions for Macs and PCs, contact zjing@sunset. nlm. nih. gov.

This paper presents a practical program, called sim2, for building local alignments of two sequences, each of which may be hundreds of kilobases long. sim2 first constructs n best non-intersecting chains of 'fragments', such as all occurrences of identical 5-tuples in each of two DNA sequences, for any specified n > or = 1. Each chain is then refined by delivering an optimal alignment in a region delimited by the chain. sim2 requires only space proportional to the size of the input sequences and the output alignments, and the same source code runs on Unix machines, on Macintoshes, on PCs, and on DEC Alpha PCs. We also describe an application of sim2 for aligning long DNA sequences from Escherichia coli. sim2 facilitates contig-building by providing a complete view of the related sequences, so differences can be analyzed and inconsistencies resolved. Examples are shown using the alignment display and editing functions from the software tool ChromoScope.

A recent paper in this journal by G. Barton proposed an efficient algorithm for locating locally optimal alignments between two sequences. Although the paper claims that all such alignments are found, the approach frequently fails to detect some of the significant matches. This note explains the deficiency.

Within a single alignment of two DNA sequences or two protein sequences, some regions may be much better conserved than others. Such strong conservation may reveal a region that possesses an important function. When alignments are so long that it is infeasible, or at least undesirable, to inspect them in complete detail, it is helpful to have an automatic process that computes information about the varying degree of conservation along the alignment and displays the information in a graphical representation that is readily assimilated. This paper presents methods for computing several such 'robustness measures' at each position of a given alignment. These methods are all very space-efficient; they use only space proportional to the sum of the two sequence lengths. To illustrate their effectiveness, one of the methods is used to locate particularly well-conserved regions in the beta-globin gene locus control region and in the 5' flank of the gamma-globin gene.

Given a family of related sequences, one can first determine alignments between various pairs of those sequences, then construct a simultaneous alignment of all the sequences that is determined in a natural manner by the set of pairwise alignments. This approach is sometimes effective for exposing the existence and locations of conserved regions, which can then be aligned by more sensitive multiple-alignment methods. This paper presents an efficient algorithm for constructing a multiple alignment from a set of pairwise alignments.

We describe an algorithm for aligning two sequences within a diagonal band that requires only O(NW) computation time and O(N) space, where N is the length of the shorter of the two sequences and W is the width of the band. The basic algorithm can be used to calculate either local or global alignment scores. Local alignments are produced by finding the beginning and end of a best local alignment in the band, and then applying the global alignment algorithm between those points. This algorithm has been incorporated into the FASTA program package, where it has decreased the amount of memory required to calculate local alignments from O(NW) to O(N) and decreased the time required to calculate optimized scores for every sequence in a protein sequence database by 40%. On computers with limited memory, such as the IBM-PC, this improvement both allows longer sequences to be aligned and allows optimization within wider bands, which can include longer gaps.

The local similarity problem is to determine the similar regions within two given sequences. We recently developed a dynamic programming algorithm for the local similarity problem that requires only space proportional to the sum of the two sequence lengths, whereas earlier methods use space proportional to the product of the lengths. In this paper, we describe how to parallelize the new algorithm and present results of experimental studies on an Intel hypercube. The parallel method provides rapid, high-resolution alignments for users of our software toolkit for pairwise sequence comparison, as illustrated here by a comparison of the chloroplast genomes of tobacco and liverwort.

We present algorithms for searching a DNA restriction enzyme map for a region that best matches a shorter 'probe' map. Our algorithms utilize a new model of map alignments, and extensive experiments prove our model superior to earlier approaches for certain applications. Let M be the number of map sites and P be the number of probe sites. Our first algorithm, which optimizes only over a restricted class of alignments, requires O(MP log P) worst-case time and O(M + P) space. Our second algorithm, which optimizes over all alignments, runs in O(MP3) time and O(M + P2) space, under reasonable assumptions about the distribution of restriction enzyme cleavage sites. Combining the algorithms gives a map-searching method that optimizes over all alignments in O(MP log P) time in practice. The algorithms' effectiveness is illustrated by searches involving a genomic restriction map of Escherichia coli.

Existing dynamic-programming algorithms for identifying similar regions of two sequences require time and space proportional to the product of the sequence lengths. Often this space requirement is more limiting than the time requirement. We describe a dynamic-programming local-similarity algorithm that needs only space proportional to the sum of the sequence lengths. The method can also find repeats within a single long sequence. To illustrate the algorithm's potential, we discuss comparison of a 73,360 nucleotide sequence containing the human beta-like globin gene cluster and a corresponding 44,594 nucleotide sequence for rabbit, a problem well beyond the capabilities of other dynamic-programming software.

This paper presents an algorithm that searches a DNA restriction enzyme map for regions that approximately match a shorter 'probe' map. Both the map and the probe consist of a sequence of address-enzyme pairs denoting restriction sites, and the algorithm penalizes a potential match for undetected or missing sites and for discrepancies in the distance between adjacent sites. The algorithm was designed specifically for comparing relatively short DNA sequences with a long restriction map, a problem that will become increasing common as large physical maps are generated. The algorithm has been used to extract information from a restriction map of the entire Escherichia coli genome.

Interactive screen editors repeatedly determine terminal command sequences to update a screen row. Computing an optimal command sequence differs from the traditional sequence comparison problem in that there is a cost for moving the cursor over unedited characters and the cost of an n -character command is not always the cost of n one-character commands. For example, on an ANSI-standard terminal, it takes nine bytes to insert one character, ten to insert two, eleven to insert three, and so on. This paper presents an O ( MN ) dynamic programming algorithm for row replacement where an n -character command costs α n + β for constants α and β. M is the length of the original row and N is the length of its replacement. Also given is an O ( Cost × ( M + N )) “greedy” algorithm for optimal row replacement. Here Cost is the optimal cost (in bytes) of the replacement, so the algorithm is fast when the require d update is small. Though the algorithm is rather complicated, it is fast enough to be useful in practice.

Space, not time, is often the limiting factor when computing optimal sequence alignments, and a number of recent papers in the biology literature have proposed space-saving strategies. However, a 1975 computer science paper by Hirschberg presented a method that is superior to the new proposals, both in theory and in practice. The goal of this paper is to give Hirschberg's idea the visibility it deserves by developing a linear-space version of Gotoh's algorithm, which accommodates affine gap penalties. A portable C-software package implementing this algorithm is available on the BIONET free of charge.

Abstract Updating a video screen involves row replacement, i.e, the task of updating an existing screen row to produce the desired row. In many environments, screen operations require transmitting characters to the terminal by a process that is painfully slow compared to computing speeds. Thus, it is worth while to compute a minimal set of row updating commands, as long as the time to do so does not outweigh the savings in character transmission time. This paper presents a simple and practical algorithm for optimal row replacement and describes experience with its use in a screen editor.

Abstract This paper presents a simple method for computing a shortest sequence of insertion and deletion commands that converts one given file to another. The method is particularly efficient when the difference between the two files is small compared to the files' lengths. In experiments performed on typical files, the program often ran four times faster than the UNIX diff command.

The graph-theoretical models of this paper can be used to compare the rounding error behavior of numerical programs The models follow the approach, popularized by Wilkinson, of assuming independent rounding errors at each arithmetic operation Models constructed on th~s assumpuon are more tractable than would be the case under more realistic assumptions There are identified two easily tested condmons on programs which guarantee that" error analyses are relatively lnsensmve to the particular graph model employed The development has the addmonal benefit of sometimes providing an elementary proof that one program is comparable in stablhty to another Examples of such results are gwen KEY WORDS AND PHRASES rounding errors, numerical stability, arithmetic graphs CR CATEGORIES 5 11, 5 14In order to represent programs as "arithmetic graphs," we restrict attention to straight-

Many roundoff analyses of nomteratlve methods from numerical linear algebra can be performed, at least in part, using off-the-shelf software.Such software is presented here and its use is illustrated with examples.The package presented differs from Its predecessor in four important respects.First, a mmicompfler allows easy specIficatmn of the algorithm being tested.Second, the package can test the simultaneous effect of rounding error upon several values.Third, it deals with branching in numerical methods, e.g. with pivoting in Gaussian elimination.Fourth, m addition to comparing rounding error with perturbations of the problem, it can directly compare rounding errors in two competing algorithms Key Words and Phrases automatic roundoff analysis, numerical stability, numerical hnear algebra CR Categories 5 10, 5 11, 5 14 The Algorithm Software for Roundoff Analysis.

article Artifacts Evaluated & ReusableArtifacts AvailableAlgorithm 532: software for roundoff analysis [Z] Share on Authors: Webb Miller Department of Mathematics, University of California, Santa Barbara, Santa Barbara, CA Department of Mathematics, University of California, Santa Barbara, Santa Barbara, CAView Profile , David Spooner Department of Computer Science, 303 Whitmore Laboratory, Pennsylvania State University, University Park, PA Department of Computer Science, 303 Whitmore Laboratory, Pennsylvania State University, University Park, PAView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 4Issue 4December 1978 pp 388–390https://doi.org/10.1145/356502.356497Online:01 December 1978Publication History 5citation222DownloadsMetricsTotal Citations5Total Downloads222Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

When analyzing a numerical algorithm, it is often possible to show that a rounding error at one floating-point operation is equivalent to errors at other operations. In such cases, it can be concluded that no generality is lost if certain operations are considered error-free. Sometimes this conclusion can be reached automatically and inexpensively compared to the cost of the ultimate roundoff analysis. It may be advantageous to use a preprocessor which performs this reduction before other automatic techniques are invoked. In this report we consider a class of elementary rounding error reductions which are most naturally interpreted as graph transformations. This leads to questions concerning heuristics and optimal strategies for the application of these transformations.

For numerical programs, or more generally for programs with floating-point data, it may be that large savings of time and storage are made possible by using numerical maximization methods instead of symbolic execution to generate test data. Two examples, a matrix factorization subroutine and a sorting method, illustrate the types of data generation problems that can be successfully treated with such maximization techniques.

The Pennsylvania State Un~verslty,

Limiting consideration to algorithms satisfying various numerical stability requirements may change lower bounds for computational complexity and/or make lower bounds easier to prove. We will show that under a sufficiently strong restriction upon numerical stability, any algorithm for multiplying two $n \times n$ matrices using only $+,\, - $ and $ \times $ requires at least $n^3 $ multiplications. We conclude with a survey of results concerning the numerical stability of several algorithms which have been considered by complexity theorists.

Fortran programs for locating numerical instabihties in algebraic processes are given.They easily diagnose known instabilities in certain versions of the QR algorithm and the Gram-Schmidt method.To analyze a given numerical algorithm we proceed as follows.A number which measures the effect of roundoff error is assigned to each set of data."Hill-climbing" procedures are then applied to search for values large enough to signal instability.

Limiting consideration to algorithms satisfying various numerical stability requirements may change lower bounds for computational complexity and/or make lower bounds easier to prove. We will show that, under a sufficiently strong restriction upon numerical stability, any algorithm for multiplying two n×n matrices using only +, − and × requires at least n3 multiplications. We conclude with a survey of results concerning the numerical stability of several algorithms which have been considered by complexity theorists.

In this paper we will be concerned with portions of roundoff analysis which can be automated. Conditions are given under which proofs of numerical stability can be performed completely automatically and very economically (in particular, in polynomial time). We also discuss the use of “numerical heuristics” which apply “hill-climbing” methods to functionals measuring contamination from roundoff.

This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function theory have been avoided. Instead, the number of necessary function evaluations is taken as the measure of computational complexity. The role of topological concepts in the study of computability is examined. Last, a topological result is used to prove that a simple initial-value problem is numerically unsolvable.