Nucleic Acids Research, 2006, Vol. 34, Web Server issue W259 types) of potential PTMs are considered. In addition, we developed a graphical tool called MassPective that shows MODi’s output in a user-friendly manner. MassPective enables a user not only to quickly view and understand MODi’s output, but also to perform additional manual de novo sequencing so that a MODi’s interpretation can be manually inspected. By incorporating MODi and MassPective with web-based interface, we have produced MODi web service. MODi web will provide the biological community a fast and convenient vehicle for identifying PTMs from tandem mass spectra. METHODS MODi consists of ﬁve stages: peak selection, tag discovery, database search, tag chain generation and PTM identiﬁcation. It assumes that the number of candidate proteins has already been reduced to 20 or less by protein identiﬁcation, before the spectra set is analyzed for PTM identiﬁcation. (i) Peak selection: We select peaks with relatively high intensities (both globally and locally). The number of peaks selected is proportional to a parent ion mass. (ii) Tag discovery: We perform partial de novo sequencing on the selected peaks to identify all the tags (partial amino acid sequences that do not contain PTMs) of length up to 3. (iii) Database search: Using the tags identified, we search the peptide database for candidate peptides that contain any of the identified tags (called forward tags) or the reverse sequences of the identified tags (called reverse tags) of length at least 3. It should be noted that the peptide database we use does not contain any PTM information. Thus the scalability requirement is satisfied. (iv) Tag chain generation: For each candidate peptide, we build a tag chain. A tag chain for a candidate peptide consists of non-overlapping forward or reverse tags of length at least 2, occurring in the candidate peptide and in-between gaps, where each gap is a maximal consecu- tive amino acid subsequence of the candidate peptide that is not covered by any tags. The difference between the mass of a gap and the size of its aligned segment of the spectrum is called mass offset for the gap. (Figure 1) (v) PTM identification: For each gap of a tag chain, we find a set of PTMs that best interprets the gap. We first enu- merate candidate sets of PTMs that correspond to the mass offset of each gap, and then select the best candidate set by comparing the partial theoretical spectra generated by each candidate set with the partial experimental spec- trum of the gap. INPUT, OUTPUT AND PARAMETERS Input MODi requires users to input spectra, protein database and PTM database. (i) Spectra. MODi can take several different formats of spec- tra: ISB mzXML format (*.xml), Thermo Finnigan dta format (possibly compressed to a *.zip format), Figure 1. A tag chain ‘__GG_glg_gga__’ for a spectrum from histone. A sequence of capital letters represents a forward tag, a sequence of small letters a reverse tag and each underline a gap. This tag chain consists of one forward tag ‘GG’, two reverse tags ‘glg’ and ‘gga’ and four gaps in between. A mass offset for a gap can be calculated by subtracting the mass of a gap from the size of its aligned segment of the spectrum. For example, the mass offset of the leftmost gap can be calculated as 41.947 Da, based on the size of aligned segment of 227.063(228.063 1) and the mass of the sequence ‘GK’ corresponding to the gap of 185.116 (Glycine: 57.021, Lysine: 128.095).