Sequence comparison with concave weighting functions
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.
- Sequence comparison with mixed convex and concave costs
- Sequence comparison. Theory and methods
- An algorithm and applications to sequence alignment with weighted constraints
- Weighted measures based on maximizing deviation for alignment-free sequence comparison
- Approximate Matching in Weighted Sequences
- Theoretical Computer Science
- A new combinatorial approach to sequence comparison
- Bounds for parametric sequence comparison
- A multiple sequence comparison method
- A linear space algorithm for computing maximal common subsequences
- Algorithms for approximate string matching
- Algorithms for computing evolutionary similarity measures with length independent gap penalties
- Rapid dynamic programming algorithms for RNA secondary structure
- RNA secondary structures and their prediction
- Some biological sequence metrics
- The Least Weight Subsequence Problem
- Locally optimal subalignments using nonlinear similarity functions
- Approximate matching of regular expressions
- Speeding up dynamic programming with applications to molecular biology
- On the space complexity of some algorithms for sequence comparison
- Dynamic programming with convexity, concavity and sparsity
- A survey of multiple sequence comparison methods
- Efficient optimal decomposition of a sequence into disjoint regions, each matched to some template in an inventory
- Identifying periodic occurrences of a template with applications to protein structure
- Constrained sequence alignment
- Reconstructing a history of recombinations from a set of sequences
- Parametric optimization of sequence alignment
- Bounds for parametric sequence comparison
- Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
- Application of max-plus algebra to biological sequence comparisons
- Approximate regular expression pattern matching with concave gap penalties
- Linear-space algorithms that build local alignments from fragments
- A robust model for finding optimal evolutionary tree
- Approximate matching between a context-free grammar and a finite-state automaton
- Set-spectrum method in structure comparison and the concept of topological kinship
- A block recursive sequence alignment algorithm
- scientific article; zbMATH DE number 434724 (Why is no real title available?)
- Sequence comparison with mixed convex and concave costs
- The concave least-weight subsequence problem revisited
- scientific article; zbMATH DE number 1945159 (Why is no real title available?)
- scientific article; zbMATH DE number 742991 (Why is no real title available?)
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- scientific article; zbMATH DE number 232493 (Why is no real title available?)
- Summation test for gap penalties and strong law of the local alignment score
- The Relative Inefficiency of Sequence Weights Approaches in Determining a Nucleotide Position Weight Matrix
- Variable length local decoding and alignment-free sequence comparison
- Tensor ranks and the fine-grained complexity of dynamic programming
- Line geometries for sequence comparisons
- Algorithms for computing evolutionary similarity measures with length independent gap penalties
- An O(NP) sequence comparison algorithm
- Minimum message length encoding and the comparison of macromolecules
- Optimal sequence alignment allowing for long gaps
- Consistency of optimal sequence alignments
This page was built for publication: Sequence comparison with concave weighting functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101364)
