Needleman-Wunsch Algorithm으로 DNA 시퀀스 정렬을 처음부터 구축 – 나에게 보내는 메모

DNA 정렬이 실제로 어떻게 동작하는가? DNA 정렬이 실제로 어떻게 작동하는지 궁금하셨나요? 🧬 우리는 Needleman-Wunsch 알고리즘을 처음부터 직접 구현해 보았습니다. “CAT”와 “CT” 같은 간단한 예시를 통해 스코어링 매트릭스를 손으로 계산해 보았습니다. 그 다음 실제 E. coli 유전체에 테스트해 보았습니다. 알고리즘은 두 서열 사이의 최적 정렬을 찾기 위해 동적 프로그래밍 기법을 사용합니다. 먼저 score matrix를 설정하고, 매 행과 열에 대해 gap penalty를 적용합니다. 그 후 매 단계마다 최대 점수를 선택하여 최종 정렬을 도출합니다. “정렬은 단순히 일치하는 부분을 찾는 것이 아니라, 전체 서열을 최대한 유사하게 매칭시키는 과정입니다.” function needlemanWunsch(seq1, seq2) { const m = seq1.length; const n = seq2.length; const dp = Array.from({ length: m + 1 }, () = Array(n + 1).fill(0)); // 초기화 for (let i = 1; i 이 구현은 Needleman-Wunsch 알고리즘을 그대로 반영하며, 실험적으로 E. coli 유전체를 대상으로 테스트해 보았습니다. 결과적으로, 수작업으로 계산한 예시와 거의 동일한 최적 정렬을 얻을 수 있었습니다.