Various methods have been developed to analyze the association between organisms and their genomic sequences. Among them, sequence alignment is most frequently used for comparative analysis of biological genomes. However, the traditional sequence alignment method is considerably complex in proportion to the product of the length of the sequences, and it is considerably challenging to align long sequences such as a human genome. Over the decades, there have been improvements in the sequence alignment algorithm, with significant advances in various aspects such as complexity, accuracy, or algorithms' diversity. However, human-defined algorithms have an explicit limitation in view of the development completeness. This thesis introduces a novel method to obtain optimal sequence alignment based on reinforcement learning.
At first, we proposed the local best path selection model, which repeats optimal alignment in the small window at every step. However, the local best path selection model needs to solve the complexity problem because it repeats optimal alignment process many times. Here, we decided to adapt deep reinforcement learning to mimic the proposed heuristic sequence alignment algorithm. This deep reinforcement learning based sequence alignment algorithm, named as DQNalign, can select the next destination by observing at the current state only without aligning the subsequences in the window size. DQNalign determines immediately and proceeds the optimal alignment direction by using the sequence information within the window of the current alignment position. DQNalign shows superiority for dissimilar sequence pairs which have low identity values. Theoretically, we prove that the proposed DQNalign can achieve the same performance as the optimal alignment method with only linear complexity in case of a large window size.
DQNalign was used to minimize human intervention and find the optimal path with only the given alignment score system. However, since previous DQNalign algorithm can only proceed global alignment, it was essential to find an appropriate starting point to complete the sequence alignment. This thesis proposes a novel local alignment method based on DQNalign algorithm. Besides, by providing adaptability in various environments using meta-learning, the proposed local alignment method based on DQNalign algorithm shows an appropriately optimized technique for different sequence sets. By deriving the window size to maintain high performance, we proved that the proposed method has an advantage in view of local alignment complexity. Also, we verified the complexity relations among various parameters through simulation in the actual genome sequence. Finally, we confirmed that the proposed local alignment method based on DQNalign algorithm has an advantage over the conventional method as the x-drop parameter increases. Through this study, it was possible to confirm the possibility of a new alignment algorithm that minimizes human intervention and has higher scalability.
생물과 염기서열 간의 연관성을 분석하기 위해 다양한 방법이 개발되었다. 이 중, 염기서열 정렬은 생물의 유전체를 비교 분석하는데에 가장 많이 사용되는 방식이다. 그러나, 기존의 염기서열 정렬 방법은 염기 서열의 길이의 곱에 비례하는 복잡성 때문에, 인간 게놈과 같은 긴 염기서열을 정렬하는 것은 상당히 복잡하고 힘든 작업이다. 이에, 수십년이라는 시간에 걸쳐 염기서열 정렬 방법은 복잡도, 정확도 측면에서 수많은 발전을 이루어왔다. 그러나, 사람이 정의한 알고리즘은 그 정밀함에 명백한 한계가 존재하므로 이 논문에서는 강화학습 방법을 기반으로 학습한 염기서열 정렬 방식이라는 새로운 방법을 제안한다.
먼저 작은 창 안에서의 염기서열 정렬을 반복하며 전체 염기서열 정렬을 완성하는 방법인 로컬 최적 경로 선택 모델을 제안하였지만, 이는 염기서열 정렬을 반복한다는 점에서 높은 복잡도 문제가 존재했다. 이에, 우리는 심층 감화학습 기법을 통해 로컬 최적 경로 선택 모델을 유사하게 구현한다. DQNalign이라 명명한 이 심층 강화 학습 기반의 염기서열 정렬 방법은 현재의 창 안에 있는 염기서열의 일부를 관찰하고 이에 대한 다음 정렬 방향을 선택함으로써 최적의 염기서열 정렬을 즉각적으로 구해나가도록 한다. 이 DQNalign 방식은 낮은 유사도의 염기서열 쌍에서 높은 성능을 가지는 것을 확인하였으며, 이론적으로도 매우 큰 창 크기에서 선형의 복잡도만으로도 최적의 염기서열 정렬 방법과 같은 성능을 얻을 수 있음을 보였다.
DQNalign은 인간의 개입을 최소화하고 주어진 정렬 점수 시스템만으로 최적의 경로를 찾을 수 있도록 하였다. 하지만, DQNalign은 현재 정해진 위치에서의 창만 관찰하고 염기서열을 정렬하기 때문에, 그 시작 지점을 찾는 것이 매우 중요한 문제점이였다. 이에, 본 논문에서는 DQNalign에 greedy x-drop 알고리즘을 융합하여 로컬 염기서열 정렬을 수행하는 방법을 제안한다. 메타 러닝 기법을 추가로 적용하면서 다양한 환경에의 적응성을 확보하였고, 실제 염기서열을 이용하여 뉴럴 네트워크를 최적화함으로써 성능을 향상시켰습니다. 높은 성능을 유지하기 위한 최적 창크기를 도출함으로써, 로컬 염기서열 정렬 방식에서 제안 방안이 복잡도의 이득을 가진다는 것을 보였다. 또한, 실제 염기서열에서의 시뮬레이션을 통해 다양한 매개변수에 대한 복잡도의 이론적 분석을 검증하였습니다. 마지막으로, DQNalign 기반의 로컬 염기서열 정렬 방식이 매우 큰 x-drop 매개변수에서 이점을 가진 다는 것을 확인하였으며, 우리는 사람의 개입을 최소화하고 높은 확장성을 가지는 새로운 염기서열 정렬 알고리즘의 가능성을 확인하였다.
