Methods and systems for compressing and comparing genomic data

• US 8,340,914 B2
• Filed: 11/08/2004
• Issued: 12/25/2012
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: Mitotech LLC
• Original Assignee: Mitotech LLC
• Inventors: Bell, Callum J., Gatewood, Joe M., Aimale, Valerio G.
• Primary Examiner(s): ZEMAN, MARY K
• Application Number:
  US11/667,264
• Publication Number:
  US 20080077607A1
• Time in Patent Office: 2,969 Days
• Field of Search: None
• US Class Current: 702/19
• 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 comparing nucleic acid sequences, the method comprising:

receiving a first script comprising a delta representation of a first segment relative to a common reference segment, wherein the first segment comprises a nucleic acid sequence;

receiving a second script comprising a delta representation of a second segment relative to the common reference segment, wherein the second segment comprises a nucleic acid sequence;

comparing the first script to the second script using a computer processor; and

determining if the nucleic acid sequence of the first segment matches the nucleic acid sequence of second segment based upon the comparison of the first script to the second script.

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

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

4. The method of claim 1, wherein the common reference segment comprises a completed human genome.

5. The method of claim 1, wherein the common reference segment comprising a nucleic acid sequence.

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

7. The method of claim 1, 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.

8. The method of claim 1, 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.

9. The method of claim 1, 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.

10. 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 delta representation of a first segment relative to a common reference segment;

receive a second script comprising a delta representation of a second segment relative to the common reference 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.

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

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

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

14. The system of claim 10, wherein the common reference sequence comprises a completed human genome.

15. The system of claim 10, wherein the common reference sequence comprises a nucleic acid sequences.

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

17. The system of claim 10, 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.

18. The system of claim 10, 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.

19. The system of claim 10, 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.

20. A non-transitory 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 delta representation of a first segment relative to a common reference segment;

receiving a second script comprising a delta representation of a second segment relative to the common reference 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.

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

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

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

24. The computer-readable medium of claim 20, wherein the common reference sequence comprises a completed human genome.

25. The computer-readable medium of claim 20, wherein the common reference sequence comprises a nucleic acid sequences.

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

27. The computer-readable medium of claim 20, 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.

28. The computer-readable medium of claim 20, 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.

29. The computer-readable medium of claim 20, 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.