DNA sequence(DNA 시퀀스)에서 dynamic programming(동적 계획법) 이용 Longest Common Subsequences(LCS, 최장 공통 부분 수열) 찾는 python 코드

두 문자열의 Longest Common Subsequence (LCS)를 찾는 알고리즘을 구현한 것입니다. LCS는 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 문자열입니다.

 

동적 계획법을 사용하여 LCS를 찾는 과정:

1. lcs 함수는 두 문자열 X와 Y를 입력으로 받아 LCS를 계산합니다.
2. 문자열의 길이 m과 n을 구하고, (m+1) x (n+1) 크기의 행렬 dp을 초기화합니다.
3. 동적 계획법을 사용하여 행렬 dp을 채웁니다. 행렬의 각 요소는 해당 위치까지의 두 문자열의 부분 문자열들 간의 LCS 길이를 저장합니다.
4. 행렬 dp에서 LCS를 추출하는 백트래킹 과정을 수행합니다. 이를 통해 실제 LCS 문자열 lcs_str을 구합니다.
5. 먼저 lcs 함수를 최적화를 위해 한 번 호출하고, 두 DNA 서열을 정의합니다.
6. 시간 측정을 시작하고, 두 DNA 서열의 LCS를 계산합니다.
7. 시간 측정을 종료한 후, 걸린 시간을 마이크로초 단위로 출력합니다.
8. 결과로 계산된 LCS를 출력합니다.

import time

def lcs(X, Y):
    # 두 문자열의 길이를 계산합니다.
    m = len(X)
    n = len(Y)

    # (m+1) x (n+1) 크기의 행렬을 초기화합니다.
    dp = [[0] * (n+1) for _ in range(m+1)]

    # 동적 계획법으로 행렬을 채웁니다.
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 행렬에서 LCS를 추출합니다.(BackTracking)
    lcs_str = ""
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs_str = X[i-1] + lcs_str
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return lcs_str

# 함수를 한번 호출하여 최적화
lcs("A", "A")

# 두 DNA 서열을 정의합니다.
seq1 = "ATGTTAT"
seq2 = "ATCGTAC"

# 시간 측정 시작
start_time = time.perf_counter()

# 두 DNA 서열의 LCS를 계산합니다.
result = lcs(seq1, seq2)

# 시간 측정 종료 후 저장
required_time = (time.perf_counter() - start_time) * 1e6 

print(f"Time required for sequence : {required_time:.5f} (us)")

# 결과를 출력합니다.
print("Longest Common Subsequence:", result)