1. A method for sequencing a nucleic acid molecule, comprising:
(a) contacting a nucleic acid template, a nucleic acid primer complementary to a portion of said template, an extension enzyme, and a reversibly blocked nucleotide under conditions wherein said primer is extended to incorporate said nucleotide into a sequence complementary to said nucleic acid template,
said reversibly blocked nucleotide comprising a sugar moiety and a base moiety, wherein said base moiety is linked to a label by linker, and
wherein, attached at the position of said sugar moiety, is a reversible blocking group comprising \u2014CH2\u2014CH\u2550CH2, \u2014CH2\u2014N3, \u2014CH2\u2014S\u2014S-tBu, \u2014CH2\u2014S-Me, \u2014CH2\u2014O\u2014CH2\u2014CH2\u2014CN, \u2014CH2\u2014CH2\u2014CN, \u2014C(O)\u2014CH3, \u2014CH3, 2-nitrobenzyl, tetrahydropyran, 4-nitrobenzoyl, 2-aminobenzoyl, \u2014C(O)-linker-dye, 2-nitrobenzyl-linker-dye, \u2014C(O)\u2014O\u2014CH2\u2014CH\u2550CH-linker-dye, \u2014NH\u2014C(O)\u2014CH3, \u2014F, \u2014NH2, phosphate, or sulfate,
(b) identifying the nucleotide in said sequence complementary to said nucleic acid template;
(c1) removing or modifying the label; and
(c2) removing the blocking group,
wherein identifying said nucleotide identifies at least a portion of the sequence of said nucleic acid molecule.
2. The method of claim 1, wherein step (c1) comprises reducing a signal from the label by chemical quenching.
3. The method of claim 1, wherein step (c1) comprises reducing a signal from the label by thermal quenching.
4. The method of claim 1, wherein step (c1) comprises reducing a signal from the label by photobleaching.
5. The method of claim 1, wherein step (c1) comprises removing or modifying the label while leaving the linker intact.
6. The method of claim 1, wherein step (c1) comprises chemically or enzymatically cleaving the linker.
7. The method of claim 1, wherein said blocking group comprises a phosphate.
8. The method of claim 1, wherein said label is a fluorescent dye.
9. The method of claim 1, wherein said label comprises a ligand.
10. The method of claim 1, wherein said nucleotide molecule is a nucleotide triphosphate.
11. The method of claim 1, wherein step (c2) comprises enzymatically, photolytically andor chemically cleaving said blocking group.
12. The method of claim 1, further comprising adding a second nucleotide and repeating step (a), wherein said complementary sequence is extended and said second nucleotide is incorporated into said sequence complementary to said nucleic acid template.
13. The method of claim 7, further comprising repeating step (b), wherein identifying said second nucleotide identifies at least a portion of the sequence of said nucleic acid template.
14. The method of claim 8, further comprising repeating steps (c1) and (c2).
15. The method of claim 6, wherein steps (c1) and (c2) are carried out in the same reaction.
16. The method of claim 6, further comprising adding one or more nucleotides and repeating steps (a), (b), (c1) and (c2) one or more times, wherein at least a portion of the sequence of said nucleic acid template is determined.
17. The method of claim 1, wherein step (a) is performed by providing an extension enzyme selected from the group consisting of a polymerase, terminal transferase, reverse transcriptase, polynucleotide phosphorylase, and telomerase.
18. The method of claim 1, wherein said nucleic acid molecule comprises a primer and said primer is hybridized to a template nucleic acid.
19. The method of claim 1, wherein the sugar moiety has a blocking group attached at the 2\u2032 position.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A computer-implemented method, comprising:
encrypting counting values as a set of counting value cyphertexts according to a hidden vector encryption scheme using sample values of a set of samples, each of the samples comprising a plurality of sample values;
generating one or more tokens that are configured according to the hidden vector encryption scheme such that each token of the one or more tokens enables decryption of matching cyphertexts that match a set of one or more match values used to generate the token;
delegating processing of the counting value cyphertexts and the tokens to a remote computing environment; and
receiving count representations from the remote computing environment, each of the count representations representing a count of a set of one or more of the counting value cyphertexts whose decryption was enabled by a set of one or more of the tokens.
2. The method of claim 1, wherein encrypting the counting values comprises using the values of the set of samples to generate vectors and using the vectors to encrypt the counting values.
3. The method of claim 2, wherein the vectors comprise at least a portion of the values of the set of samples.
4. The method of claim 2, wherein the vectors comprise a set of multiple terms for each of one or more of the values of the set of samples, each set of multiple terms including a set of one or more pseudonyms.
5. The method of claim 4, further comprising summing count representations for a group of tokens generated using a set of multiple terms for one of the values of the set of samples.
6. The method of claim 1, wherein:
each of the counting values is a cyphertext encrypted using an additively homomorphic encryption scheme;
the count representations are cyphertexts encrypted according to the additively homomorphic encryption scheme; and
the method further comprises processing the count representations according to the additively homomorphic encryption scheme to produce decrypted count values.
7. The method of claim 6, further comprising:
encrypting non-counting values as a set of non-counting value cyphertexts according to the hidden vector encryption scheme, the non-counting values being encrypted using the additively homomorphic encryption scheme; and
delegating processing of the non-counting value cyphertexts to the remote computing environment along with the counting value cyphertexts;
wherein the count representations do not represent counts of the non-counting value cyphertexts.
8. The method of claim 1, wherein the remote computing environment is a map-reduce computer cluster.
9. The method of claim 1, wherein the remote computing environment is a map-reduce cluster and wherein delegating comprises delegating to the map-reduce cluster processing of a set of computer-executable instructions to perform a map-reduce operation comprising:
perform a mapping operation that comprises using each token to decrypt corresponding counting cyphertexts to produce the counting values; and
performing a reducing operation that comprises performing a summation of the counting values to produce the count representations.
10. The method of claim 9, wherein:
each of the counting values is a cyphertext encrypted using an additively homomorphic encryption scheme;
the summation of the counting values is a summation operation for summing encrypted values according to the additively homomorphic encryption scheme to produce the count representations as cyphertexts that are also encrypted according to the additively homomorphic encryption scheme; and
wherein the method further comprises processing the count representations according to the additively homomorphic encryption scheme to produce decrypted count values.
11. The method of claim 1, wherein:
the count representations comprise representations of counts of a set of samples having a plurality of attribute values for set of available attributes that can be selected for evaluation in a node of a decision tree, as well as representations of counts of classes for the set of samples; and
the method further comprises determining which of the set of available attributes to select as an attribute to be evaluated for the node, the determination of which of the set of available attributes to select comprising using the count representations.
12. The method of claim 11, wherein determining which of the plurality of attributes to select comprises computing a gain for each of the attributes using the count representations.
13. The method of claim 12, wherein:
the set of samples is a first set of samples;
the set of available attributes is a first set of available attributes;
the node is a first node;
the count representations further comprise representations of counts of a second set of samples having a plurality of attribute values for second set of available attributes that can be selected for evaluation in a second node in a same level of the decision tree as the first node, as well as representations of counts of classes for the second set of samples; and
the method further comprises determining which of the second set of available attributes to select as an attribute to be evaluated for the second node, the determination of which of the second set of available attributes to select comprising using the count representations.
14. A computer system comprising:
at least one processor; and
at least one memory comprising instructions stored thereon that when executed by the at least one processor cause the at least one processor to perform acts comprising:
receiving a set of counting value cyphertexts and a set of tokens, the counting value cyphertexts and the tokens being configured according to a hidden vector encryption scheme;
performing a map-reduce operation in a computer cluster in the computer system, the map-reduce operation comprising performing a set of operations comprising:
using one or more tokens of the set of tokens to decrypt one or more corresponding counting value cyphertexts of the set of counting value cyphertexts to produce one or more counting values; and
performing one or more summation operations of at least a portion of the counting values to produce one or more count representations, each of the one or more count representations representing a count of a set of one or more of the counting value cyphertexts whose decryption was enabled by a set of one or more of the tokens.
15. The computer system of claim 14, wherein using the one or more tokens of the set of tokens to decrypt one or more corresponding counting value cyphertexts comprises performing a plurality of mapping operations in parallel, each of the mapping operations comprising using a token of the set of tokens to decrypt one or more corresponding counting value cyphertexts of the set of counting value cyphertexts to produce one or more counting values.
16. The computer system of claim 15, wherein performing the one or more summation operations comprises performing one or more reducing operations in the computer cluster, each of the one or more reducing operations comprising performing a summation operation of at least a portion of the counting values to produce a count representation representing a count of a set of one or more of the counting value cyphertexts whose decryption was enabled by one of the one or more tokens.
17. The computer system of claim 14, wherein the counting values are encrypted according to an additively homomorphic encryption scheme, and wherein performing the one or more summation operations comprises performing one or more summation operations according to the additively homomorphic encryption scheme.
18. The computer system of claim 17, further comprising receiving a set of non-counting value cyphertexts with the counting value cyphertexts, wherein:
performing the map-reduce operation in the computer cluster comprises using one or more tokens of the set of tokens to decrypt one or more corresponding non-counting value cyphertexts of the set of counting value cyphertexts to produce one or more non-counting values, the one or more non-counting values being encrypted according to the additively homomorphic encryption scheme; and
the one or more count representations do not represent counts of the non-counting values.
19. One or more computer-readable storage media having computer-executable instructions embodied thereon that, when executed by at least one processor, cause the at least one processor to perform acts comprising:
encrypting values using an additively homomorphic encryption scheme to form counting values and non-counting values;
encrypting the counting values as a set of counting value cyphertexts according to a hidden vector encryption scheme using real values of a set of real samples to generate real vectors and using the real vectors to encrypt the counting values, the real values comprising one or more real attribute values and a real class value for each of the real samples;
encrypting the non-counting values as a set of non-counting value cyphertexts according to the hidden vector encryption scheme using fake values of a set of fake samples to generate fake vectors and using the fake vectors to encrypt the non-counting values, the fake values comprising one or more fake attribute values and a fake class value for each of the fake samples;
maintaining a data structure comprising at least a portion of a decision tree to be constructed using the set of samples;
identifying one or more nodes of the decision tree for which an attribute is to be selected for evaluation at that node;
generating one or more tokens that are configured according to a hidden vector encryption scheme such that each token of the one or more tokens enables decryption of matching cyphertexts that match a set of one or more match values used to generate the token;
delegating processing of the counting value cyphertexts, the non-counting value cyphertexts, and the tokens to a map-reduce computer cluster; and
receiving count representations from the map-reduce computer cluster, each of the count representations representing a count of a set of one or more of the counting value cyphertexts whose decryption was enabled by a set of one or more of the tokens, the count representations being cyphertexts encrypted according to the additively homomorphic encryption scheme, and the count representations not representing counts of the non-counting value cyphertexts;
processing the count representations according to the additively homomorphic encryption scheme to produce decrypted count values;
for each node of the one or more nodes, performing the following:
determining which of a set of available attributes to select as a selected attribute to be evaluated for the node, the determination of which of the set of available attributes to select comprising using at least a portion of the decrypted count values; and
configuring the decision tree to evaluate the selected attribute at the node.
20. The one or more computer-readable storage media of claim 19, wherein:
the real vectors comprise a set of multiple terms for each of one or more of the real values of the set of real samples, each set of multiple terms including a set of one or more pseudonyms;
the fake vectors comprise a set of multiple terms for each of one or more of the fake values of the set of fake samples, each set of multiple terms including a set of one or more pseudonyms; and
processing the count representations comprises summing count representations for a group of tokens generated using a set of multiple terms for one of the real values of the set of real samples.