Optimal sequence alignment using affine gap costs

DOI10.1007/BF02462326MaRDI QIDQ1085098zbMATH OpenWikidataFDO

Authors Stephen F. Altschul, Bruce W. Erickson

Publication date 1986

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02462326

zbMATH Keywords

affine gap costsbiochemistrycomparing two biological sequencesoptimal sequence alignmentpath graph

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Physiological, cellular and medical topics (92Cxx)

Review text

When comparing two biological sequences, it is often desirable for a gap to be assigned a cost not directly proportional to its length. If affine gap costs are employed, in other words if opening a gap costs v and each null in the gap costs u, the algorithm of \textit{O. Gotoh} [J. molec, Biol. 162, 705-708 (1982)] finds the minimum cost of aligning two sequences in order MN steps. Gotoh's algorithm attempts to find only one from among possibly many optimal (minimum-cost) alignments, but does not always succeed. This paper provides an example for which this part of Gotoh's algorithm fails and describes an algorithm that finds all and only the optimal alignments. This modification of Gotoh's algorithm still requires order MN steps. A more precise form of path graph than previously used is needed to represent accurately all optimal alignments for affine gap costs.

Recommendations

• Optimal sequence alignment allowing for long gaps
• scientific article; zbMATH DE number 45430
• Alignment between two multiple alignments
• scientific article; zbMATH DE number 434724
• The Multiple Sequence Alignment Problem in Biology

Cites work

• A nonlinear measure of subalignment similarity and its significance levels
• scientific article; zbMATH DE number 3845091 (Why is no real title available?)
• On the Theory and Computation of Evolutionary Distances
• Some biological sequence metrics

Cited in

(14)

• A nonlinear measure of subalignment similarity and its significance levels
• Locally optimal subalignments using nonlinear similarity functions
• The alignment of protein structures in three dimensions
• A survey of multiple sequence comparison methods
• On computing all suboptimal alignments
• Extending alignments with k-mismatches and -gaps
• Adaptation of the method of musical composition for solving the multiple sequence alignment problem
• Sequence comparison with mixed convex and concave costs
• A parallel strategy for biological sequence alignment in restricted memory space
• A path selection approach to global pairwise sequence alignment using integer linear optimization†
• Global pairwise sequence alignment through mixed-integer linear programming: a template-free approach
• Alignment networks and electrical networks
• Optimal sequence alignment allowing for long gaps
• Consistency of optimal sequence alignments

This page was built for publication: Optimal sequence alignment using affine gap costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085098)