Journal
PHYSICAL REVIEW E
Volume 62, Issue 5, Pages 7532-7535Publisher
AMERICAN PHYSICAL SOC
DOI: 10.1103/PhysRevE.62.7532
Keywords
-
Categories
Ask authors/readers for more resources
Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length In (i.e., In residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O( rootN) speedup on the classical O( rootN) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O( rootN) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available