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

DOI10.1016/J.TCS.2008.01.008MaRDI QIDQ932322zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

similarityrun-length encodingaffine gap penalty

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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

Cites work

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

Cited in

(4)

• Hardness of comparing two run-length encoded strings
• Algorithms for computing evolutionary similarity measures with length independent gap penalties
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• 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)