탠덤 질량 스펙트럼에서 추출된 갭 태그를 단백질 데이터베이스에서 검색하는 효율적인 알고리즘

Abstract

단백질 동정(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배 빠르게 검색할 수 있다. 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.