초록 ▼

본 연구는 DNA 염기 순서의 재구성과 DNA 지도 작성 방법의 일부분을 조사하여 계산 작업이 필요한 부분을 찾아 계산모형을 만들고, NP-complete이라는 계산 모형의 분석에 따라 근사 알고리즘을 제시하고, 또 이들의 효율적 구현 방법과 성능의 수리적 분석을 다루었다. DNA 염기 순서 재구성의 경우에는 수반되는 생화학적 실험 방법에 따라 계산 모형으로 서브스트링 매칭 문제, 근사 스트링 매칭 문제, 가역 최단 공통 수퍼스트링 문제 등을 제시하여 이들 스트링 문제들이 일반 소프드웨어들에서의 응용뿐만 아니라 유전공학에도 응용될

본 연구는 DNA 염기 순서의 재구성과 DNA 지도 작성 방법의 일부분을 조사하여 계산 작업이 필요한 부분을 찾아 계산모형을 만들고, NP-complete이라는 계산 모형의 분석에 따라 근사 알고리즘을 제시하고, 또 이들의 효율적 구현 방법과 성능의 수리적 분석을 다루었다. DNA 염기 순서 재구성의 경우에는 수반되는 생화학적 실험 방법에 따라 계산 모형으로 서브스트링 매칭 문제, 근사 스트링 매칭 문제, 가역 최단 공통 수퍼스트링 문제 등을 제시하여 이들 스트링 문제들이 일반 소프드웨어들에서의 응용뿐만 아니라 유전공학에도 응용될 수 있음을 밝혔다. 가역 최단 공통 수퍼스트링 그리디 근사 알고리즘이 이론적 성능비가 2라는 분석과 효율적인 구현을 제시하였다. DNA 지도 작성 문제의 경우 역시 실험 자료에서 동등한 제한조각이 둘 이상일 때 갯수를 판별할 수 없을 경우의 계산 모형인 인접 집합 문제와 판별가능한 경우의 계산모형인 최단 공통 매칭 스트링 문제를 제시하였다. 최단 공통 매칭 스트링 문제의 경우 그 자체로 NP-complete인데 이를 두 단계의 각각 NP-complete인 문제로 분리하였으며, 각 단계에 별도의 근사 알고리즘을 적용하는 새로운 접근 방법을 제시하였다.

Abstract ▼

Our research formulated computational problems associated with DNA sequencing and mapping. Some of the problems are NP-complete, and hence their approximation algorithms were developed and analyzed and analyzed, and their efficient implementation was studied. Computational problems associated with D

Our research formulated computational problems associated with DNA sequencing and mapping. Some of the problems are NP-complete, and hence their approximation algorithms were developed and analyzed and analyzed, and their efficient implementation was studied. Computational problems associated with DNA sequencing were substring matching problem, approximate string pattern matching problem, and reversible shortest common superstring problem, depending on the data acquisition process involving biochemical methods. The uses of those string problems of their own importance in many computer software application were further extended to genetics applications. Computational problems associated with DNA mapping were consecutive sets problem and shortest common matching string prtoblem, depending again on the data acquisition process. Approximation approach to NP-complete shortest common matching string problem was to decompose the problem into two subproblems which are NP-complete by themselves, and tried approximation algorithms for each subproblem.

목차 Contents

• 1. 서론...9
• 1.1 배경...9
• 1.2 DNA 관련 문제들의 계산 모형...12
• 1.3 보고서의 구성...19
• 2. DNA 염기 순서 재구성 문제와 알고리즘...20
• 2.1 서론...20
• 2.2 용어와 기호의 정의...21
• 2.3 알고리즘 및 분석...23
• 2.4 알고리즘의 효율적 구현...27
• 3. DNA 지도 작성 문제와 알고리즘...35
• 3.1 서론...35
• 3.2 SCMS-SS를 위한 근사 알고리즘...37
• 3.3. SCMS-SS 알고리즘...44
• 4. 결론...56
• 4.1 연구 결과...56
• 4.2 향후 연구 방향...57
• 5. 참고문헌...59