Classical and Quantum Algorithms for Constructing Text from Dictionary Problem

We study algorithms for solving the problem of constructing a text (long string) from a dictionary (sequence of small strings). The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments. The problem is constructing a string t of length n from strings s1,dots, sm with possible intersections. We provide a classical algorithm with running time Oleft(n+L +m(log n)2right)=tildeO(n+L) where L is the sum of lengths of s1,dots,sm. We provide a quantum algorithm with running time Oleft(n +log n·(log m+loglog n)· √m· Lright)=tildeOleft(n +√m· Lright). Additionally, we show that the lower bound for the classical algorithm is Omega(n+L). Thus, our classical algorithm is optimal up to a log factor, and our quantum algorithm shows speed-up comparing to any classical algorithm in a case of non-constant length of strings in the dictionary.