Classical and Quantum Algorithms for Constructing Text from Dictionary Problem
share
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 s^1,..., s^m with possible intersections. We provide a classical algorithm with running time O(n+L +m(log n)^2)=Õ(n+L) where L is the sum of lengths of s^1,...,s^m. We provide a quantum algorithm with running time O(n +log n·(log m+loglog n)·√(m· L))=Õ(n +√(m· L)). Additionally, we show that the lower bound for the classical algorithm is Ω(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.
READ FULL TEXT