ON QUANTUM ALGORITHM FOR MULTIPLE ALIGNMENT OF AMINO ACID SEQUENCES
Satoshi Iriyama, Masanori Ohya · 2009
The alignment of genome sequences or amino acid sequences is one of fundamental operations for the study of life. Usual computational complexity for the multiple alignment of N sequences with common length L by dynamic programming is O(LN). This alignment is considered as one of the NP problems, so that it is desirable to find a nice algorithm of the multiple alignment. Thus in this paper we propose the quantum algorithm for the multiple alignment based on the works [7, 14] in which the NP complete problem was shown to be the P problem by means of quantum algorithm and chaos informarion dynamics.