유전자서열 정렬을 위한 Dynamic Programing Algorithm의 개선

• 발행기관: 강원대학교 기초과학연구소
• 저자명: 안희국 노희영
• 간행물 정보: 『기초과학연구』제16집, 89~105쪽, 전체 17쪽
• 주제분류: 자연과학 > 자연과학일반
• 파일형태: PDF
• 발행일자: 2005.12.01

국문 초록

  본 논문에서는 생물서열 정렬 및 검색에 사용되는 알고리즘(Dynamic Programming(DP), BLAST, FASTA)들 중에서 정확성을 보장하는 DP 알고리즘이 큰 데이터베이스에 적용될 때 발생시킬 수 있는 비용증가(O((n<SUP>*</SUP>m)) 문제를 해결하고자 하였다. DP알고리즘은 행렬생성단계와 역추적 단계로 구성되는데 본 논문에서는 행렬생성단계의 불필요한 정렬계산을 정리와 증명을 통해 제거함으로서 전체 수행시간이 단축될 수 있도록 알고리즘을 설계하였다. 본 논문에서 설계한 알고리즘을 실험샘플에 적용한 결과 기존의 일반적인 DP방법보다 적은 연산으로 완전한 최적정렬 서열을 찾을 수 있음을 확인하였다.

목차

요약
1. 서론
2. 관련 연구
3. 개선된 DP 알고리즘의 설계
4. 결과
5. 결론 및 향후 연구과제
6. 참고문헌