Classical and Quantum Algorithms for Assembling a Text from a Dictionary

Abstract

We study algorithms for solving the problem of assembling a text (long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long deoxyribonucleic-acid (DNA) sequence from small fragments. The problem is assembling a string t of length n from strings s1; : : : ; sm. Firstly, we provide a classical (randomized) algorithm with running time ~O(nL0:5 + L) where L is the sum of lengths of s1; : : : ; sm. Secondly, we provide a quantum algorithm with running time ~O(nL0:25+p mL). Thirdly, we show the lower bound for a classical (randomized or deterministic) algorithm that is (n+L). So, we obtain the quadratic quantum speed-up with respect to the parameter L; and our quantum algorithm have smaller running time comparing to any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.