Sequence Alignment Algorithms for Run-Length-Encoded Strings

DOI10.1007/978-3-540-69733-6_32MaRDI QIDQ3511343zbMATH OpenOpenAlexFDO

Authors Guan-Shieng Huang, Jia-Jie Liu, Yue-Li Wang

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_32

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Computing similarity of run-length encoded strings with affine gap penalty
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• An algorithm for matching run-length coded strings
• Edit distance of run-length encoded strings.

Cites work

• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A linear space algorithm for computing maximal common subsequences
• A space efficient algorithm for finding the best nonoverlapping alignment score
• Algorithms on Strings, Trees and Sequences
• Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
• An improved algorithm for computing the edit distance of run-length coded strings
• Approximate matching of run-length compressed strings
• Edit distance for a run-length-encoded string and an uncompressed string
• Edit distance of run-length encoded strings.
• Efficient Parallel Algorithms for String Editing and Related Problems
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Geometric applications of a matrix-searching algorithm
• Matching for run-length encoded strings
• Monge properties, discrete convexity and applications
• On the common substring alignment problem
• Perspectives of Monge properties in optimization
• The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity
• The String-to-String Correction Problem

Cited in

(7)

• Approximating dynamic time warping distance between run-length encoded strings
• Hardness of comparing two run-length encoded strings
• Dynamic RLE-compressed edit distance tables under general weighted cost functions
• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Õptimal dynamic time warping on run-length encoded strings
• Computing similarity of run-length encoded strings with affine gap penalty
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

This page was built for publication: Sequence Alignment Algorithms for Run-Length-Encoded Strings

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