2019/09/05 by Barton, Carl, Birney, Ewan, Fitzgerald, Tomas
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1909.02364
In this paper we study a variant of string pattern matching which deals with tuples of strings known as multi-track strings. Multi-track strings are a generalisation of strings (or single-track strings) that have primarily found uses in problems related to searching multiple genomes and music information retrieval. A multi-track string T = (t1, t2, t3, … , tN) of length n and track count N is a multi-set of N strings of length n with characters drawn from a common alphabet of size σU. Given two multi-track strings T = (t1, t2, t3, … , tN) and P = (p1, p2, p3, … , pN) of length n and track count N, there is a full-permuted-match between P and T if tri = pi for all i ∈ \1,2,3,… N \ and some permutation (r1, r2, r3…,rN) of (1, 2, 3,…,N), we denote this P\asympT. Efficient algorithms for some full-permuted-match problems on multi-track strings have recently been presented. In this paper we show a reduction from a multi-track string of length n and track count N with alphabet size σU, to a single-track string of length 2n-1 with alphabet size σUN. Through this reduction we allow any string algorithm to be used on multi-track string problems using \asymp as the match relation. For polynomial time algorithms on single-track strings of length n there is a multiplicative penalty of not more than O(N)-time for the same algorithm on mt-strings of length n and track count N.