Sequence comparison with concave weighting functions

DOI10.1007/BF02459948zbMath0642.92006OpenAlexW4239178990WikidataQ52579761 ScholiaQ52579761MaRDI QIDQ1101364

Eugene W. Myers, Webb Miller

Publication date: 1988

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

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

zbMATH Keywords

algorithmsconcave functionsequence comparisonbiochemistrydifference metriccandidate list paradigmcomparing long amino sequencesconstructing optimal alignmentsWSB algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational methods for problems pertaining to biology (92-08) Software, source code, etc. for problems pertaining to biology (92-04) Physiological, cellular and medical topics (92Cxx)

Related Items (21)

Determining DNA sequence similarity using maximum independent set algorithms for interval graphs ⋮ Approximate regular expression pattern matching with concave gap penalties ⋮ Set-spectrum method in structure comparison and the concept of topological kinship ⋮ Linear-space algorithms that build local alignments from fragments ⋮ A robust model for finding optimal evolutionary tree ⋮ Approximate matching of regular expressions ⋮ Speeding up dynamic programming with applications to molecular biology ⋮ Minimum message length encoding and the comparison of macromolecules ⋮ Optimal sequence alignment allowing for long gaps ⋮ Consistency of optimal sequence alignments ⋮ Unnamed Item ⋮ On the space complexity of some algorithms for sequence comparison ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ A survey of multiple sequence comparison methods ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ Constrained sequence alignment ⋮ Summation test for gap penalties and strong law of the local alignment score ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions ⋮ Approximate matching between a context-free grammar and a finite-state automaton ⋮ Application of max-plus algebra to biological sequence comparisons

Cites Work

• RNA secondary structures and their prediction
• Algorithms for computing evolutionary similarity measures with length independent gap penalties
• Rapid dynamic programming algorithms for RNA secondary structure
• Some biological sequence metrics
• Algorithms for approximate string matching
• The Least Weight Subsequence Problem
• A linear space algorithm for computing maximal common subsequences

This page was built for publication: Sequence comparison with concave weighting functions