[컴퓨팅사고력] DNA 조작 횟수를 최소로 만들어 보자

DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다.

DNA 염기서열을 연구하고 있는 원당이는 고릴라의 염기서열이 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열이 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다.

원당이는 고릴라와 원숭이의 염기서열을 똑같이 만들어 보고 싶습니다.

가령 GATA 의 염기서열을 AAGT 로 만든다면 GATA에서 3개를 변경해서 만들 수 있습니다.

혹은 AA 와 같이 만든다면  G와 T 두개의 염기서열을 삭제해서 만들 수 있습니다.

또는 GATAT 와 같은 경우는 T를 추가해서 염기서열을 만들 수가 있습니다.

이렇게 변경하거나 추가하거나 삭제하는 세가지 작업을 수행 할 수 있을때 고릴라의 염기서열과 원숭의의 염기서열을 서로 같게 만드는 최소의 작업 횟수는 얼마인지 여러분이 계산을 도와 주세요.

 

문제풀이

GATACCAGATACCCA AAGATTGCCATTATT 여기서 처음 나오는 G->A로 편집 1회 AATACCAGATACCCA AAGATTGCCATTATT 세번째 T->G 로 편집 2회 AAGACCAGATACCCA AAGATTGCCATTATT 네번째와 다섯번째 사이에 TTG를 삽입 5회 AAGATTGCCAGATACCCA AAGATTGCCATTATT 11번째 G를 삭제 12번째 A를 T로 편집 7회 AAGATTGCCATTACCCA AAGATTGCCATTATT 14번째 15번째를 TT로 편집후 16번째 17번째를 삭제 -> 11회

 

 

컴퓨팅사고력

이 문제는 컴퓨팅과학에서는 동적알고리즘(Dynamic Algorithm) 중에서 최장공통부분수열(LCS) 알고리즘을 응용하는 문제입니다.

만약 GATA 와 AAGT 의 최소 작업 횟수를 생각하면

GATA 만 있고 두번째 염기서열이 아무것도 없다면 다음과 같이 최대 4회 추가해서 만드는 경우를 생각할 수 있습니다.

두번째 염기서열에 A 가 들어 온다고 하면 다음과 같이 A가 G를 만난다면 1회 편집 하거나 G를 삭제후 A를 추가하는 횟수 2회 또는 A를 추가 후 G를 삭제하는 횟수 2회 중 가장 작은 1회 편집을 선택 할 수 있습니다.

또한 GA 에서는 아무것도 없는 곳에서 만난 G를 추가한 횟수 1회에서 편집 없이 + 0 회로 바로 가져 올 수 있습니다.

이렇게 같은 문자라면 그 이전에서 편집 횟수 없이 가져 올 수 있고 다른 문자라면 그 이전에서 편집횟수 + 1회 또는 삭제횟수 +1회, 추가 횟수 +1회 중 가장 작은 수를 자신의 숫자로 가져 올 수 있습니다.

이렇게 이전에 구해 놓은 정보를 활용해서 최적의 편집 횟수를 구하면 다음과 같이 구할 수 있습니다.

테이블을 그려서 11번의 작업으로 같게 만들 수 있는 것을 확인 할 수 있습니다.