Goal: Over the decades, there have been improvements in the sequence alignment algorithm, with significant advances in various aspects such as complexity and accuracy. However, human-defined algorithms have an explicit limitation in view of developmental completeness. This paper introduces a novel local alignment method to obtain optimal sequence alignment based on reinforcement learning. Methods: There is a DQNalign algorithm that learns and performs sequence alignment through deep reinforcement learning. This paper proposes a DQN x-drop algorithm that performs local alignment without human intervention by combining the x-drop algorithm with this DQNalign algorithm. The proposed algorithm performs local alignment by repeatedly observing the subsequences and selecting the next alignment direction until the x-drop algorithm terminates the DQNalign algorithm. This proposed algorithm has an advantage in view of linear computational complexity compared to conventional local alignment algorithms. Results: This paper compares alignment performance (coverage and identity) and complexity for a fair comparison between the proposed DQN x-drop algorithm and the conventional greedy x-drop algorithm. Firstly, we prove the proposed algorithm’s superiority by comparing the two algorithms’ computational complexity through numerical analysis. Subsequently, by comparing the coverage of alignment and identity performance in the HEV sequence set, we show that the proposed algorithm can catch up with the conventional algorithm’s alignment performance even with low complexity. Moreover, by comparing the alignment times for the E.coli sequence pair, we confirm that the proposed algorithm is faster than the conventional algorithm in the case of large X parameter. Conclusions: Through this study, it was possible to confirm the possibility of a new local alignment algorithm that minimizes computational complexity without human intervention.
Sign-in or become an IEEE member to discover the full contents of the paper.