Computing similarity of run-length encoded strings with affine gap penalty

DOI10.1016/J.TCS.2008.01.008zbMATH Open1142.68069OpenAlexW2042476538MaRDI QIDQ932322FDOQ932322

Authors: Jin Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park 

Publication date: 10 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.008

Recommendations

• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Edit distance of run-length encoded strings.
• Matching for run-length encoded strings
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Approximate matching of run-length compressed strings

zbMATH Keywords

similarityrun-length encodingaffine gap penalty

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Matching for run-length encoded strings
• Approximate matching of run-length compressed strings
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• An improved algorithm for computing the edit distance of run-length coded strings
• Some biological sequence metrics
• Edit distance of run-length encoded strings.
• A time-efficient, linar-space local similarity algorithm
• An efficient alignment algorithm for masked sequences
• Title not available (Why is that?)

Cited In (4)

• Hardness of comparing two run-length encoded strings
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Algorithms for computing evolutionary similarity measures with length independent gap penalties
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

This page was built for publication: Computing similarity of run-length encoded strings with affine gap penalty

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