A linear space algorithm for computing maximal common subsequences

Cited in

(only showing first 100 items - show all)

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
Efficient algorithms for regular expression constrained sequence alignment
Performance analysis of some simple heuristics for computing longest common subsequences
Multi-sided boundary labeling
Exact algorithms for the repetition-bounded longest common subsequence problem
Optimality regions and fluctuations for Bernoulli last passage models
Formal timing analysis for distributed real-time programs
A fast and practical bit-vector algorithm for the longest common subsequence problem
New algorithms for the LCS problem
RNA multiple structural alignment with longest common subsequences
A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
An efficient algorithm for LCS problem between two arbitrary sequences
On finding longest palindromic subsequences using longest common subsequences
An information-theoretic lower bound for the longest common subsequence problem
Longest double-bounded \((k]\)-tuple common substrings
An improved algorithm for the longest common subsequence problem
Using Hirschberg's algorithm to generate random alignments of strings
An all-substrings common subsequence algorithm
Multi-subsequence searching
A fully compressed algorithm for computing the edit distance of run-length encoded strings
Finding many optimal paths without growing any optimal path trees
On the space complexity of some algorithms for sequence comparison
Minimum message length encoding and the comparison of macromolecules
A space-efficient algorithm for longest common almost increasing subsequence of two sequences
Hardness and approximation of the asynchronous border minimization problem
Table design in dynamic programming
New Error Tolerant Method for Search of Long Repeats in DNA Sequences
The generalized definitions of the two-dimensional largest common substructure problems
Sparse RNA Folding: Time and Space Efficient Algorithms
On the inadequacy of tournament algorithms for the N-SCS problem

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)