A linear space algorithm for computing maximal common subsequences

Cited in

(only showing first 100 items - show all)

Dynamic edit distance table under a general weighted cost function
Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics
Computing a longest common subsequence for a set of strings
Efficient merged longest common subsequence algorithms for similar sequences
scientific article; zbMATH DE number 7765364 (Why is no real title available?)
Constrained LCS: Hardness and Approximation
Faster algorithms for computing longest common increasing subsequences
Space efficient algorithms for ordered tree comparison
FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
A fast algorithm for the longest-common-subsequence problem
The string merging problem
Sequence Alignment Algorithms for Run-Length-Encoded Strings
Identifying periodic occurrences of a template with applications to protein structure
Constrained sequence alignment
Parallel parsing on a one-way linear array of finite-state machines
A learning algorithm for the longest common subsequence problem
Comparing bacterial genomes from linear orders of patterns
Automatic error correction in flexion languages
A diagonal-based algorithm for the longest common increasing subsequence problem
DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
An adaptive multi-policy grid service for biological sequence comparison
Efficient algorithms for finding interleaving relationship between sequences
Longest common subsequence in sublinear space
Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
Polynomial-time equivalences and refined algorithms for longest common subsequence variants
The edit distance to k-subsequence universality
Faster space-efficient STR-IC-LCS computation
One-dimensional approximate point set pattern matching with L_p-norm
A practical semi-external memory method for approximate pattern matching
An overview on XML similarity: background, current trends and future directions
Comparison of strings belonging to the same family
scientific article; zbMATH DE number 7559216 (Why is no real title available?)
Sparse RNA folding: time and space efficient algorithms
Breadth-first heuristic search
Constrained string editing
The set LCS problem
APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
The generalized constrained longest common subsequence in the run-length encoded format
Orphan gene finding -- an exon assembly approach.
Efficient algorithms for enumerating maximal common subsequences of two strings
On measuring similarity for sequences of itemsets
ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
From Regular Expression Matching to Parsing
A linear space algorithm for computing a longest common increasing subsequence
Space-efficient STR-IC-LCS computation
Dynamic programming algorithms for the mosaic longest common subsequence problem
The merged longest common increasing subsequence problem
Weighted LCS
Longest \((k]\)-tuple common substrings
A novel look-ahead optimization strategy for trie-based approximate string matching
An almost-linear time and linear space algorithm for the longest common subsequence problem
The cache complexity of multithreaded cache oblivious algorithms
Calculating distances for dissimilar strings: the shortest path formulation revisited
A new practical linear space algorithm for the longest common subsequence problem
Sequence comparison with concave weighting functions
The intractability of computing the Hamming distance
Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
The longest common subsequence problem revisited
A time-efficient, linar-space local similarity algorithm
Longest bordered and periodic subsequences
Longest common subsequences
Fast linear-space computations of longest common subsequences
A faster linear systolic algorithm for recovering a longest common subsequence
An improved algorithm for computing the edit distance of run-length coded strings
A parallel strategy for biological sequence alignment in restricted memory space
Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
LCSk: a refined similarity measure
Asynchronous communication model based on linear logic
Linear-space S-table algorithms for the longest common subsequence problem
Strategy-proof social choice on multiple and multi-dimensional single-peaked domains
On the generalized constrained longest common subsequence problems
A hyper-heuristic for the longest common subsequence problem
Fast algorithms for computing tree LCS
On computing all suboptimal alignments
On a cyclic string-to-string correction problem
A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
Two applications of the divide \(\&\) conquer principle in the molecular sciences
Finding the gapped longest common subsequence by incremental suffix maximum queries
Dynamic programming with convexity, concavity and sparsity
Fast Algorithms for Computing Tree LCS
The edit distance to \(k\)-subsequence universality
The set-set LCS problem
Data structures and algorithms for approximate string matching
An O(NP) sequence comparison algorithm
A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection
A faster algorithm computing string edit distances
Reconstructing a history of recombinations from a set of sequences
A large neighborhood search heuristic for the longest common subsequence problem
Approximate labelled subtree homeomorphism
An \(O(ND)\) difference algorithm and its variations
A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
Linear-space algorithms that build local alignments from fragments
Matching for run-length encoded strings
From regular expression matching to parsing
An algorithm and applications to sequence alignment with weighted constraints
Absent Subsequences in Words
Shuffle squares and reverse shuffle squares
Simple and fast linear space computation of longest common subsequences
A common basis for similarity measures involving two strings†
Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence

This page was built for publication: A linear space algorithm for computing maximal common subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4055176)