Edit Distance

https://rosalind.info/problems/edit/

ROSALIND | Edit Distance

Problem

Given two strings ss and tt (of possibly different lengths), the edit distance dE(s,t)dE(s,t) is the minimum number of edit operations needed to transform ss into tt, where an edit operation is defined as the substitution, insertion, or deletion of a single symbol.

The latter two operations incorporate the case in which a contiguous interval is inserted into or deleted from a string; such an interval is called a gap. For the purposes of this problem, the insertion or deletion of a gap of length kk still counts as kk distinct edit operations.

Given: Two protein strings ss and tt in FASTA format (each of length at most 1000 aa).

Return: The edit distance dE(s,t)dE(s,t).

Sample Dataset

>Rosalind_39
PLEASANTLY
>Rosalind_11
MEANLY

Sample Output

5

 

 이 문제는 edit distance를 구하는 문제이다. edit distance란 삽입,치환,제거 3가지 방법을 이용하여 앞의 서열을 뒤의 서열로 바꿀때, 방법을 쓰는 최소의 횟수이다. 이 문제를 달리보면 longest common sequence 문제에서 치환을 추가한것과 같다. 그러므로 이 문제도 다이나믹 프로그래밍을 이용하여 풀 수 있다.

 필자는 편의를 위해 서열 앞에 공백을 추가하였다. 그리고 위의 서열을 가로로 하고 행을 i로 아래의 서열을 세로로하고 열을 j로 할 것이다. 그리고 우리는 서열의 앞부분을 비교해가며 전질할 것이다. 표[i][j]는 첫번째로 i나 j가 0이라면 한쪽은 비어있는 문자열이므로 다른 쪽에는 문자열의 길이만큼 삽입하거나 빼야하므로 i가 0이라면 j로, j가 0이라면 i이다. 두번째로 문자열1[i]와 문자열2[j]가 같다면, 그 무엇도 건드릴 필요없이 추가하면 되므로 표[i-1][j-1]이다. 마지막으로 저 둘이 다르다면, 표[i-1][j],표[i][j-1] (이 둘은 삽입,제거의 경우), 표[i-1][j-1](이는 치환의 경우)중 가장 작은 값에 +1을 하는 값이다.

 말로 풀자니 말이 어려워졌지만 https://en.wikipedia.org/wiki/Levenshtein_distance 이 위키피디아를 참고하면 쉽게 풀 수 있다. 

 위에서 말한 걸 이용하여 예시를 풀자면 아래와 같다.

	i	0	1	2	3	4	5	6	7	8	9	10
j		' '	P	L	E	A	S	A	N	T	L	Y
0	' '	0	1	2	3	4	5	6	7	8	9	10
1	M	1	1	2	3	4	5	6	7	8	9	10
2	E	2	2	2	2	3	4	5	6	7	8	9
3	A	3	3	3	3	2	3	4	5	6	7	9
4	N	4	4	4	4	3	3	4	4	5	6	8
5	L	5	5	4	5	4	4	4	5	5	5	7
6	Y	6	6	5	5	5	5	5	5	6	6	5

 

우리는 모든 문자열이 있는 오른쪽 아래의 숫자 하나만 출력하면 된다. 이경우 예시처럼 5가 나온다.

from Bio import SeqIO

def edit_distance(s1,s2):
    array=[[0 for _ in range(len(s2))] for _ in range(len(s1))]#[s1][s2]로 넣기

    for i in range(len(s1)):
        for j in range(len(s2)):
            if i==0:#i가 0이면
                array[i][j] = j
            elif j==0:#j가 0이라면
                array[i][j] = i
            elif s1[i] == s2[j]:#둘이 같으면
                array[i][j] = array[i-1][j-1]
            else:#둘이 다르면
                temp=min([array[i-1][j],array[i][j-1],array[i-1][j-1]])#이 중 최소
                array[i][j] = 1+temp#+1

    return array[len(s1)-1][len(s2)-1]#최종

if __name__ == '__main__':
    with open(r'파일경로','r') as fa:
        seqs=[]
        for s in SeqIO.parse(fa,'fasta'):
            seqs.append(s.seq)
        S1=' '+str(seqs[0])
        S2=' '+str(seqs[1])

print(edit_distance(S1,S2))