[의생명정보알고리즘] 과제 PA2 실습

Ref :
의생명정보알고리즘 강의 / 첨단바이오공학부 김재범 교수님

과제 설명

코드의 매커니즘 ft. 교수님

파일 가져오는 방법

---

✅ 과제 요구사항 정리

📝 과제 목표:

• 동적 계획법(Dynamic Programming) 을 이용한 쌍서열 정렬(pairwise sequence alignment) 구현
• Linear gap penalty 기반
• 점수 기준: match, mismatch, gap
• 프로그램 실행 예:

./PA2.py 2 1 -1 ATCTG TGCA

---

🧾 반드시 지켜야 할 조건

항목	체크 여부
기존 PA2.tmp.py를 수정	✅ 완료
새로운 파일을 만들지 않음 (재작성 금지)	✅ 완료
홈디렉토리에 PA2025 폴더 생성	✅ 완료
PA2.py 라는 이름으로 저장	✅ 완료
실행 확인	✅ Optimal alignment score = 4 출력됨
정렬 결과도 올바름	✅ ATCTG, TGCA-

---

📤 제출 방법

📍 eCampus에 제출할 것:

절대경로(absolute path)로 제출해야 해요.

예시:

/mss/home_student/202200000/PA2025/PA2.py

👉 여기서 202200000은 본인의 학번 디렉토리로 바꾸어야 해요.

---

🛠 과제 파일 가져오는 과정 쉽게 설명

1️⃣ 디렉토리 이동

cd /mss/home_student/ABD2025/

👉 이 디렉토리 안에 교수님이 미리 만들어둔 PA2.tmp.py 템플릿이 있어요!

---

2️⃣ 템플릿 파일을 복사해서 제출 폴더로 옮기기

cp PA2.tmp.py ~/PA2025/PA2.py

• cp: 복사 명령어
• PA2.tmp.py: 원본 템플릿 파일
• ~/PA2025/PA2.py: 여러분 홈 디렉토리 안의 제출용 폴더(PA2025)에 PA2.py라는 이름으로 저장해요!

💡 ~는 여러분의 홈 디렉토리를 의미해요.

---

3️⃣ vi 에디터로 템플릿 파일 열기

vi PA2.tmp.py

👉 파일 내용을 확인하거나 수정할 때 사용합니다.

---

4️⃣ 과제 다 작성한 후에는?

eCampus에 이 경로를 제출해요:

/home/student/PA2025/PA2.py

---

✅ 과제 수행 절차 요약

1️⃣ 템플릿 파일 복사

cd /mss/home_student/ABD2025/
cp PA2.tmp.py ~/PA2025/PA2.py

---

2️⃣ 제출용 디렉토리(PA2025)에 파일 생성 확인

ls ~/PA2025

→ PA2.py가 있어야 함

---

3️⃣ 실행 권한 부여 (필수!)

chmod +x ~/PA2025/PA2.py

→ 이렇게 해야 ./PA2.py처럼 실행 가능함

---

4️⃣ 파일 편집

vi ~/PA2025/PA2.py

→ 동적 계획법(DP) 기반으로 시퀀스 정렬 알고리즘을 구현
→ 입력 예시: 2 1 -1 ATCTG TGCA

 

*PA2.py 파일을 과제에 맞게 수정할 것!*

#!/usr/bin/env python3

import sys
import random

# ▶ 명령줄 인자: match 점수, mismatch 패널티, gap 패널티, 시퀀스 2개
match = int(sys.argv[1])
mismatch = int(sys.argv[2])
gap = int(sys.argv[3])
seq1 = sys.argv[4]
seq2 = sys.argv[5]

# ▶ DP 테이블 크기 정의 (행: seq1 + 1, 열: seq2 + 1)
rows = len(seq1) + 1
cols = len(seq2) + 1

# ▶ 점수 저장용 행렬(score), 이동 방향 저장용 행렬(trace)
score = [[0] * cols for _ in range(rows)]
trace = [[''] * cols for _ in range(rows)]

# ▶ 첫 번째 열 초기화: 위쪽에서만 올 수 있으므로 gap 누적
for i in range(1, rows):
    score[i][0] = score[i - 1][0] + gap
    trace[i][0] = 'U'  # Up (위쪽에서 왔다는 의미)

# ▶ 첫 번째 행 초기화: 왼쪽에서만 올 수 있으므로 gap 누적
for j in range(1, cols):
    score[0][j] = score[0][j - 1] + gap
    trace[0][j] = 'L'  # Left (왼쪽에서 왔다는 의미)

# ▶ DP 테이블 채우기 (match, mismatch, gap 고려)
for i in range(1, rows):
    for j in range(1, cols):
        # 대각선에서 온 경우: match 또는 mismatch 점수
        if seq1[i - 1] == seq2[j - 1]:
            diag = score[i - 1][j - 1] + match
        else:
            diag = score[i - 1][j - 1] + mismatch

        # 위에서 온 경우: gap 발생
        up = score[i - 1][j] + gap

        # 왼쪽에서 온 경우: gap 발생
        left = score[i][j - 1] + gap

        # 가장 높은 점수를 선택
        max_val = max(diag, up, left)
        score[i][j] = max_val

        # ▶ 같은 점수가 여러 방향에서 나올 수 있으므로 무작위 선택
        directions = []
        if diag == max_val:
            directions.append('D')  # Diagonal (대각선)
        if up == max_val:
            directions.append('U')  # Up (위)
        if left == max_val:
            directions.append('L')  # Left (왼쪽)

        trace[i][j] = random.choice(directions)  # 방향 저장

# ▶ 최적 점수 출력 (마지막 칸 값)
print("Optimal alignment score =", score[-1][-1])

# ▶ Traceback: 오른쪽 아래에서 시작해 방향 따라 이동하며 정렬 복원
i = len(seq1)
j = len(seq2)
aligned1 = ''  # 정렬된 시퀀스 1
aligned2 = ''  # 정렬된 시퀀스 2

while i > 0 or j > 0:
    move = trace[i][j]
    if move == 'D':
        aligned1 = seq1[i - 1] + aligned1
        aligned2 = seq2[j - 1] + aligned2
        i -= 1
        j -= 1
    elif move == 'U':
        aligned1 = seq1[i - 1] + aligned1
        aligned2 = '-' + aligned2  # seq2에 gap 추가
        i -= 1
    elif move == 'L':
        aligned1 = '-' + aligned1  # seq1에 gap 추가
        aligned2 = seq2[j - 1] + aligned2
        j -= 1

# ▶ 정렬된 시퀀스 출력
print(aligned1)
print(aligned2)

---

5️⃣ 실행

cd ~/PA2025
./PA2.py 2 1 -1 ATCTG TGCA

6️⃣ 출력 예시

Optimal alignment score = 4
ATCTG
TGCA-

=> 이렇게 나오면 정답!! (random 함수를 사용해 경로가 다양하므로 정답이 여러개가 나올 수 있음)

---

🧠 핵심 목표 요약

• PA2.py 안에 동적 계획법(DP) 기반 pairwise alignment 알고리즘을 구현
• 입력된 매치 점수, 미스매치 패널티, 갭 패널티를 이용해 최적 정렬
• 출력 형식은 꼭 아래와 같아야 함:
• Optimal alignment score = [정수] [정렬된 시퀀스1] [정렬된 시퀀스2]