# De novo peptide sequencing

In mass spectrometry, de novo peptide sequencing is the method in which a peptide amino acid sequence is determined from tandem mass spectrometry.
Knowing the amino acid sequence of peptides from a protein digest is essential for studying the biological function of the protein. In the old days, this was accomplished by the Edman degradation procedure. Today, analysis by a tandem mass spectrometer is a more common method to solve the sequencing of peptides. Generally, there are two approaches: database search and de novo sequencing. Database search is a simple version as the mass spectra data of the unknown peptide is submitted and run to find a match with a known peptide sequence, the peptide with the highest matching score will be selected. This approach fails to recognize novel peptides since it can only match to existing sequences in the database. De novo sequencing is an assignment of fragment ions from a mass spectrum. Different algorithms are used for interpretation and most instruments come with de novo sequencing programs.

## Peptide fragmentation

Peptides are protonated in positive-ion mode. The proton initially locates at the N-terminus or a basic residue side chain, but because of the internal solvation, it can move along the backbone breaking at different sites which result in different fragments. The fragmentation rules are well explained by some publications.
Three different types of backbone bonds can be broken to form peptide fragments: alkyl carbonyl (CHR-CO), peptide amide bond (CO-NH), and amino alkyl bond (NH-CHR).

### Different types of fragment ions

When the backbone bonds cleave, six different types of sequence ions are formed as shown in Fig. 1. The N-terminal charged fragment ions are classed as a, b or c, while the C-terminal charged ones are classed as x, y or z. The subscript n is the number of amino acid residues. The nomenclature was first proposed by Roepstorff and Fohlman, then Biemann modified it and this became the most widely accepted version.
Among these sequence ions, a, b and y-ions are the most common ion types, especially in the low-energy collision-induced dissociation (CID) mass spectrometers, since the peptide amide bond (CO-NH) is the most vulnerable and the loss of CO from b-ions.
Mass of b-ions = Σ (residue masses) + 1 (H$^+$)
Mass of y-ions = Σ (residue masses) + 19 (H$_2$O+H$^+$)
Mass of a-ions = mass of b-ions – 28 (CO)
Double backbone cleavage produces internal ions, acylium-type like H$_2$N-CHR$^2$-CO-NH-CHR$^3$-CO+ or immonium-type like H$_2$N-CHR$^2$-CO-NH$^+$=CHR$^3$. These ions are usually disturbance in the spectra.
Further cleavage happens under high-energy CID at the side chain of C-terminal residues, forming d$_n$, v$_n$, w$_n$-ions.

### Fragmentation rules summary

Most fragment ions are b- or y-ions. a-ions are also frequently seen by the loss of CO from b-ions.
Satellite ions(w$_n$, v$_n$, d$_n$-ions) are formed by high-energy CID.
Ser-, Thr-, Asp- and Glu-containing ions generate neutral molecular loss of water (-18).
Asn-, Gln-, Lys-, Arg-containing ions generate neutral molecular loss of ammonia (-17).
Neutral loss of ammonia from Arg leads to fragment ions (y-17) or (b-17) ions with higher abundance than their corresponding ions.
When C-terminus has a basic residue, the peptide generates (b$_{n-1}$+18) ion.
A complementary b-y ion pair can be observed in multiply charged ions spectra. For this b-y ion pair, the sum of their subscripts is equal to the total number of amino acid residues in the unknown peptide.
If the C-terminus is Arg or Lys, y$_1$-ion can be found in the spectrum to prove it.

### Methods for peptide fragmentation

In low energy collision induced dissociation (CID), b- and y-ions are the main product ions. In addition, loss of ammonia (-17 Da) is observed in fragment with RKNQ amino acids in it. Loss of water (-18 Da) can be observed in fragment with STED amino acids in it. No satellite ions are shown in the spectra.
In high energy CID, all different types of fragment ions can be observed but no losses of ammonia or water.
In electron transfer dissociation (ETD) and electron capture dissociation (ECD), the predominant ions are c, y, z+1, z+2 and sometimes w ions.
For post source decay (PSD) in MALDI, a, b, y-ions are most common product ions.
Factors affecting fragmentation are the charge state (the higher charge state, the less energy is needed for fragmentation), mass of the peptide (the larger mass, the more energy is required), induced energy (higher energy leads to more fragmentation), primary amino acid sequence, mode of dissociation and collision gas.

## Guidelines for interpretation

For interpretation, first, look for single amino acid immonium ions (H$_2$N$^+$=CHR$^2$). Corresponding immonium ions for amino acids are listed in Table 1. Ignore a few peaks at the high-mass end of the spectrum. They are ions that undergo neutral molecules losses (H$_2$O, NH$_3$, CO$_2$, HCOOH) from [M+H]$^+$ ions. Find mass differences at 28 Da since b-ions can form a-ions by loss of CO. Look for b$_2$-ions at low-mass end of the spectrum, which helps to identify y$_{n-2}$-ions too. Mass of b$_2$-ions are listed in Table 2, as well as single amino acids that have equal mass to b$_2$-ions. The mass of b$_2$-ion = mass of two amino acid residues + 1.
Identify a sequence ion series by the same mass difference, which matches one of the amino acid residue masses (see Table 1). For example, mass differences between a$_n$ and a$_{n-1}$, b$_n$ and b$_{n-1}$, c$_n$ and c$_{n-1}$ are the same. Identify y$_{n-1}$-ion at the high-mass end of the spectrum. Then continue to identify y$_{n-2}$, y$_{n-3}$... ions by matching mass differences with the amino acid residue masses (see Table 1). Look for the corresponding b-ions of the identified y-ions. The mass of b+y ions is the mass of the peptide +2 Da. After identifying the y-ion series and b-ion series, assign the amino acid sequence and check the mass. The other method is to identify b-ions first and then find the corresponding y-ions.

## Algorithms and software

Manual de novo sequencing is labor-intensive and time-consuming. Usually algorithms or programs come with the mass spectrometer instrument are applied for the interpretation of spectra.

### Development of de novo sequencing algorithms

An old method is to list all possible peptides for the precursor ion in mass spectrum, and match the mass spectrum for each candidate to the experimental spectrum. The possible peptide that has the most similar spectrum will have the highest chance to be the right sequence. However, the number of possible peptides may be large. For example, a precursor peptide with a molecular weight of 774 has 21,909,046 possible peptides. Even though it is done in the computer, it takes a long time.
Another method is called "subsequencing", which instead of listing whole sequence of possible peptides, matches short sequences of peptides that represent only a part of the complete peptide. When sequences that highly match the fragment ions in the experimental spectrum are found, they are extended by residues one by one to find the best matching.
In the third method, graphical display of the data is applied, in which fragment ions that have the same mass differences of one amino acid residue are connected by lines. In this way, it is easier to get a clear image of ion series of the same type. This method could be helpful for manual de novo peptide sequencing, but doesn't work for high-throughput condition.
The fourth method, which is considered to be successful, is the graph theory. Applying graph theory in de novo peptide sequencing was first mentioned by Bartels. Peaks in the spectrum are transformed into vertices in a graph called "spectrum graph". If two vertices have the same mass difference of one or several amino acids, a directed edge will be applied. The SeqMS algorithm, Lutefisk algorithm, Sherenga algorithm are some examples of this type.

### Deep Learning

More recently, deep learning techniques have been applied to solve the de novo peptide sequencing problem. The first breakthrough was DeepNovo, which adopted the convolutional neural network structure, achieved major improvements in sequence accuracy, and enabled complete protein sequence assembly without assisting databases Subsequently, additional network structures, such as PointNet (PointNovo), have been adopted to extract features from a raw spectrum. The de novo peptide sequencing problem is then framed as a sequence prediction problem. Given previously predicted partial peptide sequence, neural-network-based de novo peptide sequencing models will repeatedly generate the most probable next amino acid until the predicted peptide's mass matches the precursor mass. At inference time, search strategies such as beam search can be adopted to explore a larger search space while keeping the computational cost low. Comparing with previous methods, neural-network-based models have demonstrated significantly better accuracy and sensitivity. Moreover, with a careful model design, deep-learning-based de novo peptide sequencing algorithms can also be fast enough to achieve real-time peptide de novo sequencing. PEAKS software incorporates this neural network learning in their de novo sequencing algorithms.

### Software packages

As described by Andreotti et al. in 2012, Antilope is a combination of Lagrangian relaxation and an adaptation of Yen's k shortest paths. It is based on 'spectrum graph' method and contains different scoring functions, and can be comparable on the running time and accuracy to "the popular state-of-the-art programs" PepNovo and NovoHMM.
Grossmann et al. presented AUDENS in 2005 as an automated de novo peptide sequencing tool containing a preprocessing module that can recognize signal peaks and noise peaks.
Lutefisk can solve de novo sequencing from CID mass spectra. In this algorithm, significant ions are first found, then determine the N- and C-terminal evidence list. Based on the sequence list, it generates complete sequences in spectra and scores them with the experimental spectrum. However, the result may include several sequence candidates that have only little difference, so it is hard to find the right peptide sequence. A second program, CIDentify, which is a modified version by Alex Taylor of Bill Pearson's FASTA algorithm, can be applied to distinguish those uncertain similar candidates.
Mo et al. presented the MSNovo algorithm in 2007 and proved that it performed "better than existing de novo tools on multiple data sets". This algorithm can do de novo sequencing interpretation of LCQ, LTQ mass spectrometers and of singly, doubly, triply charged ions. Different from other algorithms, it applied a novel scoring function and use a mass array instead of a spectrum graph.
Fisher et al. proposed the NovoHMM method of de novo sequencing. A hidden Markov model (HMM) is applied as a new way to solve de novo sequencing in a Bayesian framework. Instead of scoring for single symbols of the sequence, this method considers posterior probabilities for amino acids. In the paper, this method is proved to have better performance than other popular de novo peptide sequencing methods like PepNovo by a lot of example spectra.
PEAKS is a complete software package for the interpretation of peptide mass spectra. It contains de novo sequencing, database search, PTM identification, homology search and quantification in data analysis. Ma et al. described a new model and algorithm for de novo sequencing in PEAKS, and compared the performance with Lutefisk of several tryptic peptides of standard proteins, by the quadrupole time-of-flight (Q-TOF) mass spectrometer.
PepNovo is a high throughput de novo peptide sequencing tool and uses a probabilistic network as scoring method. It usually takes less than 0.2 seconds for interpretation of one spectrum. Described by Frank et al., PepNovo works better than several popular algorithms like Sherenga, PEAKS, Lutefisk. Now a new version PepNovo+ is available.
Chi et al. presented pNovo+ in 2013 as a new de novo peptide sequencing tool by using complementary HCD and ETD tandem mass spectra. In this method, a component algorithm, pDAG, largely speeds up the acquisition time of peptide sequencing to 0.018s on average, which is three times as fast as the other popular de novo sequencing software.
As described by Jeong et al., compared with other do novo peptide sequencing tools, which works well on only certain types of spectra, UniNovo is a more universal tool that has a good performance on various types of spectra or spectral pairs like CID, ETD, HCD, CID/ETD, etc. It has a better accuracy than PepNovo+ or PEAKS. Moreover, it generates the error rate of the reported peptide sequences.
Ma published Novor in 2015 as a real-time de novo peptide sequencing engine. The tool is sought to improve the de novo speed by an order of magnitude and retain similar accuracy as other de novo tools in the market. On a Macbook Pro laptop, Novor has achieved more than 300 MS/MS spectra per second.
Pevtsov et al. compared the performance of the above five de novo sequencing algorithms: AUDENS, Lutefisk, NovoHMM, PepNovo, and PEAKS . QSTAR and LCQ mass spectrometer data were employed in the analysis, and evaluated by relative sequence distance (RSD) value, which was the similarity between de novo peptide sequencing and true peptide sequence calculated by a dynamic programming method. Results showed that all algorithms had better performance in QSTAR data than on LCQ data, while PEAKS as the best had a success rate of 49.7% in QSTAR data, and NovoHMM as the best had a success rate of 18.3% in LCQ data. The performance order in QSTAR data was PEAKS > Lutefisk, PepNovo > AUDENS, NovoHMM, and in LCQ data was NovoHMM > PepNovo, PEAKS > Lutefisk > AUDENS. Compared in a range of spectrum quality, PEAKS and NovoHMM also showed the best performance in both data among all 5 algorithms. PEAKS and NovoHMM had the best sensitivity in both QSTAR and LCQ data as well. However, no evaluated algorithms exceeded a 50% of exact identification for both data sets.
Recent progress in mass spectrometers made it possible to generate mass spectra of ultra-high resolution . The improved accuracy, together with the increased amount of mass spectrometry data that are being generated, draws the interests of applying deep learning techniques to de novo peptide sequencing. In 2017 Tran et al. proposed DeepNovo, the first deep learning based de novo sequencing software. The benchmark analysis in the original publication demonstrated that DeepNovo outperformed previous methods, including PEAKS, Novor and PepNovo, by a significant margin. DeepNovo is implemented in python with the Tensorflow framework. To represent a mass spectrum as a fixed-dimensional input to the neural-network, DeepNovo discretized each spectrum into a length 150,000 vector. This unnecessarily large spectrum representation, and the single-thread CPU usage in the original implementation, prevents DeepNovo from performing peptide sequencing in real time. To further improve efficiency of de novo peptide sequencing models, Qiao et al. proposed PointNovo in 2020. PointNovo is a python software implemented with the PyTorch framework and it gets rid of the space consuming spectrum-vector-representation adopted by DeepNovo. Comparing with DeepNovo, PointNovo managed to achieve better accuracy and efficiency at the same time by directly representing a spectrum as a set of m/z and intensity pairs.