Nonlinear Phenomena in Complex Systems, 2021, Vol.24, No.3, pp.207

NONLINEAR PHENOMENA IN COMPLEX SYSTEMS
An Interdisciplinary Journal

2021, Vol.24, No.3, pp.207 - 221

Classical and Quantum Algorithms for Assembling a Text from a Dictionary

Kamil Khadiev and Vladislav Remidovskii

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 s¹,...,s^m. Firstly, we provide a classical (randomized) algorithm with running time Õ(nL^0.5 + L) where L is the sum of lengths of s¹,...,s^m. Secondly, we provide a quantum algorithm with running time Õ(nL^0.25 + √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.

Key words: quantum computation, quantum algorithm, string constructing, sequence assembly, DNA constructing

DOI: https://doi.org/10.33581/1561-4085-2021-24-3-207-221

Full text: Acrobat PDF (620 KB)