A Mixed-Integer Optimization Framework for De Novo Peptide Identification

Proteomics for the discovery of biomarkers and diagnosis of periodontitis: a critical review

Periodontitis is a common chronic and destructive disease whose pathogenetic mechanisms remain unclear. Due to their sensitivity and global scale, proteomics studies offer the opportunity to uncover critical host and pathogen activity indicators and can elucidate clinically applicable biomarkers for improved diagnosis and treatment of the disease. This review summarizes the literature of proteomics studies on periodontitis and comprehensively discusses commonly found candidate biomarkers. Key considerations in the design of an experimental proteomics platform are also outlined. The applicability of protein biomarkers across the progression of periodontitis and unexplored areas of research are highlighted.

Discovery of biomarker combinations that predict periodontal health or disease with high accuracy from GCF samples based on high-throughput proteomic analysis and mixed-integer linear optimization

AIM

To identify optimal combination(s) of proteomic based biomarkers in gingival crevicular fluid (GCF) samples from chronic periodontitis (CP) and periodontally healthy individuals and validate the predictions through known and blind test sets.

MATERIALS AND METHODS

GCF samples were collected from 96 CP and periodontally healthy subjects and analysed using high-performance liquid chromatography, tandem mass spectrometry and the PILOT_PROTEIN algorithm. A mixed-integer linear optimization (MILP) model was then developed to identify the optimal combination of biomarkers which could clearly distinguish a blind subject sample as healthy or diseased.

RESULTS

A thorough cross-validation of the MILP model capability was performed on a training set of 55 samples and greater than 99% accuracy was consistently achieved when annotating the testing set samples as healthy or diseased. The model was then trained on all 55 samples and tested on two different blind test sets, and using an optimal combination of 7 human proteins and 3 bacterial proteins, the model was able to correctly predict 40 out of 41 healthy and diseased samples.

CONCLUSIONS

The proposed large-scale proteomic analysis and MILP model led to the identification of novel combinations of biomarkers for consistent diagnosis of periodontal status with greater than 95% predictive accuracy.

PILOT_PROTEIN: identification of unmodified and modified proteins via high-resolution mass spectrometry and mixed-integer linear optimization

A novel protein identification framework, PILOT_PROTEIN, has been developed to construct a comprehensive list of all unmodified proteins that are present in a living sample. It uses the peptide identification results from the PILOT_SEQUEL algorithm to initially determine all unmodified proteins within the sample. Using a rigorous biclustering approach that groups incorrect peptide sequences with other homologous sequences, the number of false positives reported is minimized. A sequence tag procedure is then incorporated along with the untargeted PTM identification algorithm, PILOT_PTM, to determine a list of all modification types and sites for each protein. The unmodified protein identification algorithm, PILOT_PROTEIN, is compared to the methods SEQUEST, InsPecT, X!Tandem, VEMS, and ProteinProspector using both prepared protein samples and a more complex chromatin digest. The algorithm demonstrates superior protein identification accuracy with a lower false positive rate. All materials are freely available to the scientific community at http://pumpd.princeton.edu.

Novel protein identification methods for biomarker discovery via a proteomic analysis of periodontally healthy and diseased gingival crevicular fluid samples

AIM

To identify possible novel biomarkers in gingival crevicular fluid (GCF) samples from chronic periodontitis (CP) and periodontally healthy individuals using high-throughput proteomic analysis.

MATERIALS AND METHODS

Gingival crevicular fluid samples were collected from 12 CP and 12 periodontally healthy subjects. Samples were trypically digested with trypsin, eluted using high-performance liquid chromatography, and fragmented using tandem mass spectrometry (MS/MS). MS/MS spectra were analysed using PILOT_PROTEIN to identify all unmodified proteins within the samples.

RESULTS

Using the database derived from Homo sapiens taxonomy and all bacterial taxonomies, 432 human (120 new) and 30 bacterial proteins were identified. The human proteins, angiotensinogen, clusterin and thymidine phosphorylase were identified as biomarker candidates based on their high-scoring only in samples from periodontal health. Similarly, neutrophil defensin-1, carbonic anhydrase-1 and elongation factor-1 gamma were associated with CP. Candidate bacterial biomarkers include 33 kDa chaperonin, iron uptake protein A2 and phosphoenolpyruvate carboxylase (health-associated) and ribulose biphosphate carboxylase, a probable succinyl-CoA:3-ketoacid-coenzyme A transferase, or DNA-directed RNA polymerase subunit beta (CP-associated). Most of these human and bacterial proteins have not been previously evaluated as biomarkers of periodontal conditions and require further investigation.

CONCLUSIONS

The proposed methods for large-scale comprehensive proteomic analysis may lead to the identification of novel biomarkers of periodontal health or disease.

A novel approach for untargeted post-translational modification identification using integer linear optimization and tandem mass spectrometry

A novel algorithm, PILOT_PTM, has been developed for the untargeted identification of post-translational modifications (PTMs) on a template sequence. The algorithm consists of an analysis of an MS/MS spectrum via an integer linear optimization model to output a rank-ordered list of PTMs that best match the experimental data. Each MS/MS spectrum is analyzed by a preprocessing algorithm to reduce spectral noise and label potential complimentary, offset, isotope, and multiply charged peaks. Postprocessing of the rank-ordered list from the integer linear optimization model will resolve fragment mass errors and will reorder the list of PTMs based on the cross-correlation between the experimental and theoretical MS/MS spectrum. PILOT_PTM is instrument-independent, capable of handling multiple fragmentation technologies, and can address the universe of PTMs for every amino acid on the template sequence. The various features of PILOT_PTM are presented, and it is tested on several modified and unmodified data sets including chemically synthesized phosphopeptides, histone H3-(1-50) polypeptides, histone H3-(1-50) tryptic fragments, and peptides generated from proteins extracted from chromatin-enriched fractions. The data sets consist of spectra derived from fragmentation via collision-induced dissociation, electron transfer dissociation, and electron capture dissociation. The capability of PILOT_PTM is then benchmarked using five state-of-the-art methods, InsPecT, Virtual Expert Mass Spectrometrist (VEMS), Mod(i), Mascot, and X!Tandem. PILOT_PTM demonstrates superior accuracy on both the small and large scale proteome experiments. A protocol is finally developed for the analysis of a complete LC-MS/MS scan using template sequences generated from SEQUEST and is demonstrated on over 270,000 MS/MS spectra collected from a total chromatin digest.

A mixed integer linear optimization framework for the identification and quantification of targeted post-translational modifications of highly modified proteins using multiplexed electron transfer dissociation tandem mass spectrometry

Here we present a novel methodology for the identification of the targeted post-translational modifications present in highly modified proteins using mixed integer linear optimization and electron transfer dissociation (ETD) tandem mass spectrometry. For a given ETD tandem mass spectrum, the rigorous set of modified forms that satisfy the mass of the precursor ion, within some tolerance error, are enumerated by solving a feasibility problem via mixed integer linear optimization. The enumeration of the entire superset of modified forms enables the method to normalize the relative contributions of the individual modification sites. Given the entire set of modified forms, a superposition problem is then formulated using mixed integer linear optimization to determine the relative fractions of the modified forms that are present in the multiplexed ETD tandem mass spectrum. Chromatographic information in the mass and time dimension is utilized to assess the likelihood of the assigned modification states, to average several tandem mass spectra for confident identification of lower level forms, and to infer modification states of partially assigned spectra. The utility of the proposed computational framework is demonstrated on an entire LC-MS/MS ETD experiment corresponding to a mixture of highly modified histone peptides. This new computational method will facilitate the unprecedented LC-MS/MS ETD analysis of many hypermodified proteins and offer novel biological insight into these previously understudied systems.

A hybrid method for peptide identification using integer linear optimization, local database search, and quadrupole time-of-flight or OrbiTrap tandem mass spectrometry

A novel hybrid methodology for the automated identification of peptides via de novo integer linear optimization, local database search, and tandem mass spectrometry is presented in this article. A modified version of the de novo identification algorithm PILOT, is utilized to construct accurate de novo peptide sequences. A modified version of the local database search tool FASTA is used to query these de novo predictions against the nonredundant protein database to resolve any low-confidence amino acids in the candidate sequences. The computational burden associated with performing several alignments is alleviated with the use of distributive computing. Extensive computational studies are presented for this new hybrid methodology, as well as comparisons with MASCOT for a set of 38 quadrupole time-of-flight (QTOF) and 380 OrbiTrap tandem mass spectra. The results for our proposed hybrid method for the OrbiTrap spectra are also compared with a modified version of PepNovo, which was trained for use on high-precision tandem mass spectra, and the tag-based method InsPecT. The de novo sequences of PILOT and PepNovo are also searched against the nonredundant protein database using CIDentify to compare with the alignments achieved by our modifications of FASTA. The comparative studies demonstrate the excellent peptide identification accuracy gained from combining the strengths of our de novo method, which is based on integer linear optimization, and database driven search methods.