๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal sequence alignment allowing for long gaps

โœ Scribed by Osamu Gotoh

Book ID
104271946
Publisher
Springer
Year
1990
Tongue
English
Weight
735 KB
Volume
52
Category
Article
ISSN
1522-9602

No coin nor oath required. For personal study only.

โœฆ Synopsis

A new algorithm for optimal sequence alignment allowing for long insertions and deletions is developed. The algorithm requires O((L+C)MN) computational steps, O(LN) primary memory and O(MN) secondary memory storage, where M and N (M~> N) are sequence lengths, L (typically L~< 3) is the number of segment specifying the gap weighting function, and C is a constant. We have also modified our earlier traceback algorithm so that it finds all and only the optimal alignments in a compact form of a directed graph. The current versions accept a set of aligned sequences as input, which facilitates multiple sequence alignment by some iterative procedures.

* Dedicated to Professor Akiyoshi Wada on the occasion of his 60th birthday.

๐Ÿ“œ SIMILAR VOLUMES

Normalization of Affine Gap Costs Used i
Normalization of Affine Gap Costs Used in Optimal Sequence Alignment
โœ Lloyd Allison ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 226 KB

It is shown how to normalize the costs of an alignment algorithm that employs affine or linear gap costs. The normalized costs are interpreted as the -log probabilities of the instructions of a finite-state edit-machine. This gives an explicit model relating sequences that can be linked to processes

Fast, Optimal Alignment of Three Sequenc
Fast, Optimal Alignment of Three Sequences Using Linear Gap Costs
โœ DAVID R. POWELL; LLOYD ALLISON; TREVOR I. DIX ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 160 KB

Alignment algorithms can be used to infer a relationship between sequences when the true relationship is unknown. Simple alignment algorithms use a cost function that gives a "xed cost to each possible point mutation\*mismatch, deletion, insertion. These algorithms tend to "nd optimal alignments tha

Generalized affine gap costs for protein
Generalized affine gap costs for protein sequence alignment
โœ Stephen F. Altschul ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 125 KB

Based on the observation that a single mutational event can delete or insert multiple residues, affine gap costs for sequence alignment charge a penalty for the existence of a gap, and a further length-dependent penalty. From structural or multiple alignments of distantly related proteins, it has be