Secure and scalable mapping of human sequencing reads on hybrid clouds

Patent metadata

Field	Value
Publication number	US-2016110500-A1
Application number	US-201514984109-A
Country	US
Kind code	A1
Filing date	Dec 30, 2015
Priority date	May 13, 2011
Publication date	Apr 21, 2016
Grant date	—

Abstract

System and methods are provided for performing privacy-preserving, high-performance, and scalable DNA read mapping on hybrid clouds including a public cloud and a private cloud. The systems and methods offer strong privacy protection and have the capacity to process millions of reads and allocate most of the workload to the public cloud at a small overall cost. The systems and methods perform seeding on the public cloud using keyed hash values of individual sequencing reads' seeds and then extend matched seeds on the private cloud. The systems and methods are designed to move the workload of read mapping from the extension stage to the seeding stage, thereby ensuring that the dominant portion of the overhead is shouldered by the public cloud.

First claim

What is claimed is:

1 . A method of analyzing a plurality of DNA sequence reads, the method comprising the steps of: obtaining a plurality of DNA sequence reads, characterized by partitioning each of a plurality of DNA sequence reads into a plurality of seeds; encrypting each of the plurality of seeds; comparing a plurality of the encrypted plurality of seeds to a reference genome; and identifying a location in the reference genome which matches the plurality of the encrypted plurality of seeds, said steps of comparing and identifying performed in a public computing environment wherein the plurality of the encrypted plurality of seeds are exposed to at least one computing network outside a user computing network.

2 . The method according to claim 1 characterized by extending the seeds from the locations in the reference genome indentified in said step of indentifying, said step of extending performed in a private computing environment wherein the seed being extended is not exposed to other computing networks outside the computing network of the user.

3 . The method according to claim 1 or 2 characterized in that the comparing step includes comparing seed combinations.

4 . The method according to any of the preceding claims characterized in that the reference genome comprises a human genome.

5 . The method according to any of the preceding claims characterized in that said step of encrypting comprises assigning keyed-hash values to each of the plurality of seeds.

6 . The method according to any of the preceding claims characterized in that the reference genome is stored in a database comprising a computer network outside the user computing network.

7 . The method according to any of the preceding claims characterized by: partitioning a least one reference genome into a plurality of unique sequence segments; identifying a plurality of indices relating to the plurality of unique sequence segments of the at least one reference genome; and recording the plurality of indices relating to the plurality of unique sequence segments in a first reference table.

8 . The method according to claim 6 characterized in that the first reference table is stored in a database comprising the computing network outside the user computing network.

9 . The method according to any of the preceding claims characterized in that said step of identifying includes recording the location, in the reference genome which matches each of the plurality of seeds, in a second reference table.

10 . The method according to claim 8 characterized in that the second reference table is stored in a database within the user computing network.

11 . The method according to any of the preceding claims, characterized in that the encrypting step includes using a cryptographic hash algorithm.

12 . The method according to any of the preceding claims, characterized in that the encrypting step includes using a version of the secure hash algorithm.

13 . The method according to any of the preceding claims, characterized in that the encrypting step includes using block cipher modes of operation.

14 . The method according to any of the preceding claims, characterized in that the encrypting step includes using electronic codebook mode or counter mode, with Rivest Cipher, Twofish, or CAST-256.

15 . A system for analyzing a plurality of DNA sequence reads, the system comprising a user computing network having a processor and a memory including a plurality of computer readable instructions stored thereon, the computer readable instructions executable by the processor such that when executed by the processor cause the processor to: obtain a plurality of DNA sequence reads, characterized by further causing the processor to partition the plurality of DNA sequence reads into a plurality of sequence seeds; encrypt at least a plurality of the seeds; send the encrypted seeds to a external computing network so that the external computing network identifies a location in the reference genome which matches the seeds and communicate the location to the user computing network, and extending a seed from a location in the reference genome identified as matching the seed by the external network.

16 . The system of claim 13 characterized by an external computing network external configured to communicate with the user computing network, the external computing network having a processor and a memory including the reference genome stored thereon and a plurality of computer executable instructions stored thereon, such that when executed by the processor cause the processor to compare at least a plurality of the seeds with a reference genome; and identify a location in the reference genome which matches the seeds and communicate the location to the user computing network.

17 . The system of claim 13 or 14 characterized in that the external computing network compares pairs of the encrypted seeds.

18 . The system of any of the preceding claims 13 - 15 characterized in that the reference genome is a human genome.

19 . The system of any of the preceding claims 13 - 16 characterized in that the encryption of the seeds comprises assigning a keyed-hash value to at least a plurality of the seeds.

20 . The system of any of the preceding claims 13 - 17 characterized in that the computer readable instructions of the user computing network, when executed by the processor, cause the processor to partition at least one reference genome into a plurality of unique sequence segments; identify a plurality of indices relating to the plurality of unique sequence segments of the at least on reference genome; and record the plurality of indices relating to the plurality of unique sequence segments in a first reference table.

21 . The system of any of the preceding claims 13 - 18 characterized in that the first reference table is stored in the memory of the user computing network.

22 . The system of any of the preceding claims 13 - 19 characterized in that the user computing network is further configured to record the location in the reference genome which matches the seeds in a second reference table.

23 . The system of any of the preceding claims 13 - 20 characterized in that the second reference table is stored in the memory of the user computing network.

24 . A method of analyzing a plurality of DNA sequence reads, the method comprising the steps of:
partitioning each of a plurality of DNA sequence reads into a plurality of seeds including at least one hash value; encrypting each of the plurality of seeds; comparing the at least one hash value to a corresponding hash value in a reference genome; identifying a location in the reference genome which matches the at least one hash value, said steps of comparing and identifying performed in a public computing environment wherein the plurality of the encrypted plurality of seeds are exposed to at least one computing network outside a user computing network; extending the seeds from the locations in the reference genome indentified in said step of indentifying, said step of extending performed in a private computing environment wherein the seed being extended is not exposed to other computing networks outside the computing network of the user.

25 . A computer-readable medium storing a plurality of computer instructions to perform the methods of any of claims 1 - 14 and 24 .

Assignees

• Univ Indiana Res & Tech Corp

Inventors

• Wang Xiaofeng
• Tang Haixu
• Chen Yangyi
• Peng Bo

Classifications

• G06F19/22 Primary

  Physics · mapped topic

• H04L9/0637

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• G06F19/28

  Physics · mapped topic

• G16B50/40

  Encryption of genetic data · CPC title