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 scienceAffine transformationSoftwareSpace (punctuation)LimitingSequence (biology)VisibilityLinear spaceTheoretical computer scienceSoftware packageAlgorithmMathematicsProgramming languageBiologyDiscrete mathematicsEngineering
Affiliated Institutions
Related Publications
SAGA: sequence alignment by genetic algorithm
We describe a new approach to multiple sequence alignment using genetic algorithms and an associated software package called SAGA. The method involves evolving a population of a...
Aligning two sequences within a specified diagonal band
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 ...
IQ-TREE: A Fast and Effective Stochastic Algorithm for Estimating Maximum-Likelihood Phylogenies
Large phylogenomics data sets require fast tree inference methods, especially for maximum-likelihood (ML) phylogenies. Fast programs exist, but due to inherent heuristics to fin...
The Multiple Sequence Alignment Problem in Biology
The study and comparison of sequences of characters from a finite alphabet is relevant to various areas of science, notably molecular biology. The measurement of sequence simila...
A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation
Sequence database searches require accurate estimation of the statistical significance of scores. Optimal local sequence alignment scores follow Gumbel distributions, but determ...
Publication Info
- Year
- 1988
- Type
- article
- Volume
- 4
- Issue
- 1
- Pages
- 11-17
- Citations
- 1234
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1234
OpenAlex
Cite This
Eugene W. Myers,
Webb Miller
(1988).
Optimal alignments in linear space.
Computer applications in the biosciences
, 4
(1)
, 11-17.
https://doi.org/10.1093/bioinformatics/4.1.11
Identifiers
- DOI
- 10.1093/bioinformatics/4.1.11