Methods and apparatus for performing pattern discovery and generation with respect to data sequences

• US 6,571,230 B1
• Filed: 01/06/2000
• Issued: 05/27/2003
• Est. Priority Date: 01/06/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Parida, Laxmi P.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/478,551
• Time in Patent Office: 1,237 Days
• Field of Search: 706/48, 341/55
• US Class Current: 706/48
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/20 Sequence assembly
• 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

Given an input sequence of data, a motif is a repeating pattern. The data could be a sequence of characters or sets of characters or even real values. In the first two cases, the number of motifs could potentially be exponential in the size of the input sequence and in the third case there could be uncountably infinite number of motifs. By suitably defining the notion of maximality and redundancy for any sequence with n characters, there exists only a linear (or no more than 3n) number of special motifs and every other motif can be generated from these irredundant motifs.

Claims

1. A method of detecting repeating patterns in an input data sequence, wherein the data sequence includes elements from an element alphabet, the method comprising the steps of:

obtaining the input data sequence;

constructing a set of patterns from the input data sequence, each pattern being unique and including one or more elements from the input data sequence, and each pattern having a list associated therewith representing the location of the pattern in the input data sequence;

removing a pattern from the set when the location list of the pattern is a union of the location lists of at least two other patterns in the set;

for each pair of compatible patterns in the set, constructing a new pattern which is a concatenation of the pair of compatible patterns, each new pattern having a location list associated therewith; and

storing the patterns, and associated location lists, remaining after the removing step and the new pattern constructing step as the detected repeating patterns.

2. The method of claim 1, wherein one or more patterns further include one or more don'"'"'t care positions.

3. The method of claim 1, wherein the elements of the input data sequence are characters.

4. The method of claim 1, wherein the elements of the input data sequence are character sets.

5. The method of claim 1, wherein the elements of the input data sequence are real numbers.

6. The method of claim 1, wherein no more than 3n repeating patterns are detected given an input data sequence which includes n elements.

7. The method of claim 1, wherein the first constructing step further comprises constructing the unique patterns with at least two elements such that the cardinality of the set of patterns is less than or equal to the square of the cardinality of the element alphabet multiplied by the number of elements in the input data sequence.

8. The method of claim 7, further comprising the step of constructing a graph having vertices and directed edges wherein each vertex ν

_m corresponds to a pattern m and a directed edge exists from ν

_mp to ν

_mc if _mc⊂

_mp where represents a location list.

9. The method of claim 8, wherein the removing step further comprises, for each vertex ν

_mp, considering the vertices incident on outgoing edges ν

_mc1, ν

_mc2, . . . , ν

_mcl, and when _mp is equivalent to unions of _mc1 through _mcl, then;

removing the vertex ν

_mc1 and replacing the associated pattern m_p of vertex ν

_mp with a union of m_p and m_cl, when l is equivalent to one; and

removing the vertex ν

_mp and its incident edges, when l is greater than one.

10. The method of claim 9, wherein the second constructing step further comprises:

defining a pair of patterns m_a and m_b to be compatible when the last character in m_a is equivalent to the first character in m_b;

for each pair of compatible patterns m_i, m_j, corresponding to vertices in the graph, letting ′

_mi be equivalent to the sum of _mi and the length of pattern m_i;

constructing _mnew to be equivalent to the intersection of ′

_mi and _mj; and

constructing pattern m_new when there exist compatible patterns m_i and m_j such that the union of;

(i) the sum of _mi and the length of pattern m_i minus one; and

(ii) _mj, is equivalent to _mnew, and the cardinality of _mnew is greater than or equal to a value k.

11. The method of claim 10, further comprising the step of updating the graph by introducing a vertex corresponding to pattern m_new and introducing a directed edge from ν

_mi to ν

m_new.

12. The method of claim 11, repeating the removing step and the new pattern constructing step until _mnew is empty, for every pair of compatible patterns m_i, m_j with m_new equivalent to the union of m_i and m_j.

13. The method of claim 1, wherein the stored patterns are maximal and non-redundant.

14. The method of claim 13, further comprising the step of generating patterns, from the stored patterns, which are at least one of non-maximal and redundant.

15. The method of claim 14, further comprising the step of storing the at least one of non-maximal and redundant patterns.

16. The method of claim 14, wherein the at least one of non-maximal and redundant patterns are generated in accordance with one or more annotated tries.

17. The method of claim 1, wherein the input data sequence is a protein sequence.

18. The method of claim 17, wherein the stored patterns are used in accordance with protein sequence homology detection.

19. The method of claim 1, wherein the input data sequence is obtained from a client device via a network and the first constructing step, the removing step, the second constructing step and the storing step are performed in accordance with a server coupled to the network.

20. Apparatus for detecting repeating patterns in an input data sequence, wherein the data sequence includes elements from an element alphabet, the apparatus comprising:

at least one processor operative to;

(i) obtain the input data sequence;

(ii) construct a set of patterns from the input data sequence, each pattern being unique and including one or more elements from the input data sequence, and each pattern having a list associated therewith representing the location of the pattern in the input data sequence;

(iii) remove a pattern from the set when the location list of the pattern is a union of the location lists of at least two other patterns in the set;

(iv) for each pair of compatible patterns in the set, construct a new pattern which is a concatenation of the pair of compatible patterns, each new pattern having a location list associated therewith; and

(v) store the patterns, and associated location lists, remaining after the removing operation and the new pattern constructing operation as the detected repeating patterns.

21. An article of manufacture for detecting repeating patterns in an input data sequence, wherein the data sequence includes elements from an element alphabet, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the input data sequence;

constructing a set of patterns from the input data sequence, each pattern being unique and including one or more elements from the input data sequence, and each pattern having a list associated therewith representing the location of the pattern in the input data sequence;

removing a pattern from the set when the location list of the pattern is a union of the location lists of at least two other patterns in the set;

for each pair of compatible patterns in the set, constructing a new pattern which is a concatenation of the pair of compatible patterns, each new pattern having a location list associated therewith; and

storing the patterns, and associated location lists, remaining after the removing step and the new pattern constructing step as the detected repeating patterns.