Classical and quantum algorithms for constructing text from dictionary problem

Abstract

We study algorithms for solving a problem of constructing a text (a 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 DNA sequence from small fragments. Our problem is the construction a string t of length n using strings s1,⋯,sm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s^1,\dots , s^m$$\end{document} with possible overlapping. Firstly, we provide a classical (randomized) algorithm with running time On+L+m(logn)2=O~(n+L)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n+L +m(\log n)^2\right) =\tilde{O}(n+L)$$\end{document} where L is the sum of lengths of s1,⋯,sm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s^1,\dots ,s^m$$\end{document}. Secondly, we provide a quantum algorithm with running time On+logn·(logm+loglogn)·m·L=O~n+m·L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n +\log n\cdot (\log m+\log \log n)\cdot \sqrt{m\cdot L}\right) =\tilde{O}\left( n +\sqrt{m\cdot L}\right) $$\end{document}. Additionally, we show that the lower bound for a classical (randomized or deterministic) algorithm is Ω(n+L)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (n+L)$$\end{document}. Thus, our classical algorithm is optimal up to a log factor, and our quantum algorithm shows a speed-up when compared with any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.