- 크로스 링크된 단백질 서브시퀀스를 찾는 알고리즘
- ㆍ 저자명
- 김성권,Kim. Sung-Kwon
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2002년|29권 9호|pp.514-519 (6 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
단백질의 구조를 예측하는 과정에 사용될 수 있는 다음 문제를 고려한다. 길이가 n이고 원소가 모두 양수인 두 배열 A, B와 양수 M이 주어질 때, A[i]＋…A[j]＋B[k]＋…B[ι]=M이 되는 부배열 쌍 A[i]＋…A[j],$1{leq}i{leq}j{leq}n$과 B[k], …, B[l], $1{leq}k{leq}l{leq}n$을 모두 찾으시오. 본 논문에서는 이 문제를 $Ο(n^2log n+K)$ 시간에 Ο(n) 메모리를 사용하여 해결하는 알고리즘을 제시한다. 단, K는 찾은 부배열 쌍의 수이다. 기존의 결과는$Ο(n^2log +Klog n)$ 시간과 Ο(n) 메모리였다.
We are considering the following problem that can be used in the prediction of the structure of proteins. Given two length n arrays A, B with positive numbers and a positive number M, find all pairs of subarrays A[i]＋…A[j],$1{leq}i{leq}j{leq}n$ such that A[i]＋…A[j]＋B[k]＋…B[l]=M. This paper presents an algorithm with $Ο(n^2log n+K)$ time using Ο(n) memory, where K is the number of pairs output. The previously best known one is with $Ο(n^2log +Klog n)$ time and Ο(n) memory.