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

등록일 2002.11.20 MS 워드 (doc) | 6페이지 | 가격 1,400원

소개글

알고리즘 레포트로 작성된 동적 계획법의 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의 염기서열에 ‘대응 문자 없슴’ 표시인 – 부호를 추가한다.
<후략>
*원하는 자료를 검색 해 보세요.
  • [C언어] selection algorithm 0페이지
    #include <stdio.h> #include <stdlib.h> #include <time.h> void SORT_INSERTION(int s, int e, int *data); int SELECTION(int..
  • 오류 역전파 알고리즘-안면인식 알고리즘 26페이지
    1.1 프로젝트 목적 정보화 시대를 걷고 있는 지금 보안의 중요성은 어떤 것 보다 강조 될 수 있다. 하지만 정보의 중요성이 강조 되는 만큼 현대사회에서는 보안을 위협하는 수많은 내외부의 공격에 노출되어 있다. 이러한 위협..
  • 알고리즘 특론(과제 3) 3페이지
    3. 패턴 집합이 다음과 같이 주어졌을 때 Aho-Corasick 알고리즘을 적용하기 위한 단어 나무를 만드시오. {double, done, undo, unit, universe} * 단어 나무의 정의 패턴의 집합..
  • 알고리즘 특론(과제 4) 9페이지
    1. 다음 텍스트 T에 대하여 접미사 나무와 접미사 배열을 각각 그리시오. T = ababcbc * 접미사 나무 T$=ababcbc$ - Naive 알고리즘 1. T$의 모든 접미사로 이루어진 단어 나무 생성 ..
  • Preparing Standard Acid and Base 레포트 자료입니다. 7페이지
    Preparing Standard Acid and Base 1.실험목적 : 일차 표준물질(KHP)를 이용하여 염기(NaOH)를 표정한다. 2.실험이론 및 원리 * 염기 표준 용액의 제법 염기 표준용액을 만드는데..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [알고리즘] 동적 계획법. 최소 변환 편집(Minimum Editing Sequence) 문제. (C++)