A linear space algorithm for computing maximal common subsequences
From MaRDI portal
Publication:4055176
DOI10.1145/360825.360861zbMath0301.68042OpenAlexW2165654401WikidataQ55891301 ScholiaQ55891301MaRDI QIDQ4055176
Publication date: 1975
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/360825.360861
Related Items (only showing first 100 items - show all)
DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM ⋮ Longest common subsequences ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Absent Subsequences in Words ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Longest bordered and periodic subsequences ⋮ Space-efficient STR-IC-LCS computation ⋮ Shuffle squares and reverse shuffle squares ⋮ Unnamed Item ⋮ ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS ⋮ Weighted LCS ⋮ FINDING MANY OPTIMAL PATHS WITHOUT GROWING ANY OPTIMAL PATH TREES ⋮ AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS ⋮ Unnamed Item ⋮ A learning algorithm for the longest common subsequence problem ⋮ From Regular Expression Matching to Parsing ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ A common basis for similarity measures involving two strings† ⋮ Formal timing analysis for distributed real-time programs ⋮ Using Hirschberg's algorithm to generate random alignments of strings ⋮ Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings ⋮ Performance analysis of some simple heuristics for computing longest common subsequences ⋮ A faster linear systolic algorithm for recovering a longest common subsequence ⋮ LCS\(k\): a refined similarity measure ⋮ A linear space algorithm for computing a longest common increasing subsequence ⋮ Dynamic programming algorithms for the mosaic longest common subsequence problem ⋮ Efficient algorithms for regular expression constrained sequence alignment ⋮ Efficient algorithms for finding interleaving relationship between sequences ⋮ The longest common subsequence problem revisited ⋮ Constrained string editing ⋮ An \(O(ND)\) difference algorithm and its variations ⋮ Asynchronous communication model based on linear logic ⋮ The set LCS problem ⋮ Sequence comparison with concave weighting functions ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ RNA multiple structural alignment with longest common subsequences ⋮ Data structures and algorithms for approximate string matching ⋮ Linear-space algorithms that build local alignments from fragments ⋮ Calculating distances for dissimilar strings: the shortest path formulation revisited ⋮ Multi-sided boundary labeling ⋮ A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection ⋮ Two applications of the divide \(\&\) conquer principle in the molecular sciences ⋮ A faster reduction of the dynamic time warping distance to the longest increasing subsequence length ⋮ Longest common subsequence in sublinear space ⋮ Optimality regions and fluctuations for Bernoulli last passage models ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ One-dimensional approximate point set pattern matching with \(L_p\)-norm ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ A faster algorithm computing string edit distances ⋮ Strategy-proof social choice on multiple and multi-dimensional single-peaked domains ⋮ Fast Algorithms for Computing Tree LCS ⋮ Constrained LCS: Hardness and Approximation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Orphan gene finding -- an exon assembly approach. ⋮ Sequence Alignment Algorithms for Run-Length-Encoded Strings ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ The string merging problem ⋮ A fast algorithm for the longest-common-subsequence problem ⋮ A parallel strategy for biological sequence alignment in restricted memory space ⋮ On a cyclic string-to-string correction problem ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ An O(NP) sequence comparison algorithm ⋮ Minimum message length encoding and the comparison of macromolecules ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ On measuring similarity for sequences of itemsets ⋮ An overview on XML similarity: background, current trends and future directions ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ Space efficient algorithms for ordered tree comparison ⋮ On the inadequacy of tournament algorithms for the \(N\)-SCS problem ⋮ Breadth-first heuristic search ⋮ An adaptive multi-policy grid service for biological sequence comparison ⋮ Parallel parsing on a one-way linear array of finite-state machines ⋮ Dynamic edit distance table under a general weighted cost function ⋮ On the generalized constrained longest common subsequence problems ⋮ On the space complexity of some algorithms for sequence comparison ⋮ Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ A time-efficient, linar-space local similarity algorithm ⋮ Comparing bacterial genomes from linear orders of patterns ⋮ Fast linear-space computations of longest common subsequences ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ A practical semi-external memory method for approximate pattern matching ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ An all-substrings common subsequence algorithm ⋮ An improved algorithm for the longest common subsequence problem ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ Constrained sequence alignment ⋮ The intractability of computing the Hamming distance ⋮ Unnamed Item ⋮ An information-theoretic lower bound for the longest common subsequence problem ⋮ Table design in dynamic programming ⋮ Fast algorithms for computing tree LCS ⋮ The cache complexity of multithreaded cache oblivious algorithms ⋮ Approximate labelled subtree homeomorphism ⋮ Sparse RNA Folding: Time and Space Efficient Algorithms
This page was built for publication: A linear space algorithm for computing maximal common subsequences
