Method and apparatus for searching pattern in sequence data

• US 9,607,106 B2
• Filed: 02/28/2014
• Issued: 03/28/2017
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Roh, Yo-Han, Park, Hyoung-Min, Jeon, Joo-Hyuk, Hong, Seok-Jin
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/193,320
• Publication Number:
  US 20140258327A1
• Time in Patent Office: 1,124 Days
• US Class Current: 1/1
• 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;

determining a candidate pattern that is within an interest pattern length of at least one of the plurality of interest pattern models;

controlling a processor to access a predetermined structure of the sequence data in a memory and calculate a support for the candidate pattern in the sequence data based on an allowed mismatch value of the at least one of the plurality of interest pattern models; and

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

wherein the determining of whether the support fulfills the condition of the minimum support of the 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 a 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.

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

3. The method of claim 1, wherein the controlling of the processor further comprises, in response to the allowed mismatch value being 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 for the candidate pattern fulfills the condition of the minimum support of at least one of the plurality of interest patter 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 controlling of the processor further comprises, in response to the allowed mismatch value being 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 1, wherein the calculating of the support for the candidate pattern includes calculating a sum of supports of determined similar patterns for the candidate pattern.

7. The method of claim 1, wherein the controlling of the processor to access the predetermined structure of the sequence data further comprises controlling an accessing of the predetermined structure by one or more processing devices, and the calculating of the support of the candidate pattern further comprises calculating, by at least one of the one or more processing devices, a sum of respectively determined supports, of determined similar patterns of the candidate pattern, which are based on the accessed predetermined structure,

wherein the determining of whether the support for the candidate pattern fulfills the condition further comprises determining whether the candidate pattern fulfills conditions of at least two of the plurality of interest pattern models, which have different allowed mismatch values, based on the sum.

8. The method of claim 1, wherein a calculated support for a pattern in the sequence data indicates a number of times the pattern appears in the sequence.

9. 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;

controlling a processor to calculate a support of a parent pattern in the sequence data through an accessing of a predetermined structure of the sequence data in a memory; and

in response to determining whether the support of the parent pattern is greater than or equal to the minimum support, calculating a support of a child pattern, of the parent 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,

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, for each of the at least one interest pattern model, whether a support sum of similar patterns in a 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.

10. The method of claim 9, wherein the calculating of the support of the child pattern comprises calculating the support of the child pattern in response to a parent pattern length of the parent pattern being less than a maximum interest pattern length of the at least one interest pattern model.

11. The method of claim 9, wherein the calculating of the support of the child pattern comprises, in response to the allowed mismatch value being the same in each of the at least one interest pattern model, calculating the support of the child pattern by:

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.

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

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

14. 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;

controlling a processor to calculate a support of a parent pattern, including accessing a predetermined structure of the sequence data in a memory; and

in response to determining whether the support of the parent application is greater than or equal to the minimum support, calculating a support of a child pattern of the parent pattern using mismatch values of similar patterns of the parent pattern,

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 response to at least one child pattern derived from the parent pattern fulfilling a condition of the minimum support and having 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;

controlling a processor to calculate a support of a parent pattern, including accessing a predetermined structure of the sequence data in a memory;

in response to determining whether the support of the parent pattern is greater than or equal to the minimum support, calculating a support of a child pattern of the parent pattern using mismatch values and supports of similar patterns of the parent pattern; and

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.

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 response to at least one child pattern of the parent pattern fulfilling a condition of the minimum support and having 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 comprising a processor configured to calculate a support for a candidate pattern which is within the interest pattern length of at least one of the plurality of interest pattern models, for the sequence data, through an accessing of a predetermined structure of the sequence data in a memory and 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 fulfills a condition of the minimum support of at least one of the plurality of interest pattern models,

wherein, in response to the support of the candidate pattern fulfilling the condition of the minimum support of the at least one of the plurality of interest pattern models and the candidate pattern having 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.

22. The apparatus of claim 21, wherein, in response to the allowed mismatch value being 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 response to the allowed mismatch value being 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. 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;

controlling a processor to access a predetermined structure of the sequence data in a memory and calculate a support and a mismatch value of each of the similar patterns with respect to the sequence data; and

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,

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 response to the support sum being 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 response to the support sum being 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.

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

28. 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 a candidate pattern, which is within an interest pattern length of at least one of the plurality of interest pattern models, and determining similar patterns of the candidate pattern;

controlling a processor to access a predetermined structure of the sequence data, respectively calculating support of each of the similar patterns in the sequence data, based on a minimum allowed mismatch value of the plurality of interest pattern models, and to calculate a sum of the respectively calculated supports of the similar patterns; and

determining whether the candidate pattern fulfills conditions of all of the plurality of interest pattern models based at least on the calculated sum,

wherein the calculating of the sum of the respectively determined supports of the similar patterns comprises;

calculating the sum as a first sum of respectively determined supports of similar patterns corresponding to a first interest pattern model having the minimum allowed mismatch value of the mismatch values of the plurality of interest pattern models; and

calculating a second sum of the first sum and respectively determined supports of similar patterns of the candidate pattern corresponding to a mismatch value, greater than the minimum mismatch value, of a second interest pattern model of the plurality of interest pattern models.

29. The method of claim 28, wherein the determining of whether the candidate pattern fulfills the conditions of all of the plurality of interest pattern models includes determining whether the first sum meets a minimum support of the first interest pattern model and whether the second sum meets a minimum support of the second interest pattern model.