Earticle

초록

영어

Proteomics is the study of proteins, particularly expression, structures, functions and interactions of proteins. Protein identification searches protein sequence database for given amino acid sequences. Recently, MS-GappedDictionary proposed to search the databases using gapped tags. Using this method, more candidate amino-acid sequences are found than previous method. For searching gapped tags, it takes O(n) time without database indexing and O(p) time with indexing where n is the size of database and p is the average number of gapped tags. For UniProt protein sequence database which is widely-used in general, n = 35,856,033 and p = 719, so it is really necessary to index the database to reduce time. In previous works, a gap size is limited to 500Da because it uses a lot of memory to index the database. However, the size of a gap is actually more than 500Da. We propose an efficient algorithm which searches gapped tags whose size more than 500Da in O(p) time. Our method uses the same memory, but search time is 652 and 98 times faster than original method from 501Da to 600Da and to 650Da, respectively.

한국어

단백질 동정(Protein identification)은 단백질의 기능을 분석하고 성질을 파악하기 위해 널리 사용되는 방법이며단백질을 동정하기 위해서는 아미노산 서열을 이용하여 단백질 서열 데이터베이스를 검색하는 과정이 필요하다. 최근에 갭태그를 사용하여 데이터 베이스를 검색하는 방법이 MS-GappedDictionary에서 제안되었으며 이 방법을 이용하면 기존의 방법보다 좀 더 많은 수의 후보 아미노산 서열을 검색할 수 있다. 이 방법은 데이터베이스를 인덱싱하지 않을 경우 갭태그를 검색하는데 O(n) (n은 데이터베이스의 크기) 시간이 걸리고 인덱싱을 이용하면 O(p) (p 는 갭태그의 평균개수) 시간이 필요하다. 실제로 널리 사용되는 단백질 서열 데이터베이스인 UniProt의 경우 n = 35,856,033이고 p = 719이므로 인덱싱을 이용하는 것이 필수적이다. 기존에는 인덱싱이 메모리를 많이 사용하기때문에 갭의 크기를 500Da 이하로 제한했다. 하지만 실제로 갭의 크기가 500Da보다 큰 것이 가능하다는 것을 고려하면 500Da은 제한적이다. 본 논문에서는 500Da까지만 인덱싱을 하면서도 500Da보다 큰 갭을 포함한 갭태그를O(p)에 비례하는 시간에 데이터베이스에서 검색하는 방법을 제안한다. 이 방법을 사용하면 501Da에서 600Da의갭 태그를 평균 652배 빠르게 데이터베이스를 검색할 수 있고 650Da까지는 98배 빠르게 검색할 수 있다.

목차

요약
 Abstract
 1. 서론
 2. 연구 내용
  2.1 [G1]이 아미노산 한 개일 경우
  2.2 [G1]이 아미노산 두 개일 경우
  2.3 [G1]이 아미노산 세 개 이상일 경우
  2.4 태그 조합 시간 복잡도 축소
 3. 연구 결과
  3.1 데이터베이스 인덱싱
  3.2 갭 태그를 이용한 데이터베이스 검색
 4. 결론
 참고문헌

키워드

저자

• 김현우 [ Hyunwoo Kim | 한양대학교 전자컴퓨터통신공학과 ]
• 박희진 [ Heejin Park | 한양대학교 컴퓨터공학부 ] Corresponding author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국차세대컴퓨팅학회 논문지 [THE JOURNAL OF KOREAN INSTITUTE OF NEXT GENERATION COMPUTING]

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004