Method for solving frequency, frequency distribution and sequence-matching problems using multidimensional attractor tokens

• US 7,061,491 B2
• Filed: 06/03/2002
• Issued: 06/13/2006
• Est. Priority Date: 06/03/2002
• Status: Expired due to Fees

• Current Assignee: Omnikon Technologies Ltd.
• Original Assignee: Omnikon Technologies Ltd.
• Inventors: Happel, Kenneth M.
• Primary Examiner(s): Chauhan, Ulka
• Assistant Examiner(s): Santiago, Enrique L.
• Application Number:
  US10/161,891
• Publication Number:
  US 20040107059A1
• Time in Patent Office: 1,471 Days
• Field of Search: None
• US Class Current: 345/440
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

An improved method is provided for solving sequence matching and comparison problems using attractor-based processes to extract identity tokens that indicate sequence and subsequence symbol content and order. These attractor processes map the sequence from its original sequence representation space (OSRS) into a hierarchical multidimensional attractor space (HMAS). The HMAS can be configured to represent equivalent symbol distributions within two symbol sequences or perform exact symbol sequence matching. The mapping process results in each sequence being drawn to an attractor in the HMAS. Each attractor within the HMAS forms a unique token for a group of sequences with no overlap between the sequence groups represented by different attractors. The size of the sequence groups represented by a given attractor can be reduced from approximately half of all possible sequences to a much smaller subset of possible sequences. The mapping process is repeated for a given sequence so that tokens are created for the whole sequence and a series of subsequences created by repeatedly removing a symbol from the one end of sequence and then repeating the process from the other end. The resulting string of tokens represents the exact identity of the whole sequence and all its subsequences ordered from each end.

Claims

1. A method for determining a combinatorial identity of a source set from a source multiset space, said source multiset having a plurality of elements comprising the steps of:

a) configuring a device in at least one of hardware, firmware and software to carry out an attractor process for mapping said source multiset to an attractor space, said attractor process being an iterative process which cause said plurality of elements to converge on one of at least two different behaviors defined within said attractor space as a result of said iterative process, said configuring step including inputting a characterization of the source multiset to input to said device the number of distinct elements of said source multiset;

b) using said device, executing said mapping of said plurality of elements of said source multiset to one or more coordinates of said attractor space;

c) mapping said attractor space coordinates into a target space representation, said target space representation including at least the attractor space coordinates;

d) storing the representation from said target space.

2. The method of claim 1 wherein said target space and said attractor space are collapsed onto a single space.

3. The method of claim 1 further comprising the step of:

(e) mapping said target space representation into an analytical space for evaluation to determine the source set'"'"'s combinatorial identity.

4. The method of claim 3 wherein two or more of said target space, said analytic space and said attractor space are collapsed onto a single space.

5. The method of claim 1 wherein said configuring step includes counting the number of distinct elements.

6. The method of claim 5 wherein said configuring step includes choosing a number of distinct symbols for a particular grouping of said plurality of elements.

7. The method of claim 6 wherein the configuring step includes assigning symbol groups to said counted number of distinct elements and counting the number of distinct symbols within each symbol group.

10. The method of claim 6 wherein two or more of said target space, said analytic space and said attractor space are collapsed onto a single space.

11. The method of claim 6 wherein the pre-determined value is zero.

8. A method for recognizing the identity of a family of permutations of a source multiset in a space of multisets containing combinations of set elements, repeat elements, and permutations of those combinations of set elements and repeat elements, said method comprising the steps of:

a) configuring a device in at least one of hardware, firmware and software to carry out an attractor process for mapping said source multiset to an attractor space, said attractor process being an iterative process which causes said plurality of elements to converge on one of at least two different behaviors defined within said attractor space as a result of said iterative process, said configuring step including inputting a characterization of the source multiset to input to said device the number of distinct elements of said source multiset;

b) using said device, executing said mapping of said plurality of elements, N, of said multiset to one or more coordinates in said attractor space;

c) mapping said attractor space coordinates as part of an accumulation of attractor space coordinates into a target space representation, said target space representation including at least the attractor space coordinates, said target space being designed to provide representational structure to the accumulation of attractor space coordinates;

d) removing one or more elements as a group from the source multiset to form a source multiset with N=N−

1 element groups;

e) repeating steps b), c) and d) until N is less than a pre-determined value;

f) mapping said target space representation into an analytic space to determine the source multiset'"'"'s combinatorial identity, said analytic space including at least the attractor space coordinate and an identification of said source multiset;

g) storing a representation of said analytic space.

9. The method of claim 8 further comprising the step of:

h) evaluating said stored representation of said analytic space to determine a permutation family of said source multiset.

12. The method of claim 8 further comprising the step of:

h) determining if the source multiset representation is mapped to a unique set in said analytic space and if it is not, repeat steps a) through h) until said representation is unique and for each such repetition, inputting a different characterization of the source multiset to input to said device the number of distinct elements by grouping said elements to form distinct groups and counting each distinct group as one element.

13. A method of analytical symbol creation for describing, detecting, matching, recognizing, identifying, correlating, evaluating, analyzing, and labeling frequency, frequency distribution, waveform, signal attribute or sequence patterns, comprising:

mapping a plurality of patterns or embedded parts or fractional parts thereof or any combinations of the same from an original representation space (ORS) into a hierarchical multidimensional attractor behavior space (HMBS), to draw the patterns or embedded parts or fractional parts thereof or any combinations of the same, respectively, to a plurality of resultant attractor behaviors in the HMBS, wherein each of the resultant attractor behaviors forms an identity for a group of patterns or embedded parts or fractional parts thereof or any combinations of the same;

mapping each attractor behavior identity to a specific analytical symbol that is part of an analytical symbol scheme;

mapping said analytical symbol to create a spatial coordinate in a space, a group of spaces or a hierarchy of spaces.

14. The method of claim 13 wherein the step of mapping a plurality of patterns or embedded parts or fractional parts thereof or any combinations of the same further comprises:

repeating the step of mapping to include a plurality of portions of a predetermined pattern to create a string of analytical symbols for the pattern and respective portions;

mapping said analytical symbol string to create a series of spatial coordinates in a space, a group of spaces, or a hierarchy of spaces.

15. The method of claim 13 wherein the step of mapping a plurality of patterns or embedded parts or fractional parts thereof or any combinations of the same further comprises:

repeating the step of mapping to include a plurality of portions of a predetermined pattern to create a string of analytical symbols for the pattern and respective portions, the plurality of portions being created by removing a predetermined pattern piece from a predetermined reference location within the pattern, the predetermined pattern piece and predetermined reference location being individually selected for each portion;

mapping said analytical symbol string to create a series of spatial coordinates in a space, group of spaces or a hierarchy of spaces.

16. The method of claim 13 wherein the step of mapping a plurality of patterns or embedded parts or fractional parts thereof or any combinations of the same further comprises:

repeating the step of mapping to include a plurality of portions of a predetermined pattern to create a string of analytical symbols for the pattern and respective portions, the plurality of portions being created;

by removing a predetermined pattern piece from a predetermined reference location within the pattern,

then removing a predetermined pattern piece from a predetermined reference location within the portion previously created,

then repeating the previous step at least one time,

the predetermined pattern piece and predetermined reference location being individually selected for each portion;

mapping said analytical symbol string to create a series of spatial coordinates in a space, a group of spaces, or a hierarchy of spaces.

17. The method of claim 13 wherein the step of mapping a plurality of patterns or embedded parts or fractional parts thereof or any combinations of the same further comprises:

repeating the step of mapping to include a plurality of portions of a predetermined pattern to create a string of analytical symbols for the pattern and respective portions, the plurality of portions being created;

by removing a predetermined pattern piece from a predetermined reference location within the pattern,

then removing the same predetermined pattern piece from the same predetermined reference location within the portion previously created,

then repeating the previous step at least one time;

mapping said analytical symbol string to create a series of spatial coordinates in a space, a group of spaces, or a hierarchy of spaces.

18. The method of claim 13 wherein the space comprises a member of a plurality of spaces.

19. The method of claim 18, wherein the plurality of spaces comprises a plurality of hierarchical embedded pattern spaces.

20. The method of claim 19, wherein the embedded pattern spaces each comprise a plurality of pattern sub-spaces.

21. The method of claim 19, wherein the embedded pattern spaces comprise Hausdorf spaces.

22. The method of claim 19, wherein the step of mapping said analytical symbol string comprises mapping said analytical symbol string symbols to spatial vectors in the embedded pattern spaces.

23. The method of claim 22, wherein the step of comparing the sequence-similarity characteristics comprises comparing the spatial vectors of said at least two of the sequences.

24. The method of claim 18, wherein the plurality of spaces comprise a plurality of hierarchical numerical spaces.

25. The method of claim 24, wherein the step of mapping said analytical symbol string comprises mapping said string of analytical symbols to coordinate values in the numerical spaces.

26. The method of claim 25, wherein the step of comparing the sequence-similarity characteristics comprises evaluating a numerical distance of the coordinate values of said at least two of the sequences.

27. The method of claim 18, wherein the space comprises a member of a plurality of hierarchical set-theoretic spaces having a plurality of layer coordinates.

28. The method of claim 27, wherein the step of mapping said string of analytical symbols comprises mapping said string of analytical symbols to coordinate values in the layer coordinates of the set-theoretic spaces.

29. The method of claim 28, wherein the step of comparing the sequence-similarity characteristics comprises evaluating an arithmetic distance between analytical symbols or analytical symbol strings of each of the layer coordinates representing at least two of the sequences.

30. The method of claim 13, further comprising assigning a label to each of the subsequences.

31. The method of claim 30, further comprising the step of assigning a plurality of labels for a plurality of subsequences within the given sequence to a label set.

32. The method of claim 31, wherein the spaces comprises hierarchical set-theoretic spaces, further comprising assigning a plurality of label sets to a plurality of hierarchical label spaces.

33. The method of claim 32, further comprising the step of sorting the label sets into groups of predetermined content and content order in a classification space.

34. The method of claim 33, wherein the label sets are organized into branch structures, wherein the branch structures of different sequences are compared to one another.

35. The method of claim 13, wherein the patterns comprise the nucleotide sequences forming deoxyribonucleic acid (DNA) or related neuclotide composed molecules such as RNA.

36. The method of claim 13, wherein the patterns comprise waveform features forming an analog signal.

37. The method of claim 13, wherein the patterns comprise periodically recurring subpatterns whose cardinality in a second is evaluated as frequency expressed in Hertz.

38. The method of claim 13, wherein the patterns comprise amino acid sequences forming proteins or related molecules composed of amino acid sequences.

39. A method of sequence matching, comprising:

mapping a plurality of sequences from an original representation space (ORS) comprised of sequences into a hierarchical multidimensional attractor behavior space (HMBS), to draw the sequences respectively to a plurality of attractor behaviors in the HMBS, wherein each of the attractor behaviors forms a unique identity for a given group of said sequences with no overlap between different groups of sequences represented by different attractor behaviors, then mapping the attractor identity to an analytical symbol that is part of an analytical symbol scheme;

repeating the step of mapping a plurality of subsequences of a given one of the sequences to create a string of analytical symbols for the given sequence and the subsequences, the step of mapping the subsequences comprising repeatedly removing a sequence element from the first end of the given sequence, the resulting string of analytical symbols representing an exact identity of the given sequence and all of the subsequences ordered from the first end of the given sequence;

repeating the step of mapping a plurality of subsequences of a given one of the sequences to create a string of analytical symbols for the given sequence and the subsequences, the step of mapping the subsequences comprising repeatedly removing a sequence element from the second end of the given sequence, the resulting string of analytical symbols representing an exact identity of the given sequence and all of the subsequences ordered from the second end of the given sequence;

repeating the step of mapping a plurality of subsequences for each subsequence created above forming two groups of analytical symbol strings each composed of an analytical symbol sequence for the sequence and each subsequence with one group comprising those analytical symbol strings created by first end sequence element removal and the second group comprising those analytical symbol strings created by second end sequence element removal;

mapping said groups of analytical symbol strings to create a series of spatial coordinates in a hierarchy of spaces; and

evaluating sequence-similarity characteristics of at least two strings of analytical symbols on from the first end of the sequence in a space, a group of spaces or a hierarchy of spaces to compare at least two of the sequences.

40. A method of sequence matching comprising:

a) mapping a first sequence having a plurality of sequence elements from an original representation space (ORS) into a multidimensional attractor behavior space (HMBS), said first sequence converging to one of at least two distinct behaviors in said attractor behavior space, wherein each behavior is assigned a unique analytical symbol from an analytical symbol scheme, such that the first sequence convergence and analytical symbol assignment is the first analytical symbol;

b) forming a plurality of subsequences of said first sequence; and

c) mapping said plurality of subsequences of said first sequence to said HMBS space to create a plurality of analytical symbols corresponding to the behavior of each subsequence, said first analytical symbol and said plurality of analytical symbols defining together a first analytical symbol string uniquely characterizing said first sequence including its subsequences;

wherein the step of forming a plurality of subsequences comprising;

1) removing a sequence element from a first end of the first sequence to produce a subsequence;

2) iteratively repeating step

     1) for the produced subsequence to form subsequent subsequences;

3) removing a symbol from a second end of the first sequence to produce another subsequence;

4) iteratively repeating step

     3) for the produced subsequence to form subsequent other subsequences,

d) ordering said first analytical symbol string to produce an ordered first analytical symbol string; and

e) repeating steps a)–

d) for a second sequence to obtain an ordered second analytical symbol string;

f) said first and second analytical symbol string representing an exact identity of the first and second sequences respectively and all subsequences ordered from the first and second ends of the first and second sequences; and

g) comparing the ordered first analytical symbol string with the ordered second analytical symbol string whereby a match may be detected between said first sequence and said second sequence.

41. The method as recited in claim 40 wherein for each of said first and second sequences said unique analytical symbol is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space.

42. The method as recited in claim 41 wherein for each of said subsequences of said first and second sequences said plurality of analytical symbols is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space.

43. The method as recited in claim 42 wherein for each of said subsequences of said first and second sequences said plurality of analytical symbols is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space.

44. The method as recited in claim 41 wherein for each of said first and second sequences said unique analytical symbol string is obtained by a composite of:

(a) a taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(d) removing j sequence elements, where j is an integer initially equal to one, from one end of said subsequence and, for the resulting subsequence, repeating steps a)–

c);

(e) iteratively repeating step d) at least once for j=j+1 at each iteration;

(f) removing k sequence elements, where k is an integer initially equal to one, from the other end of said subsequence and, for the resulting subsequence, repeating steps a)–

c); and

(g) iteratively repeating step f) at least once for k=k+1 at each iteration.

45. The method as recited in claim 44 wherein for each of said subsequences, said plurality of analytical symbols is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(d) removing j sequence elements, where j is an integer initially equal to one, from one end of said subsequence and, for the resulting subsequence, repeating steps a)–

c);

(e) iteratively repeating step d) at least once for j=j+1 each iteration;

(f) removing k sequence elements, where k is an integer initially equal to one, from the other end of said subsequence and, for the resulting subsequence, repeating steps a)–

c); and

(g) iteratively repeating step f) at least once for k=k+1 at each iteration.

46. The method as recited in claim 45 wherein for each of said subsequences, said plurality of analytical symbols is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(d) removing j sequence elements, where j is an integer initially equal to one, from one end of said subsequence and, for the resulting subsequence, repeating steps a)–

c);

(e) iteratively repeating step d) at least once for j=j+1 at each iteration;

(f) removing k sequence elements, where k is an integer initially equal to one, from the other end of said subsequence and, for the resulting subsequence, repeating steps a)–

c); and

(g) iteratively repeating step f) at least once for k=k+1 at each iteration;

wherein the mapping comprises;

1.) create a row sequence list,

2.) count the number of times each sequence element occurs in the sequence,

3.) express the count for each sequence element as a number within a numerical counting base, ordered with the order of the sequence elements,

4.) create a two dimensional array (the count array) with as many columns as the number of digits in a numerical counting base (not necessarily the same as the base of the numbers in the sequence element count),

a. count the number of times each digit in the base occurs within the group of numbers

b. express each digit count as a number in the base entered into the respective digit column of the count array such that the sequence of numbers in a row of the array represents the number of times each digit occurred respectively,

c. determine if the current row'"'"'s sequence of numbers occurs in any preceding row of the count array,

d. if the current row'"'"'s sequence of numbers has not occurred in any previous row of the count array repeat steps a.)–

d.),

5.) if the current row'"'"'s sequence of numbers occurs in any preceding row, copy the sequence of rows (the row sequence) and place it in the row sequence list,

6.) determine if the current row sequence has been previously placed in the row sequence list,

7.) if the current row sequence is new, assign it an unique analytical symbol from an analytical symbol scheme and place the analytical symbol in the next position of the ordered analytical symbol string for the current sequence,

8.) if the current row sequence is not new, assign the analytical symbol for the previous occurance of the row sequence to the next position in the ordered analytical symbol sequence string and erase the current row sequence from the list.

47. The method as recited in claim 45 wherein for each of said subsequences, said plurality of analytical symbols is obtained by a composite of:

(a) taking said sequence elements one at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(b) taking said sequence elements two at a time at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(c) taking said sequence elements three at a time forming analytical sequence elements and, collectively, an analytical sequence and mapping the analytical sequence to said attractor space;

(d) removing j sequence elements, where j is an integer initially equal to one, from one end of said subsequence and, for the resulting subsequence, repeating steps a)–

c);

(e) iteratively repeating step d) at least once for j=j+1 at each iteration;

(f) removing k sequence elements, where k is an integer initially equal to one, from the other end of said subsequence and, for the resulting subsequence, repeating steps a)–

c); and

(g) iteratively repeating step f) at least once for k=k+1 at each iteration;

wherein the mapping comprises;

9.) create a row sequence list,

10.) count the number of times each sequence element occurs in the sequence,

11.) express the count for each sequence element in a non-numerical form, ordered with the order of the sequence elements,

12.) create a two dimensional array (the count array) with as many columns as the base number of count symbols in said non-numerical form

a. count the number of times each count symbol occurs within the group of numbers

b. express each count symbol count in said non-numerical form entered into the respective count symbol column of the count array such that the sequence of count symbols in a row of the array represents the number of times each digit occurred respectively,

c. determine if the current row'"'"'s sequence of count symbols occurs in any preceding row of the count array,

d. if the current row'"'"'s sequence of count symbols has not occurred in any previous row of the count array repeat steps a.)–

d.),

13.) if the current row'"'"'s sequence of count symbols occurs in any preceding row, copy the sequence of rows (the row sequence) and place it in the row sequence list,

14.) determine if the current row sequence has been previously placed in the row sequence list,

15.) if the current row sequence is new, assign it an unique analytical symbol from an analytical symbol scheme and place the analytical symbol in the next position of the ordered analytical symbol string for the current sequence,

16.) if the current row sequence is not new, assign the analytical symbol for the previous occurance of the row sequence to the next position in the ordered analytical symbol sequence string and erase the current row sequence from the list.