학술저널
유전자서열 정렬을 위한 Dynamic Programing Algorithm의 개선
- 강원대학교 기초과학연구소
- 기초과학연구
- 제16집
-
2005.1289 - 105 (17 pages)
- 16
본 논문에서는 생물서열 정렬 및 검색에 사용되는 알고리즘(Dynamic Programming(DP), BLAST, FASTA)들 중에서 정확성을 보장하는 DP 알고리즘이 큰 데이터베이스에 적용될 때 발생시킬 수 있는 비용증가(O((n<SUP>*</SUP>m)) 문제를 해결하고자 하였다. DP알고리즘은 행렬생성단계와 역추적 단계로 구성되는데 본 논문에서는 행렬생성단계의 불필요한 정렬계산을 정리와 증명을 통해 제거함으로서 전체 수행시간이 단축될 수 있도록 알고리즘을 설계하였다. 본 논문에서 설계한 알고리즘을 실험샘플에 적용한 결과 기존의 일반적인 DP방법보다 적은 연산으로 완전한 최적정렬 서열을 찾을 수 있음을 확인하였다.
요약<BR>1. 서론<BR>2. 관련 연구<BR>3. 개선된 DP 알고리즘의 설계<BR>4. 결과<BR>5. 결론 및 향후 연구과제<BR>6. 참고문헌<BR>
(0)
(0)