[알고리즘] 동적 계획법. 최소 변환 편집(Minimum Editing Sequence) 문제. (C++)

소개

알고리즘 레포트로 작성된 동적 계획법의 Minimum Editing Sequence 문제 풀이 입니다.
과제는 두개의 서로 다른 염기서열에 대해 최소 편집을 시도해 염기 서열의 유사도를 측정하는 것입니다.

C++ 로 작성되었으며 VC++ 6.0 으로 작업했습니다.

A+ 레포트

목차

1. 문제 정의
2. 문제 해석
3. 알고리즘
4. Source
5. 결과

본문내용

1. 문제 정의
두 염기서열 S = s1 s2 s3 . . . sm과 T = t1 t2 . . . tn의 차이는 다음과 같이 정의된다. A로부터 다음의 세가지 연산들을 이용하여 B로 바꿀 때 필요한 최소 연산수이다:
하나의 문자를 insert
하나의 문자를 delete
하나의 문자를 다른 문자로 대체
위의 연산들에 의하여 이들 두 염기서열을 맞출 수 있다
S = AGT-CC // -는 대응하는 문자가 없다는 것을 의미함
T = -GTACG
위의 두 염기서열의 차이가 3임을 알 수 있다.
두 염기서열을 입력하여 가장 차이가 작도록 두 염기수열을 맞추는 프로그램을 작성하시오.

2. 문제 해석
동적 계획법의 Minimum Editing Sequence 문제를 해결하고 각 편집 과정 중에서 Insert 와 Delete 과정에 대응되는 염기에 – 부호를 추가해 준다.

3. 알고리즘
염기서열 A를 염기서열 B로 바꾸기 위해 2차원 배열로 테이블을 구성한다.
배열은 변환횟수와 변환과정을 저장하기 위한 구조체로 정의하며 완성된 테이블을 이용하여 역방향으로 변환과정을 탐색한다.
탐색중 변환과정 ‘L’ 에 해당되는 delete의 경우 원본 A에 해당하는 B의 염기가 존재하지 않는 것이므로 B의 염기서열에 ‘대응 문자 없슴’ 표시인 – 부호를 추가한다.
<후략>

참고자료

· 없음