Recently, we introduced Probability Profile Method (PPM), which utilizes neutral-loss neighborhoods around each peak in MS/MS spectrum to "label" it: to assign a probability that the peak in question belongs to one of the specific categories (such as b- or y-ion peaks). Here we present the PPM-chain program — a PPM-based tool for de novo protein tag identification. De novo peptide identification involves finding a connected sequence of ion peaks separated by amino acid mass intervals, corresponding to a tag - partial peptide of the source protein. In the existing approaches the number of the possible connected sequences may run into hundreds of thousands, and it increases exponentially with the desired length of the tag. PPM can be used to locate high probability islands, containing very pure sets of b- and y-ion peaks, thereby reducing computational complexity and sharply increasing precision of tagging. In addition, the obtained tags can be reliably ranked using PPM-derived probabilities assigned to the connected peaks. The value of peptide tags was demonstrated on a large database of ~20,000 spectra. With the additional flanking mass constraints PPMchain shows precision and coverage similar to the field industrial-power standard — Sequest program, while providing a set of novel unique capabilities and significantly outperforming Sequest in speed.