Methods for generating sequencer-specific nucleic acid barcodes that reduce demultiplexing errors
Provided herein are compositions and methods for analyzing nucleic acids in a sample. Compositions include simple barcode sets having reduced DNA sequencing instrument-specific error rates. Methods include methods to deconvolute sequence reads from different samples.
1. A method for synthesizing a set of oligonucleotide barcodes, comprising:
(a) providing a sequencer-specific error model for a high-throughput sequencing system, generated by:
(1) using the system to sequence a plurality of training barcode sequences of length N, wherein N is at least 5, to generate a plurality of sequence reads; and
(2) for positions in the training barcode sequences, counting the number of times a nucleic acid base is observed at a particular position in a plurality of the sequence reads; and
(b) generating one or more sets of barcode sequences by:
(i) selecting one or more first nucleotide sequences from an initial set of possible nucleotide sequences, wherein the initial set of possible nucleotide sequences comprises all possible nucleotide sequences of length N (4 N sequences), and wherein N is at least 5, to form a candidate pool;
(ii) for each iteration in a plurality of iterations:
for each respective nucleotide sequence in the set of possible nucleotide sequences, determining a respective predicted error rate, θ, produced by the sequence-specific error model, for the candidate pool that further includes the respective nucleotide sequence, wherein θ is computed using the objective function:
wherein
ρ(σ i |σ j )=Σ k-0 N-1 ln[ P (σ ik |σ jk ,k )],
ρ(σ i |σ j ) is the natural log of the probability of observing sequence σ i when the actual barcode sequence supplied to the sequencer is σ j ,
M is the number of barcodes,
σ ik refers to the nucleotide at the kth position in the ith barcode sequence, and
P(σ ik |σ jk , k) is the error model associated with the sequencer, and
adding, to the candidate pool, the respective nucleotide sequence from the set of possible nucleotide sequences that minimizes the predicted error rate, θ;
(iii) iterating step (ii) to create a final candidate pool having M different nucleotide sequences, wherein M is at least 10;
(c) synthesizing the final candidate pool to produce a pool of barcodes;
(d) attaching different synthesized oligonucleotide barcodes to polynucleotide molecules in a plurality of different samples to produce barcoded samples;
(e) pooling the barcoded samples; and
(f) sequencing polynucleotide molecules in the barcoded samples with the sequencing system or a corresponding type thereof.
2. The method of claim 1 , wherein N is at least 7.
3. The method of claim 2 , wherein M is at least 50.
4. The method of claim 2 , wherein M is at least 96.
5. The method of claim 1 , wherein N is at least 10.
6. The method of claim 5 , wherein M is at least 50.
7. The method of claim 5 , wherein M is at least 96.
8. The method of claim 7 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/1,000,000.
9. The method of claim 1 , wherein N is at least 15.
10. The method of claim 1 , wherein the sequencer uses a sequencing method selected from massively parallel signature sequencing (MPSS), DNA cluster sequencing, polony sequencing, pyrosequencing, sequencing by ligation, DNA nanoball sequencing, single molecule sequencing, single molecule real time (SMRT) sequencing, or nanopore DNA sequencing.
11. The method of claim 1 , wherein the barcodes further comprise an amplification primer sequence.
12. The method of claim 1 , wherein M is at least 50.
13. The method of claim 1 , wherein M is at least 100.
14. The method of claim 1 , wherein counting comprises, for each position in the training barcode sequences and for each nucleotide in the training barcode sequences, counting the number of occurrences of each nucleotide in the sequenced reads.
15. The method of claim 1 , wherein iteratively adding a new sequence comprises adding a sequence such that the sequences of the barcodes in the candidate pool have a minimum edit distance of three.
16. The method of claim 1 , wherein iteratively adding a new sequence comprises adding a sequence such that the sequences of the barcodes in the candidate pool have a minimum edit distance of four.
17. The method of claim 1 , wherein M is at least 50.
18. The method of claim 1 , wherein M is at least 96.
19. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/1000.
20. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/10,000.
21. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/100,000.
22. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/1,000,000.
23. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/10,000,000.
24. The method of claim 1 , further comprising, in each iteration, adding to the candidate pool a respective nucleotide sequence from the set of possible nucleotide sequences when the predicted error rate of the candidate pool with the added sequence is no more than 1/100,000,000.
25. The method of claim 1 , comprising generating a plurality of sets of barcode sequences in step (b), and selecting for synthesis a final candidate pool having a predicted error rate that is in the lowest 10% of the predicted error rates of the plurality of final candidate pools.
26. The method of claim 1 , comprising generating a plurality of sets of barcode sequences in step (b), and selecting for synthesis a final candidate pool having a predicted error rate that is in the lowest 1% of the predicted error rates of the plurality of final candidate pools.
27. The method of claim 1 , comprising generating a plurality of sets of barcode sequences in step (b), and selecting for synthesis a final candidate pool having a predicted error rate that is the lowest of the predicted error rates of the plurality of final candidate pools.
28. The method of claim 1 , further comprising (g) assigning one or more sequence reads of the sequenced polynucleotide molecules to one of the samples in the plurality of different samples based on one or more corresponding barcodes of the one or more sequence reads.
29. The method of claim 1 , wherein the system uses DNA cluster sequencing.
30. A method for synthesizing a set of oligonucleotide barcodes, comprising:
(a) providing a sequencer-specific error model for a high-throughput sequencing system, generated by:
(1) using the system to sequence a plurality of training barcode sequences of length N, wherein N is at least 5, to generate a plurality of sequence reads; and
(2) for positions in the training barcode sequences, counting the number of times a nucleic acid base is observed at a particular position in a plurality of the sequence reads; and
(b) generating one or more sets of barcode sequences by:
(i) selecting one or more first nucleotide sequences from an initial set of possible nucleotide sequences of length N (4 N sequences), wherein N is at least 5, to form a candidate pool;
(ii) iteratively adding a new sequence from the set of possible nucleotide sequences to the candidate pool such that, in each iteration, a candidate pool with the added sequence produces a predicted error rate, θ, in the sequencer-specific error model, that is below a threshold value,
wherein θ is computed using the objective function:
Θ
=
∑
i
=
0
M
-
1
∑
j
=
i
+
1
M
-
1
ρ
(
σ
i
|
σ
j
)
,
wherein
ρ
(
σ
i
|
σ
j
)
=
∑
k
=
0
N
-
1
ln
[
P
(
σ
ik
|
σ
ik
,
k
)
]
,
and wherein
ρ
(
σ
i
❘
"\[LeftBracketingBar]"
σ
j
)
=
∑
k
=
0
N
-
1
ln
[
P
(
σ
ik
❘
"\[LeftBracketingBar]"
σ
jk
,
k
)
]
,
and wherein
ρ(σ i |σ j ) is the natural log of the probability of observing sequence σ i when the actual barcode sequence supplied to the sequencer is σ j ,
M is the number of barcodes,
σ ik refers to the nucleotide at the kth position in the ith barcode sequence, and
P(α ik |α jk , k) is the error model associated with the sequencer;
(iii) iterating step (ii) to create a final candidate pool having M different nucleotide sequences, wherein M is at least 10;
(c) synthesizing the final candidate pool to produce a pool of barcodes;
(d) attaching different synthesized oligonucleotide barcodes to polynucleotide molecules in a plurality of different samples to produce barcoded samples;
(e) pooling the barcoded samples; and
(f) sequencing polynucleotide molecules in the barcoded samples with the sequencing system or a corresponding type thereof.