2020/08/04 by Sepideh Aghamolaei, Aghamolaei, Sepideh
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2008.01768
openalex publication_date 2020/08/04 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Given a set of k strings I, their longest common subsequence (LCS) is the\nstring with the maximum length that is a subset of all the strings in I. A\ndata-structure for this problem preprocesses I into a data-structure such\nthat the LCS of a set of query strings Q with the strings of I can be\ncomputed faster. Since the problem is NP-hard for arbitrary k, we allow an\nerror that allows some characters to be replaced by other characters. We define\nthe approximation version of the problem with an extra input m, which is the\nlength of the regular expression (regex) that describes the input, and the\napproximation factor is the logarithm of the number of possibilities in the\nregex returned by the algorithm, divided by the logarithm regex with the\nminimum number of possibilities. Then, we use a tree data-structure to achieve\nsublinear-time LCS queries. We also explain how the idea can be extended to the\nlongest increasing subsequence (LIS) problem.\n