Classical and Quantum Algorithms for Constructing Text from Dictionary\n Problem

2020/05/28 by Kamil Khadiev, Khadiev, Kamil, Vladislav Remidovskii +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Genome Rearrangement Algorithms #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2005.14335

openalex publication_date 2020/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study algorithms for solving the problem of constructing a text (long\nstring) from a dictionary (sequence of small strings). The problem has an\napplication in bioinformatics and has a connection with the Sequence assembly\nmethod for reconstructing a long DNA sequence from small fragments. The problem\nis constructing a string t of length n from strings s¹,\…, s^m with\npossible intersections. We provide a classical algorithm with running time\nO\(n+L +m(\log n)²\)=\O(n+L) where L is the sum of lengths\nof s¹,\…,s^m. We provide a quantum algorithm with running time O\(n\n+\log n\⋅(\log m+\log\log n)\⋅ \√(m\⋅ L)\)=\O\(n\n+\√(m\⋅ L)\). Additionally, we show that the lower bound for the\nclassical algorithm is \Ω(n+L). Thus, our classical algorithm is optimal\nup to a log factor, and our quantum algorithm shows speed-up comparing to any\nclassical algorithm in a case of non-constant length of strings in the\ndictionary.\n

Cited by

• Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle

Related

• Quantum Algorithm for the Multiple String Matching Problem
• Quantum Algorithm for the Shortest Superstring Problem
• Longest Common Substring and Longest Palindromic Substring in O(√(n)) Time
• Near-Optimal Quantum Algorithms for String Problems
• Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings