An O(NP) sequence comparison algorithm

DOI10.1016/0020-0190(90)90035-VMaRDI QIDQ912628zbMATH OpenFDO

Authors Sun Wu, Udi Manber, Gene Myers, Webb Miller

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

sequence comparisonlongest commong subsequenceshortest edit script

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An \(O(ND)\) difference algorithm and its variations
• scientific article; zbMATH DE number 3845091
• Sequence comparison with concave weighting functions
• A fast longest common subsequence algorithm for similar strings
• Incremental String Comparison

Cites work

• scientific article; zbMATH DE number 4128413 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• Algorithms for approximate string matching
• Algorithms for the Longest Common Subsequence Problem
• An \(O(ND)\) difference algorithm and its variations
• Shortest paths in Euclidean graphs
• The String-to-String Correction Problem

Cited in

(16)

• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• Calculating distances for dissimilar strings: the shortest path formulation revisited
• A new practical linear space algorithm for the longest common subsequence problem
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 4128413 (Why is no real title available?)
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• scientific article; zbMATH DE number 2086238 (Why is no real title available?)
• An efficient algorithm for sequence comparison with block reversals
• Fast Algorithms for Local Similarity Queries in Two Sequences
• Mining Bit-Parallel LCS-length Algorithms
• An \(O(ND)\) difference algorithm and its variations
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Simple and fast linear space computation of longest common subsequences
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• Fast trie-based method for multiple pairwise sequence alignment
• A learning algorithm for the longest common subsequence problem

This page was built for publication: An O(NP) sequence comparison algorithm

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