Weighted LCS

DOI10.1016/J.JDA.2010.02.001MaRDI QIDQ5901140zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Zvi Gotthilf, B. R. Shalom

Publication date 18 August 2010

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2010.02.001

zbMATH Keywords

approximation algorithmsNP-hard problemposition weight matrixstring algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Weighted LCS (extended abstract)
• Polynomial-time approximation algorithms for weighted LCS problem
• Polynomial-time approximation algorithms for weighted LCS problem
• A linear space algorithm for the heaviest common subsequence problem
• An algorithm for the constrained heaviest common subsequence problem

Cites work

• A linear space algorithm for computing maximal common subsequences
• A linear space algorithm for the heaviest common subsequence problem
• Approximate Matching in Weighted Sequences
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2163025 (Why is no real title available?)
• Matching for run-length encoded strings
• Property Matching and Weighted Matching
• The String-to-String Correction Problem

Cited in

(14)

• On-line weighted pattern matching
• A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
• Polynomial-time approximation algorithms for weighted LCS problem
• LCSk: a refined similarity measure
• Polynomial-time approximation algorithms for weighted LCS problem
• A multiobjective optimization algorithm for the weighted LCS
• Linear-time computation of prefix table for weighted strings
• A linear space algorithm for the heaviest common subsequence problem
• Linear-time computation of prefix table for weighted strings {\&} applications
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Fast Average-Case Pattern Matching on Weighted Sequences
• Weighted LCS (extended abstract)
• Weighted shortest common supersequence
• Weighted shortest common supersequence problem revisited

Describes a project that uses

Uses Software

• ClustalW

This page was built for publication: Weighted LCS

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