Methods and systems for assembly of protein sequences
Methods and systems for determining amino acid sequence of a polypeptide or protein from mass spectrometry data is provided, using a weighted de Bruijn graph. Extracted and purified protein is cleaved into a mixture of peptide and then analyzed using mass spectrometry. A list of peptide sequences is derived from mass spectrometry fragment data by de novo sequencing, and amino acid confidence scores are determined from peak fragment ion intensity. A weighted de Bruijn graph is constructed for the list of peptide sequences having node weights defined by k−1 mer confidence scores. At least one contig is assembled from the de Bruijn graph by identifying node weights having the highest k−1 mer confidence scores.
1. A computer implemented system for determining amino acid sequence of a polypeptide from mass spectrometry data using weighted de Bruijn graph, the system including one or more processors and non-transitory computer readable media, the computer implemented system comprising:
a mass spectrometer configured to generate a mass spectrometry fragment ion data of peptides cleaved from the polypeptide; and
a processor configured to:
a) convert the fragment ion data into a first list of peptide sequences, wherein the peptide sequences are sequence reads of the mass spectrometry fragment ions;
b) determine an amino acid confidence score for each amino acid in the peptide sequences, wherein the amino acid confidence score is determined based on a corresponding fragment ion intensity from the mass spectrometry fragment ion data and represents a probability that an amino acid at a position in a peptide sequence is correct;
c) construct a first weighted de Bruijn graph for the first list of peptide sequences by:
identifying a k-amino acid length substring (k-mer) from the first list of peptide sequences;
identifying an adjacent k-amino acid length substring, having overlapping sequence (k−1 mer) by a length of k−1; and
generating a map of all possible k−1 mers by assigning each k−1 mer as a node and representing relationships between each k−1 mer as paths connecting the nodes, wherein nodes having multiple possible relationships are represented by junctions with multiple paths; and
assigning each path a k−1 mer confidence score determined according to Equation I:
score
(
k
-
1
mer
)
=
∑
peptides
containing
k
-
1
mer
intensity
(
peptide
)
×
(
∏
aa
in
k
-
1
mer
(
sc
ore
(
aa
)
)
weight
(
aa
)
)
1
∑
aa
in
k
-
1
mer
weight
(
aa
)
(
1
)
wherein score(k−1 mer) is the k−1 mer confidence score;
wherein intensity(peptide) is the logarithm of precursor intensity for a peptide based on the mass spectrometry fragment ion data;
wherein aa is amino acid;
wherein score(aa) is the amino acid confidence score;
wherein weight(aa) is a weight ratio, where amino acids at both ends of the k−1 mer have a higher weight than amino acids at middle positions of the k−1 mer; and
d) assemble at least one contig from the first weighted de Bruijn graph by connecting all nodes using paths having the highest k−1 mer confidence score at each junction.
2. The computer implemented system of claim 1 , wherein k is between 5 and 10.
3. The computer implemented system of claim 2 , wherein k is 6 or 7.
4. The computer implemented system of claim 1 , wherein weight(aa) is 5 for amino acids at both ends of the k−1 mer, and 1 for amino acids at middle positions of the k−1 mer.
5. The computer implemented system of claim 1 , wherein one contig is assembled from the weighted de Bruijn graph and the one contig represents a full amino acid sequence of the polypeptide.
6. The computer implemented system of claim 1 , wherein multiple contigs are assembled from the weighted de Bruijn graph and are merged into a full amino acid sequence of the polypeptide.
7. The computer implemented system of claim 1 , wherein the mass spectrometer is tandem mass spectrometer (MS/MS) or liquid chromatography tandem mass spectrometer (LC-MS/MS).
8. The computer implemented system of claim 1 , wherein the fragment data is converted into the first list of peptide sequences by de novo sequencing using PEAKS™.
9. The computer implemented system of claim 1 , wherein the a processor configured to further configured to:
generate a second list of peptide sequences by:
matching the first list of peptide sequences against candidate peptides searched from an existing sequence database, wherein the candidate peptide has a threshold of 1% False Discovery Rate (FDR);
correcting errors in the first list of peptide sequences based on a best match candidate peptide; and
assigning all amino acid confidence score as 85; and
generate a second weighted Bruijn graph or the third list of peptide sequences.
10. The computer implemented system of claim 9 , wherein the second list of peptide sequences is generated by PEAKS DB™.
11. The computer implemented system of claim 9 , wherein the a processor configured to further configured to:
generate a third list of peptide sequences by:
performing a homology search for homologous peptides using the first and second list of peptide sequences, wherein the homologous peptide has a threshold of 1% FDR;
predicting peptide sequences based on the homology search; and
assigning all amino acid confidence score as 85; and
generate a third weighted Bruijn graph for the third list of peptide sequences.
12. The computer implemented system of claim 11 , wherein the third list of peptide sequences is generated by PEAKS™ and SPIDER™.
13. The computer implemented system of claim 9 , wherein the most complete at least one contig from the first or the second weighted Bruijn graph is used to assemble a full amino acid sequence of the polypeptide.
14. The computer implemented system of claim 11 , wherein the most complete at least one contig from the first, second, or third weighted Bruijn graph is used to assemble a full amino acid sequence of the polypeptide.
15. The computer implemented system of claim 1 , wherein the polypeptide is an antibody protein.
16. A method of determining amino acid sequence of a polypeptide from mass spectrometry data by constructing a weighted de Bruijn graph, the method comprising:
a) purifying the polypeptide and cleaving the polypeptide into peptides
b) analyzing the peptides through mass spectrometry;
c) obtaining mass spectrometry fragment ion data of the peptides and converting the fragment ion data into a first list of peptide sequences, wherein the peptide sequences are sequence reads of the mass spectrometry fragment ions;
d) determining an amino acid confidence score for each amino acid in the peptide sequences, wherein the amino acid confidence score is determined based on a corresponding fragment ion intensity from the mass spectrometry fragment ion data and represents a probability that an amino acid at a position in a peptide sequence is correct;
e) constructing a first weighted de Bruijn graph for the first list of peptide sequences by:
identifying a k-amino acid length substring (k-mer) from the first list of peptide sequences;
identifying an adjacent k-amino acid length substring, having overlapping sequence by a length of k−1 (k−1 mer); and
generating a map of all possible k−1 mers by assigning each k−1 mer as a node and representing relationships between each k−1 mer as paths connecting the nodes, wherein nodes having multiple possible relationships are represented by junctions with multiple paths; and
assigning each path a k−1 mer confidence score determined according to Equation I:
score
(
k
-
1
mer
)
=
∑
peptides
containing
k
-
1
mer
intensity
(
peptide
)
×
(
∏
aa
in
k
-
1
mer
(
sc
ore
(
aa
)
)
weight
(
aa
)
)
1
∑
aa
in
k
-
1
mer
weight
(
aa
)
(
1
)
wherein score(k−1 mer) is the k−1 mer confidence score;
wherein intensity(peptide) is the logarithm of precursor intensity for a peptide based on the mass spectrometry fragment ion data;
wherein aa is amino acid;
wherein score(aa) is the amino acid confidence score;
wherein weight(aa) is a weight ratio, where amino acids at both ends of the k−1 mer have a higher weight than amino acids at middle positions of the k−1 mer; and
f) assembling at least one contig from the first weighted de Bruijn graph by connecting all nodes using paths having the highest k−1 mer confidence score at each junction.
17. The method of claim 16 , wherein k is between 5 and 10.
18. The method of claim 17 , wherein k is 6 or 7.
19. The method of claim 16 , wherein weight(aa) is 5 for amino acids at both ends of the k−1 mer, and 1 for amino acids at middle positions of the k−1 mer.
20. The method of claim 16 , wherein one contig is assembled from the weighted de Bruijn graph and the one contig represents a full amino acid sequence of the polypeptide.
21. The method of claim 16 , wherein multiple contigs are assembled from the weighted de Bruijn graph and are merged into a full amino acid sequence of the polypeptide.
22. The method of claim 16 , wherein the mass spectrometry is tandem mass spectrometry (MS/MS) or liquid chromatography tandem mass spectrometry (LC-MS/MS).
23. The method of claim 16 , wherein the fragment data is converted into the first list of peptide sequences by de novo sequencing.
24. The method of claim 23 , wherein PEAKS™ is used to convert the fragment data into the first list of peptide sequences.
25. The method of claim 16 , further comprising:
generating a second list of peptide sequences by:
matching the first list of peptide sequences against candidate peptides searched from an existing sequence database, wherein the candidate peptide has a threshold of 1% False Discovery Rate (FDR);
correcting errors in the first list of peptide sequences based on a best match candidate peptide; and
assigning all amino acid confidence score as 85; and
generating a second weighted Bruijn graph or the third list of peptide sequences.
26. The method of claim 25 , wherein the second list of peptide sequences is generated by PEAKS DB™.
27. The method of claim 25 , further comprising
generating a third list of peptide sequences by:
performing a homology search for homologous peptides using the first and second list of peptide sequences, wherein the homologous peptide has a threshold of 1% FDR;
predicting peptide sequences based on the homology search; and
assigning all amino acid confidence score as 85; and
generating a third weighted Bruijn graph for the third list of peptide sequences.
28. The method of claim 27 , wherein the third list of peptide sequences is generated by PEAKS™ and SPIDER™.
29. The method of claim 25 , wherein the most complete at least one contig from the first or the second weighted Bruijn graph is used to assemble a full amino acid sequence of the polypeptide.
30. The method of claim 27 , wherein the most complete at least one contig from the first, second, or third weighted Bruijn graph is used to assemble a full amino acid sequence of the polypeptide.
31. The method of claim 16 , wherein the polypeptide is an antibody protein.