탠덤 질량 스펙트럼에서 2-PTM 검색을 위한 효율적인 알고리즘

Abstract

MODa 알고리즘은 단백질 데이터베이스와 MS/MS 데이터로부터 동적 프로그래밍을 기반으로 PTM(Post-Translational Modifications)을 포함한 펩타이드를 동정하는 알고리즘이다. MODa에는 PTM을 한 개 이하만 허용하는 OneMOD, 그리고 복수의 개수를 허용하는 MultiMOD 두 가지 버전이 있다. MultiMOD에서 동정된 펩타이드 중, 약 99%가 두 개 이하의 PTM을 가지고 있다. 이에 착안하여 두 개 이하의 PTM을 허용하는 펩타이드를 더욱 효율적으로 동정하고자 TwoMOD 버전을 고안하였다. 기존 MultiMOD의 시간 복잡도는 O(CmT^2N(L+R))이지만, TwoMOD에서는 O(CtN(L+R))로 향상시켰다. 실제 실험 결과, 기존의 MultiMOD에 비하여 약 30%의 시간이 단축되었으며, 두 개 이하의 PTM을 갖는 펩타이드도 성공적으로 동정하였다.|MODa algorithm is the algorithm for peptide identification from MS/MS data based on dynamic programming. There are two versions for MODa. First one is OneMOD which allows only less than one PTM, and the another one is MultiMOD which allows arbitrary number of PTMs. The 99% of peptide identified from MultiMOD has less than 2 PTMs. In this paper, we proposed the novel version of MODa - TwoMOD, which allows identifying the peptide that has less than 2-PTMs. We improved the time complexity from O(CmT^2N(L+R)) to O(CtN(L+R)) comparing with MultiMOD. In the experiment, the running time has been improved about 30%, and we successfully identified the peptides which has less than 2 PTMs.; MODa algorithm is the algorithm for peptide identification from MS/MS data based on dynamic programming. There are two versions for MODa. First one is OneMOD which allows only less than one PTM, and the another one is MultiMOD which allows arbitrary number of PTMs. The 99% of peptide identified from MultiMOD has less than 2 PTMs. In this paper, we proposed the novel version of MODa - TwoMOD, which allows identifying the peptide that has less than 2-PTMs. We improved the time complexity from O(CmT^2N(L+R)) to O(CtN(L+R)) comparing with MultiMOD. In the experiment, the running time has been improved about 30%, and we successfully identified the peptides which has less than 2 PTMs.