Exhaustively Identifying Cross-Linked Peptides with a Linear Computational Complexity.

Chemical cross-linking coupled to mass spectrometry is a powerful tool to study protein-protein interactions and protein conformations. Two linked peptides are ionized and fragmented to produce a tandem mass spectrum. In such an experiment, a tandem mass spectrum contains ions from two peptides. The peptide identification problem becomes a peptide-peptide pair identification problem. Currently, most tools do not search all possible pairs due to the quadratic time complexity. Consequently, missed findings are unavoidable. In our previous work, we developed a tool named ECL to search all pairs of peptides exhaustively. Unfortunately, it is very slow due to the quadratic computational complexity, especially when the database is large. Furthermore, ECL uses a score function without statistical calibration, while researchers1-3 have proposed that it is inappropriate to directly compare uncalibrated scores because different spectra have different random score distributions. Here we propose an advanced version of ECL, named ECL2. It achieves a linear time and space complexity by taking advantage of the additive property of a score function. It can search a data set containing tens of thousands of spectra against a database containing thousands of proteins in a few hours. Comparison with other five state-of-the-art tools shows that ECL2 is much faster than pLink, StavroX, ProteinProspector, and ECL. Kojak is the only one that is faster than ECL2, but Kojak does not exhaustively search all possible peptide pairs. The comparison shows that ECL2 has the highest sensitivity among the state-of-the-art tools. The experiment using a large-scale in vivo cross-linking data set demonstrates that ECL2 is the only tool that can find the peptide-spectrum matches (PSMs) passing the false discovery rate/q-value threshold. The result illustrates that the exhaustive search and a well-calibrated score function are useful to find PSMs from a huge search space.

In planta chemical cross-linking and mass spectrometry analysis of protein structure and interaction in Arabidopsis.

Site-specific chemical cross-linking in combination with mass spectrometry analysis has emerged as a powerful proteomic approach for studying the three-dimensional structure of protein complexes and in mapping protein-protein interactions (PPIs). Building on the success of MS analysis of in vitro cross-linked proteins, which has been widely used to investigate specific interactions of bait proteins and their targets in various organisms, we report a workflow for in vivo chemical cross-linking and MS analysis in a multicellular eukaryote. This approach optimizes the in vivo protein cross-linking conditions in Arabidopsis thaliana, establishes a MudPIT procedure for the enrichment of cross-linked peptides, and develops an integrated software program, exhaustive cross-linked peptides identification tool (ECL), to identify the MS spectra of in planta chemical cross-linked peptides. In total, two pairs of in vivo cross-linked peptides of high confidence have been identified from two independent biological replicates. This work demarks the beginning of an alternative proteomic approach in the study of in vivo protein tertiary structure and PPIs in multicellular eukaryotes.