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

DOI10.1016/J.TCS.2008.01.008zbMath1142.68069OpenAlexW2042476538MaRDI QIDQ932322

Gad M. Landau, Amihood Amir, Jin Wook Kim, Kun Soo 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

zbMATH Keywords

similarityrun-length encodingaffine gap penalty

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (1)

Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

Cites Work

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

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