Sequence Alignment Algorithms for Run-Length-Encoded Strings
From MaRDI portal
Publication:3511343
DOI10.1007/978-3-540-69733-6_32zbMath1148.68574OpenAlexW1600388734MaRDI QIDQ3511343
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
Related Items
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 ⋮ Hardness of comparing two run-length encoded strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
Cites Work
- Unnamed Item
- A space efficient algorithm for finding the best nonoverlapping alignment score
- An improved algorithm for computing the edit distance of run-length coded strings
- Geometric applications of a matrix-searching algorithm
- Matching for run-length encoded strings
- Approximate matching of run-length compressed strings
- Edit distance of run-length encoded strings.
- Perspectives of Monge properties in optimization
- Edit distance for a run-length-encoded string and an uncompressed string
- Monge properties, discrete convexity and applications
- Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
- On the Common Substring Alignment Problem
- Efficient Parallel Algorithms for String Editing and Related Problems
- The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity
- Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time
- A linear space algorithm for computing maximal common subsequences
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Algorithms on Strings, Trees and Sequences
- The String-to-String Correction Problem
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score