Optimal alignments in linear space
Computer applications in the biosciencesPublished 1 January 1988
Eugene W. Myers, Webb Miller
Citations1,245
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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.
Abstract
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.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Journal of Molecular BiologyAn improved algorithm for matching biological sequences
1,739 Citations1982Osamu Gotoh
The algorithm of Waterman et al. (1976) for matching biological sequences was modified under some limitations to be accomplished in essentially MN steps, instead of the M 2 N steps necessary in the original algorithm.
AlgorithmicaAnO(ND) difference algorithm and its variations
884 Citations1986Eugene W. Myers
A simpleO(ND) time and space algorithm is developed whereN is the sum of the lengths of A andB andD is the size of the minimum edit script forA andB, and the algorithm performs well when differences are small and is consequently fast in typical applications.
Journal of Computer and System SciencesA faster algorithm computing string edit distances
654 Citations1980William Joseph Masek, Michael S. Paterson
An algorithm is described for computing the edit distance between two strings of length n and m, n ⪖ m, which requires O(n · max(1, mlog n) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite.
Information and ControlAlgorithms for approximate string matching
621 Citations1985Esko Ukkonen
An improved algorithm that works in time and in space O and algorithms that can be used in conjunction with extended edit operation sets, including, for example, transposition of adjacent characters.
Advances in MathematicsSome biological sequence metrics
373 Citations1976Michael S. Waterman, Temple F. Smith +1 more
Some new metrics are introduced to measure the distance between biological sequences, such as amino acid sequences or nucleotide sequences, which generalize a metric of Sellers who considered only single deletions, mutations, and insertions.
Journal of Molecular EvolutionComparative biosequence metrics
255 Citations1981Temple F. Smith, Michael S. Waterman +1 more
The sequence alignment algorithms of Needleman and Wunsch (1970) and Sellers (1974) are compared and the two procedures are proven to be equivalent.
Software Practice and ExperienceA file comparison program
187 Citations1985Webb Miller, Eugene W. Myers
A simple method for computing a shortest sequence of insertion and deletion commands that converts one given file to another, which is particularly efficient when the difference between the two files is small compared to the files' lengths.
Bulletin of Mathematical BiologySequence comparison with concave weighting functions
156 Citations1988Webb Miller, Eugene W. Myers
Two algorithms based on the ‘candidate list paradigm’ first used by Waterman (1984) are presented, which computes significantly more parsimonious candidate lists than Waterman's method and a technique for constructing optimal alignments inO(N) space in expectation.
Nucleic Acids ResearchFast optimal alignment
102 Citations1984James W. Fickett
This work shows how to speed up sequence alignment algorithms of the type introduced by Needleman and Wunsch (and generalized by Sellers and others) by reorder the computation of the usual alignment matrix so that the optimal alignment is ordinarily found when only a small fraction of the matrix is filled.
Journal of Theoretical BiologyAlignment of three biological sequences with an efficient traceback procedure
91 Citations1986Osamu Gotoh
This paper describes a dynamic programming algorithm for aligning three sequences at a time that uses an effective technique for memory management, which is applicable to a wide range of sequence-matching methods.
Mathematical BiosciencesA dynamic programming algorithm to find all solutions in a neighborhood of the optimum
74 Citations1985Michael S. Waterman, Thomas Byers
A new technique is described which modifies the usual backtracking procedure and lists all near-optimal policies and is very much in the spirit of the original formulation of dynamic programming.
Nucleic Acids ResearchA fast homology program for aligning biological sequences
59 Citations1984Philip L. Taylor
A procedure for computing the alignment of a pair of sequences of lengths M and N in a single pass of MN steps for both cases of evolutionary distance and optimal path is described.
Computer applications in the biosciencesPattern matching of biological sequences with limited storage
28 Citations1987Osamu Gotoh
An improved method is presented with which the storage requirement is greatly reduced, while the computational steps remain O(N2), and the aligments found are optimal in the sense that their scores are locally maximal.
Computer applications in the biosciencesOptimal alignments of biological sequences on a microcomputer
6 Citations1985Kazutada Watanabe, Yoshio Urano +1 more
An algorithm and a program have been developed which enable optimal alignments of biological sequences on an 8-bit microcomputer.