Methods and Systems for Compressing and Comparing Genomic Data

• US 20080077607A1
• Filed: 11/08/2004
• Published: 03/27/2008
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: Mitotech LLC
• Original Assignee: Seirad Inc.
• Inventors: Aimale, Valerio, Gatawood, Joe, Bell, Callum
• Granted Patent: US 8,340,914 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

Systems and methods are disclosed for compressing and comparing data such as genomic data. The disclosed systems and methods may include selecting a segment, creating a delta representation of the segment, the delta representation comprising a script, and storing the script. Furthermore, the disclosed systems and methods may include receiving a first script comprising a compressed version of a first segment and receiving a second script comprising a compressed version of a second segment. The disclosed systems and methods may further include comparing the first script to the second script and determining if the first segment matches the second segment based upon the comparison of the first script to the second script.

Claims

1. A method for compressing data, the method comprising:

selecting a segment;

creating a delta representation of the segment, the delta representation comprising a script; and

storing the script.

2. The method of claim 1, wherein selecting the segment further comprises selecting the segment including genomic data.

3. The method of claim 1, wherein selecting the segment further comprises selecting the segment including human genomic data.

4. The method of claim 1, wherein selecting the segment further comprises selecting the segment including any nucleic acid sequences.

5. The method of claim 1, wherein selecting the segment further comprises selecting the segment including deoxyribonucleic acid data.

6. The method of claim 1, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising a script comprising a compact symbolic representation.

7. The method of claim 1, wherein creating the delta representation further comprises:

selecting a reference sequence; and

aligning the reference sequence and the segment.

8. The method of claim 7, wherein selecting the reference sequence further comprises selecting the reference sequence comprising a completed human genome.

9. The method of claim 7, wherein selecting the reference sequence further comprises selecting the reference sequence including any nucleic acid sequences.

10. The method of claim 1, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation.

11. The method of claim 1, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

12. The method of claim 1, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

13. The method of claim 1, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.

14. The method of claim 1, wherein storing the script further comprises storing the script in a relational database configured to store separate operations indicated in the script in separate tables.

15. The method of claim 1, wherein storing the script further comprises storing the script in a relational database configured to include a segment table having a one-to-many relationship with a variant table.

16. The method of claim 1, wherein storing the script further comprises storing the script in an object oriented database.

17. A method for comparing data, the method comprising:

receiving a first script comprising a compressed version of a first segment;

receiving a second script comprising a compressed version of a second segment;

comparing the first script to the second script; and

determining if the first segment matches the second segments based upon the comparison of the first script to the second script.

18. The method of claim 17, wherein at least one of the first segment and the second segment includes genomic data.

19. The method of claim 17, wherein at least one of the first segment and the second segment includes human genomic data.

20. The method of claim 17, wherein at least one of the first segment and the second segment includes deoxyribonucleic acid data.

21. The method of claim 17, wherein at least one of the first script and the second script comprises a compact symbolic representation.

22. The method of claim 17, wherein at least one of the first script and the second script comprises a delta representation.

23. The method of claim 22, wherein the delta representation was created with a reference sequence comprising a completed human genome.

24. The method of claim 22, wherein the delta representation was created with a reference sequence comprising any nucleic acid sequences.

25. The method of claim 17, wherein at least one of the first script and the second script is configured to indicate at least one operation.

26. The method of claim 17, wherein at least one of the first script and the second script is configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

27. The method of claim 17, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

28. The method of claim 17, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.

29. A system for compressing data, the system comprising:

a memory storage for maintaining a database; and

a processing unit coupled to the memory storage, wherein the processing unit is operative to

select a segment;

create a delta representation of the segment, the delta representation comprising a script; and

store the script.

30. The system of claim 29, wherein the processing unit being operative to select the segment further comprises the processing unit being operative to select the segment including genomic data.

31. The system of claim 29, wherein the processing unit being operative to select the segment further comprises the processing unit being operative to select the segment including human genomic data.

32. The method of claim 29, wherein the processing unit being operative to select the segment further comprises the processing unit being operative to select the segment including any nucleic acid sequences.

33. The system of claim 29, wherein the processing unit being operative to select the segment further comprises the processing unit being operative to select the segment including deoxyribonucleic acid data.

34. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to create the delta representation of the segment, the delta representation comprising a script comprising a compact symbolic representation.

35. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to select a reference sequence;

and

align the reference sequence and the segment.

36. The system of claim 35, wherein the processing unit being operative to select the reference sequence further comprises the processing unit being operative to select the reference sequence comprising a completed human genome.

37. The system of claim 35, wherein the processing unit being operative to select the reference sequence further comprises the processing unit being operative to select the reference sequence comprising any nucleic acid sequences.

38. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to create the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation.

39. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to create the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

40. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to create the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

41. The system of claim 29, wherein the processing unit being operative to create the delta representation further comprises the processing unit being operative to create the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.

42. The system of claim 29, wherein the processing unit being operative to store the script further comprises the processing unit being operative to store the script in a relational database configured to store separate operations indicated in the script in separate tables.

43. The system of claim 29, wherein the processing unit being operative to store the script further comprises the processing unit being operative to store the script in a relational database configured to include a segment table having a one-to-many relationship with a variant table.

44. The system of claim 29, wherein the processing unit being operative to store the script further comprises the processing unit being operative to store the script in an object oriented database.

45. A system for comparing data, the system comprising:

a memory storage for maintaining a database; and

a processing unit coupled to the memory storage, wherein the processing unit is operative to receive a first script comprising a compressed version of a first segment;

receive a second script comprising a compressed version of a second segment;

compare the first script to the second script; and

determine if the first segment matches the second segments based upon the comparison of the first script to the second script.

46. The system of claim 45, wherein at least one of the first segment and the second segment includes genomic data.

47. The system of claim 45, wherein at least one of the first segment and the second segment includes human genomic data.

48. The system of claim 45, wherein at least one of the first segment and the second segment includes deoxyribonucleic acid data.

49. The system of claim 45, wherein at least one of the first script and the second script comprises a compact symbolic representation.

50. The system of claim 45, wherein at least one of the first script and the second script comprises a delta representation.

51. The system of claim 45, wherein the delta representation was created with a reference sequence comprising a completed human genome.

52. The system of claim 45, wherein the delta representation was created with a reference sequence comprising any nucleic acid sequences.

53. The system of claim 45, wherein at least one of the first script and the second script is configured to indicate at least one operation.

54. The system of claim 45, wherein at least one of the first script and the second script is configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

55. The system of claim 45, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

56. The system of claim 45, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.

57. A computer-readable medium which stores a set of instructions which when executed performs a method for compressing data, the computer-readable medium executed by the set of instructions comprising:

selecting a segment;

creating a delta representation of the segment, the delta representation comprising a script; and

storing the script.

58. The computer-readable medium of claim 57, wherein selecting the segment further comprises selecting the segment including genomic data.

59. The computer-readable medium of claim 57, wherein selecting the segment further comprises selecting the segment including human genomic data.

60. The computer-readable medium of claim 57, wherein selecting the segment further comprises selecting the segment including any nucleic acid sequences.

61. The computer-readable medium of claim 57, wherein selecting the segment further comprises selecting the segment including deoxyribonucleic acid data.

62. The computer-readable medium of claim 57, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising a script comprising a compact symbolic representation.

63. The computer-readable medium of claim 57, wherein creating the delta representation further comprises:

selecting a reference sequence; and

aligning the reference sequence and the segment.

64. The computer-readable medium of claim 63, wherein selecting the reference sequence further comprises selecting the reference sequence comprising a completed human genome.

65. The computer-readable medium of claim 63, wherein selecting the reference sequence further comprises selecting the reference sequence comprising any nucleic acid sequences.

66. The computer-readable medium of claim 57, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation.

67. The computer-readable medium of claim 57, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

68. The computer-readable medium of claim 57, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

69. The computer-readable medium of claim 57, wherein creating the delta representation further comprises creating the delta representation of the segment, the delta representation comprising the script comprising at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.

70. The computer-readable medium of claim 57, wherein storing the script further comprises storing the script in a relational database configured to store separate operations indicated in the script in separate tables.

71. The computer-readable medium of claim 57, wherein storing the script further comprises storing the script in a relational database configured to include a segment table having a one-to-many relationship with a variant table.

72. The computer-readable medium of claim 57, wherein storing the script further comprises storing the script in an object oriented database.

73. A computer-readable medium which stores a set of instructions which when executed performs a method for comparing data, the computer-readable medium executed by the set of instructions comprising:

receiving a first script comprising a compressed version of a first segment;

receiving a second script comprising a compressed version of a second segment;

comparing the first script to the second script; and

determining if the first segment matches the second segments based upon the comparison of the first script to the second script.

74. The computer-readable medium of claim 73, wherein at least one of the first segment and the second segment includes genomic data.

75. The computer-readable medium of claim 73, wherein at least one of the first segment and the second segment includes human genomic data.

76. The computer-readable medium of claim 73, wherein at least one of the first segment and the second segment includes deoxyribonucleic acid data.

77. The computer-readable medium of claim 73, wherein at least one of the first script and the second script comprises a compact symbolic representation.

78. The computer-readable medium of claim 73, wherein at least one of the first script and the second script comprises a delta representation.

79. The computer-readable medium of claim 78, wherein the delta representation was created with a reference sequence comprising a completed human genome.

80. The computer-readable medium of claim 78, wherein the delta representation was created with a reference sequence comprising any nucleic acid sequences

81. The computer-readable medium of claim 73, wherein at least one of the first script and the second script is configured to indicate at least one operation.

82. The computer-readable medium of claim 73, wherein at least one of the first script and the second script is configured to indicate at least one operation comprising one of insert, delete, substitute, and copy.

83. The computer-readable medium of claim 73, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate a feature associated with the at least one symbol.

84. The computer-readable medium of claim 73, wherein at least one of the first script and the second script comprises at least one symbol, the at least one symbol being configured to be looked-up in a dictionary to indicate an operation associated with the at least one symbol, the operation comprising one of insert, delete, substitute, and copy.