METHOD AND APPARATUS FOR SEARCHING PATTERN IN SEQUENCE DATA

• US 20140258327A1
• Filed: 02/28/2014
• Published: 09/11/2014
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Hyoung-Min, Hong, Seok-Jin, Roh, Yo-Han, Jeon, Joo-Hyuk
• Granted Patent: US 9,607,106 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding

Abstract

A method of searching a pattern in sequence data includes setting a plurality of interest pattern models each including an interest pattern length, an allowed mismatch value, and a minimum support; calculating a support of a candidate pattern that is generable within the interest pattern length based on the allowed mismatch value of at least one of the plurality of interest pattern models; and determining whether the support of the candidate pattern fulfills a condition of the minimum support of at least one of the plurality of interest pattern models.

Claims

1. A method of searching a pattern in sequence data, the method comprising:

setting a plurality of interest pattern models each comprising an interest pattern length, an allowed mismatch value, and a minimum support;

calculating a support of a candidate pattern that is generable within the interest pattern length of at least one of the plurality of interest pattern models based on the allowed mismatch value of at least one of the plurality of interest pattern models; and

determining whether the support of the candidate pattern fulfills a condition of the minimum support of at least one of the plurality of interest pattern models.

2. The method of claim 1, wherein the calculating of the support of the candidate pattern comprises calculating the support of a candidate pattern that is generable within a maximum interest pattern length of the plurality of the interest pattern models.

3. The method of claim 1, wherein the calculating of the support of the candidate pattern comprises, in a case where the allowed mismatch value is the same in each of the plurality of interest pattern models:

generating a set of similar patterns having a mismatch value compared to the candidate pattern within a range of the allowed mismatch value; and

calculating a support of each of the similar patterns in the set.

4. The method of claim 3, wherein the determining of whether the support of the candidate pattern fulfills the condition of the minimum support of at least one of the plurality of interest pattern models comprises determining whether a support sum of the similar patterns in the set fulfills a condition of the minimum support of each of the plurality of interest pattern models.

5. The method of claim 1, wherein the calculating of the support of the candidate pattern comprises, in a case where the allowed mismatch value is different in at least two of the plurality of interest pattern models:

generating a set of similar patterns having a mismatch value compared to the candidate pattern within a range of a maximum allowed mismatch value of the plurality of interest pattern models; and

calculating a support of each of the similar patterns in the set.

6. The method of claim 4, wherein the determining of whether the support of the candidate pattern fulfills the condition of the minimum support of at least one of the plurality of interest pattern models comprises determining, for each of the plurality of interest pattern models, whether a support sum of similar patterns in the set fulfilling a condition of the allowed mismatch value of the interest pattern model fulfills the condition of the minimum support of the interest pattern model.

7. A method of searching a pattern in sequence data, the method comprising:

setting a plurality of interest pattern models each comprising an interest pattern length, an allowed mismatch value, and a minimum support;

determining whether a support of a parent pattern is greater than or equal to the minimum support of the plurality of interest pattern models;

in a case where the support of the parent pattern is greater than or equal to the minimum support of at least one interest pattern model of the plurality of interest pattern models, calculating a support of a child pattern based on the allowed mismatch value of the at least one interest pattern model; and

determining whether the support of the child pattern fulfills a condition of the minimum support of the at least one interest pattern model.

8. The method of claim 7, wherein the calculating of the support of the child pattern comprises, in a case where a parent pattern length is less than a maximum interest pattern length of the at least one interest pattern model, calculating the support of the child pattern.

9. The method of claim 7, wherein the calculating of the support of the child pattern comprises, in a case where the allowed mismatch value is the same in each of the at least one interest pattern model:

generating a set of similar patterns within a range of the allowed mismatch value of the at least one interest pattern model; and

calculating a support of each of the similar patterns in the set.

10. The method of claim 9, wherein the determining of whether the support of the child pattern fulfills the condition of the minimum support of the at least one interest pattern model comprises determining whether a support sum of the similar patterns in the set fulfills a condition of the minimum support of each of the at least one interest pattern model.

11. The method of claim 7, wherein the calculating of the support of the child pattern comprises:

generating a set of similar patterns within a range of a maximum allowed mismatch value of the at least one interest pattern model; and

calculating a support of each of the similar patterns in the set.

12. The method of claim 10, wherein the determining of whether the support of the child pattern fulfills the condition of the one minimum support of the at least one interest pattern model comprises determining, for each of the at least one interest pattern model, whether a support sum of similar patterns in the set fulfilling a condition of the allowed mismatch value of the interest pattern model fulfills a condition of the minimum support of the interest pattern model.

13. A method of searching a pattern in sequence data, the method comprising:

setting an interest pattern model comprising an interest pattern length, an allowed mismatch value, and a minimum support;

determining whether a support of a parent pattern is greater than or equal to the minimum support; and

in a case where the support of the parent pattern is greater than or equal to the minimum support, calculating a support of a child pattern that is generable from the parent pattern using mismatch values of similar patterns of the parent pattern.

14. The method of claim 13, wherein the calculating of the support of the child pattern comprises:

generating a first set of patterns by appending a unit pattern to similar patterns of the parent pattern having a mismatch value less than the allowed mismatch value;

generating a second set of patterns by appending a unit pattern to similar patterns of the parent pattern having a mismatch value equal to the allowed mismatch value;

calculating a support of each of the patterns in the first set and the second set; and

calculating the support of the child pattern using the support of each of the patterns in the first set and the second set.

15. The method of claim 14, wherein the calculating of the support of the child pattern further comprises:

generating the child pattern by appending a unit pattern to the parent pattern;

adding a sum support of the patterns in the first set and a support of a pattern in the second set derived by appending a same unit pattern appended to the parent pattern to generate the child pattern; and

determining whether a result of the adding fulfills a condition of the minimum support.

16. The method of claim 14, further comprising, in a case where at least one child pattern derived from the parent pattern fulfills a condition of the minimum support and has a length less than the interest pattern length, calculating a mismatch value by comparing each of the at least one child fulfilling the condition of the minimum support with each of the patterns in the first set and the second set.

17. A method of searching a pattern in sequence data, the method comprising:

setting an interest pattern model comprising an interest pattern length, an allowed mismatch value, and a minimum support;

determining whether a support of a parent pattern is greater than or equal to the minimum support; and

in a case where the support of the parent pattern is greater than or equal to the minimum support, calculating a support of a child pattern that is generable from the parent pattern using mismatch values and supports of similar patterns of the parent pattern.

18. The method of claim 17, wherein the calculating of the support of the child pattern comprises:

generating a set of patterns by appending a unit pattern to similar patterns of the parent pattern having a mismatch value equal to the allowed mismatch value;

calculating a support of each of the patterns in the set; and

calculating the support of the child pattern using the support of the patterns in the set and a support of similar patterns of the parent pattern having a mismatch value less than the allowed mismatch value.

19. The method of claim 18, wherein the calculating of the support of the child pattern further comprises:

generating the child pattern by appending a unit pattern to the parent pattern; and

calculating the support of the child pattern by adding the support of each of the patterns in the set derived by appending a same unit pattern appended to the parent pattern to generate the child pattern, and the support of each of the similar patterns having the mismatch value less than the allowed mismatch value.

20. The method of claim 17, further comprising, in a case where at least one child pattern that is generable from the parent application fulfills a condition of the minimum support and has a length less than the interest pattern length:

generating a set of patterns by appending a unit pattern to similar patterns of the parent pattern having a mismatch value less than the allowed mismatch value; and

calculating a support of each of the patterns in the set.

21. An apparatus for searching a pattern in sequence data, the apparatus comprising:

an interest pattern model setter configured to set a plurality of interest pattern models each comprising an interest pattern length, an allowed mismatch value, and a minimum support;

a support calculator configured to calculate a support of a candidate pattern generable within the interest pattern length of at least one of the plurality of interest pattern models based on the allowed mismatch value of at least one of the plurality of interest pattern models; and

a determiner configured to determine whether the support of the candidate pattern fulfills a condition of the minimum support of at least one of the plurality of interest pattern models.

22. The apparatus of claim 21, wherein in a case where the allowed mismatch value is the same in each of the plurality of interest pattern models, the support calculator is further configured to:

generate a set of similar patterns having a mismatch value compared to the candidate pattern within a range of the allowed mismatch value; and

calculate a support of each of the similar patterns in the set.

23. The apparatus of claim 22, wherein the determiner is further configured to determine whether a support sum of the similar patterns in the set fulfills a condition of the minimum support of each of the plurality of interest pattern models.

24. The apparatus of claim 21, wherein in a case where the allowed mismatch value is different in at least two of the plurality of interest pattern models, the support calculator is further configured to:

generate a set of similar patterns having a mismatch value compared to the candidate pattern within a range of a maximum allowed mismatch value of the plurality of interest pattern models; and

calculate a support of each of the similar patterns in the set.

25. The apparatus of claim 24, wherein the determiner is further configured to determine, for each of the plurality of interest pattern models, whether a support sum of similar patterns in the set fulfilling a condition of the allowed mismatch value of the interest pattern model fulfills the condition of the minimum support of the interest pattern model.

26. The apparatus of claim 21, wherein, in a case where the support of the candidate pattern fulfills the condition of the minimum support of the at least one of the plurality of interest pattern models and the candidate pattern has a length less than a maximum interest pattern length of the at least one of the plurality of interest pattern models:

the support calculator is further configured to calculate a support of a child pattern that is generable from the candidate pattern using a mismatch value of each pattern of similar patterns of the candidate pattern; and

the determiner is further configured to determine whether the child pattern fulfills conditions of the at least one of the plurality of interest pattern models of which the condition of the minimum support is fulfilled by the candidate pattern.

27. A method of searching a pattern in sequence data, the method comprising:

setting a plurality of interest pattern models each comprising an interest pattern length, an allowed mismatch value, and a minimum support, wherein the allowed mismatch value is different in each of the plurality of interest pattern models;

generating all possible similar patterns of a candidate pattern within the interest pattern length;

calculating a support and a mismatch value of each of the similar patterns;

determining, for each of the plurality of interest pattern models, whether the candidate pattern fulfills conditions of the interest pattern model based on the support of only those similar patterns having a mismatch value less than or equal to the mismatch value of the interest pattern model.

28. The method of claim 27, wherein the determining comprises:

calculating a support sum of only those similar patterns having a mismatch value less than or equal to the mismatch value of the interest pattern model;

comparing the support sum with the minimum support of the interest pattern model;

in a case where the support sum is greater than or equal to the minimum support of the interest pattern model, determining that the candidate pattern fulfills the conditions of the interest pattern model; and

in a case where the support sum is less than the minimum support of the interest pattern model, determining that the candidate pattern does not fulfill the conditions of the interest pattern model.

29. The method of claim 27, wherein the minimum support is different in each of the plurality of interest pattern models.