2023/07/10 by Md. Rabiul Islam Khan, Khan, Md. Rabiul Islam, Shadman Shahriar +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #Computational Engineering #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Finance #Genomics (q-bio.GN) #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2307.04479
openalex publication_date 2023/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sequence Alignment is the process of aligning biological sequences in order to identify similarities between multiple sequences. In this paper, a Quantum Algorithm for finding the optimal alignment between DNA sequences has been demonstrated which works by mapping the sequence alignment problem into a path-searching problem through a 2D graph. The transition, which converges to a fixed path on the graph, is based on a proposed oracle for profit calculation. By implementing Grover's search algorithm, our proposed approach is able to align a pair of sequences and figure out the optimal alignment within linear time, which hasn't been attained by any classical deterministic algorithm. In addition to that, the proposed algorithm is capable of quadratic speeding up to any unstructured search problem by finding out the optimal paths accurately in a deterministic manner, in contrast to existing randomized algorithms that frequently sort out the sub-optimal alignments, therefore, don't always guarantee of finding out the optimal solutions.