A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
From MaRDI portal
Publication:4441897
DOI10.1137/S0097539702402007zbMath1253.74047DBLPjournals/siamcomp/CrochemoreLZ03OpenAlexW2008803097WikidataQ56813219 ScholiaQ56813219MaRDI QIDQ4441897
Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson
Publication date: 8 January 2004
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702402007
Dynamic programming (90C39) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items (41)
Faster subsequence recognition in compressed strings ⋮ Speeding up transposition-invariant string matching ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ Calculating distances for dissimilar strings: the shortest path formulation revisited ⋮ Parallel comparison of run-length-encoded strings on a linear systolic array ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ An efficient alignment algorithm for masked sequences ⋮ Versatile string kernels ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Fast Algorithms for Computing Tree LCS ⋮ Unified compression-based acceleration of edit-distance computation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Monge properties of sequence alignment ⋮ Sequence Alignment Algorithms for Run-Length-Encoded Strings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient all path score computations on grid graphs ⋮ Fast computation of a longest increasing subsequence and application ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ Textual data compression in computational biology: algorithmic techniques ⋮ Computing similarity of run-length encoded strings with affine gap penalty ⋮ Edit distance with block deletions ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ On almost Monge all scores matrices ⋮ Constrained sequence analysis algorithms in computational biology ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Unnamed Item ⋮ Hardness of comparing two run-length encoded strings ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Fast algorithms for computing tree LCS ⋮ Semi-local longest common subsequences in subquadratic time ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ A faster algorithm for the computation of string convolutions using LZ78 parsing ⋮ Unnamed Item ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets ⋮ Fast distance multiplication of unit-Monge matrices
This page was built for publication: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
