US 10,309,968 B2Granted

Methods and systems for assembly of protein sequences

AssigneeBioinformatics Solutions Inc.

InventorsNgoc Hieu Tran, Mohammad Ziaur Rahman, Lin He, Lei Xin, Baozhen Shan, Ming Li

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims31

Dependent claims

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.

103 more elements

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.

102 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/599,431Filed 18 May 2017 · us provisional application
Priority: 18 May 2016
Published: US 2017/0336419 A123 Nov 2017
Granted: 4 Jun 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G01N 33/6818
General methods of protein analysis not limited to specific proteins or families of proteins: sequencing of polypeptides
G01N 33/6848
General methods of protein analysis not limited to specific proteins or families of proteins: methods of protein analysis involving mass spectrometry
G01N 33/6854
Involving proteins, peptides or amino acids: immunoglobulins
G16B 30/00
Ict specially adapted for sequence analysis involving nucleotides or amino acids

Family

Application62/338,279Us provisional application · filed 18 May 2016
US 2017/0336419 A1Pre-grant publication · published 23 Nov 2017
US 10,309,968 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key