Sequence comparison with concave weighting functions
type: Item
instance of: scholarly article
title: Sequence comparison with concave weighting functions
zbMATH Open document ID: 0642.92006
DOI: 10.1007/BF02459948
author: Webb Miller
author: Eugene W. Myers
published in: Bulletin of Mathematical Biology
publication date: 1988-01-01T00:00:00Z
review text: We consider efficient methods for computing a difference metric between two sequences of symbols, where the cost of an operation to insert or delete a block of symbols is a concave function of the block's length. Alternatively, sequences can be optimally aligned when gap penalties are a concave function of the gap length. Two algorithms based on the `candidate list paradigm' first used by \textit{M. S. Waterman} [J. theor. Biol. 108, 333-337 (1984)] are presented. The first computes significantly more parsimonious candidate lists than Waterman's method. The second method refines the first to the point of guaranteeing \(O(N^ 2lg N)\) worst-case time complexity, and under certain conditions \(O(N^ 2).\) Experimental data show how various properties of the comparison problem affect the methods' relative performance. A number of extensions are discussed, among them a technique for constructing optimal alignments in O(N) space in expectation. This variation gives a practical method for comparing long amino sequences on a small computer.
Mathematics Subject Classification ID: 92Cxx
Mathematics Subject Classification ID: 92-04
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 92-08
zbMATH DE Number: 4047483
zbMATH Keywords: biochemistry
zbMATH Keywords: WSB algorithm
zbMATH Keywords: sequence comparison
zbMATH Keywords: difference metric
zbMATH Keywords: concave function
zbMATH Keywords: algorithms
zbMATH Keywords: candidate list paradigm
zbMATH Keywords: constructing optimal alignments
zbMATH Keywords: comparing long amino sequences
MaRDI profile type: Publication
Wikidata QID: Q52579761
cites work: Algorithms for computing evolutionary similarity measures with length independent gap penalties
cites work: A linear space algorithm for computing maximal common subsequences
cites work: The Least Weight Subsequence Problem
cites work: Algorithms for approximate string matching
cites work: Rapid dynamic programming algorithms for RNA secondary structure
cites work: Some biological sequence metrics
cites work: RNA secondary structures and their prediction
full work available at URL: https://doi.org/10.1007/bf02459948
OpenAlex ID: W4239178990
Recommended article: Sequence comparison with mixed convex and concave costs
Recommended article: Sequence comparison. Theory and methods
Recommended article: AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS
Recommended article: Weighted measures based on maximizing deviation for alignment-free sequence comparison
Recommended article: Approximate Matching in Weighted Sequences
Recommended article: Theoretical Computer Science
Recommended article: A new combinatorial approach to sequence comparison
Recommended article: Bounds for parametric sequence comparison
Recommended article: A multiple sequence comparison method
description: scientific article; zbMATH DE number 4047483