[알고리즘] 동적 계획법. 최소 변환 편집(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의 염기서열에 ‘대응 문자 없슴’ 표시인 – 부호를 추가한다.
<후략>
*원하는 자료를 검색 해 보세요.
  • 생명정보학 20페이지
    ~ 사람에 이르는 다양한 종의 염기서열 정보 - 간단한 유전자의 DNA ... 수백억의 염기서열과 발현데이터 및 수많은 단백질 구조 정보를 어떻게 ... 접근하고 분석하는가 ? Contents 생물정보프로그램 생물정보학 생물정보
  • NGS에 대하여 4페이지
    Sequencing)란 차세대 염기서열 분석을 뜻한다. DNA 유전정보를 읽어내는 기술을 ... 다양한 생체 정보는 DNA 염기서열 유전자로 표현되고, 개체의 완전한 ... DNA 염기서열 정보는 생명현상을 이해하고 질병과 관련된 정보를 얻을 수
  • [생물정보학] 게놈프로젝트 15페이지
    DNA상에 존재하게 되는데 유전을 통해 단일염기변이 정보들이 서로 혼합 ... (Genetic information)를 담고 있는 물질은 DNA다. 게놈이란 ... DNA를 담고 있는 그릇의 개념으로, 유전 정보 전체를 의미한다. DNA
  • [분자생물학실험] Reverse Genetics and Bioinformatics 결과보고서 11페이지
    변이는 DNA 손상의 회복 에러, DNA 염기의 가벼운 상처에 의한 대합 ... DNA 서열분석에 이용되고 있다. 컴퓨터와 소프트웨어를 활용해 유전자의 염기 ... 염색체 DNA 상에 변이를 이식, 변이체의 표현형을 조사하여 그 산물
  • 자기조립 (self-assembly)에 대한 개괄. 3페이지
    0과 1로 짜인 알고리즘을 사용한다면 DNA 컴퓨터는 4가지 염기 ... 점에 착안해 DNA라는 생체분자를 정보 처리 프로그램으로 이용하는 DNA ... 과학 분야에서의 자기조립 DNA를 비롯해 세포와 단백질 등 우리 몸의
  • [생명공학] RNAi에 관한 설명 1페이지
    질이 만들어질 때 DNA가 유전자의 정보를 그 세포의 단백질-구성요소 ... 근거를 둔다. 과학자들은 십년 전부터 특정 유전자의 염기서열에 해당하는 ... 가지고 있는 알고리즘으로 제작된 siRNA (small interfering
  • [technology] IT,BT,NT 그리고 BT와 IT를 접합한 bioinformatics 7페이지
    . 건강한 사람의 DNA(유전자) 또는 mRNA와 상보적인 cDNA를 ... 만들어 이것을 DNA 재조합법으로 레트로바이러스 벡터와 결합시키고, 그것은 ... 그 DNA 결합으로 생긴 유전병 환자의 세포에 효율적으로 도입시키는
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [알고리즘] 동적 계획법. 최소 변환 편집(Minimum Editing Sequence) 문제. (C++)