탠덤 질량 스펙트럼에서 추출된 갭 태그를 단백질데이터베이스에서 검색하는 효율적인 알고리즘
An Efficient Algorithm for Searching Gapped Tag from Tandem Mass Spectrum in Protein Database
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
단백질 동정(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
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.
참고문헌 (17)
- M. R. Wilkins, "Proteome Research: New Frontiers in Functional Genomics" (1997), Springer
- H. Steen, "The ABC's (XYZ's) of peptide sequencing, Molecular Cell Biology", Nature Reviews, 5, pp.699~711 (2004)
- B. Ma, "PEAKS: powerful software for peptide de novo sequencing by tandem mass spectrometry", Rapid Communications Mass Spectrometry, 17, pp.2337~2342 (2003)
- V. Dancik, "De novo peptide sequencing via tandem mass spectrometry", J. Comput. Biol., 6(3-4), pp.327~342 (1999)
- A. Frank, "PepNovo: de novo peptide sequencing via probabilistic network modeling", Anal. Chem, 77, pp.964~973 (2005)
- J. Eng, "An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database", J.Am.Soc.MassSpectrom, 5, pp.976~989 (1994)
- D. N. Perkins, "Probability-based protein identification by searching sequence databases using mass spectrometry data", Electrophoresis, 20, pp.3551~3567 (1999)
- S. Tanner, "InsPecT: Identification of Posttranslationally Modified Peptides from Tandem Mass Spectra", Analytical Chemistry, 77(14), pp.4626~4639 (2005)
- S. Na, "Fast Multi-blind Modification Search through Tandem Mass Spectrometry", Mol. Cell Proteomics, 11(4) (2012)
- K. Jeong, "Gapped Spectral Dictionaries and Their Applications for Database Searches of Tandem Mass Spectra", RECOMB 2010, pp.208~232 (2010)
- 송명선, "유전체 데이터를 위한 효율적인 데이터 관리자의 구현 및 성능분석", 한국차세대컴퓨팅학회 논문지, 8(1), pp.24~33 (2012), 한국차세대컴퓨팅학회
- 신영성, "암호화된 빅데이터 상에서 효율적인 질의 처리를 지원하는 Prefix 트리를 사용한 GPU 기반 병렬 질의처리 기법", 한국차세대컴퓨팅학회 논문지, 10(2), pp.19~30 (2014), 한국차세대컴퓨팅학회
- 장재우, "대용량 민감 데이터 보호를 지원하는 비트맵 기반 분산 색인구조 및 암호화 질의처리 기법", 한국차세대컴퓨팅학회 논문지, 11(2), pp.24~40 (2015), 한국차세대컴퓨팅학회
- The UniProt Consortium, "The universal protein resource (UniProt)", Nucleic Acids Res., 36, pp.D190~D195 (2008)
- N. Castellana, "Proteogenomics to discover the full coding content of genomes: A computational perspective", J. of Proteomics, 73, pp.2124~2135 (2010)
- A. Bairoch, "The SWISS-PROT protein sequence database and its supplement TrEMBL in 2000", Nucl. Acids Res, 28, pp.45~48 (2000)
- J. Elias, "Target-decoy search strategy for increased confidence in large-scale protein identifications by mass spectrometry", Nat. Methods, 4, pp.207~214 (2007)