Stochastic modeling of spatial distributed sequences

• US 7,613,572 B2
• Filed: 02/20/2002
• Issued: 11/03/2009
• Est. Priority Date: 02/20/2001
• Status: Active Grant

• Current Assignee: Context-Based 4 Casting (C-B4), Ltd.
• Original Assignee: Context-Based 4 Casting (C-B4), Ltd.
• Inventors: Morag, Gail, Shmilovici, Armin, Zinger, Gonen, Ben-Gal, Irad
• Primary Examiner(s): Brusca; John S
• Application Number:
  US10/468,101
• Publication Number:
  US 20040068332A1
• Time in Patent Office: 2,813 Days
• Field of Search: None
• US Class Current: 702/19
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids

Abstract

Apparatus for building a stochastic model of a spatially related data sequence, the data sequence comprising symbols selected from a finite symbol set, the apparatus comprising: an input for receiving said data sequence, a tree builder for expressing said symbols as a series of counters within nodes, each node having a counter for each symbol, each node having a position within said tree, said position expressing a symbol sequence and each counter indicating a number of its corresponding symbol which follows a symbol sequence of its respective node, and a tree reducer for reducing said tree to an irreducible set of conditional probabilities of relationships between symbols in said input data sequence. The tree may then be used to carry out a comparison with a new data sequence to determine a statistical distance between the old and the new data sequence.

Claims

1. An apparatus for determining statistical consistency in spatially related data, wherein said spatially related data is expressible in terms of a finite set of symbols, the apparatus comprising:

a sequence input configured for receiving a spatially related data sequence of symbols selected from said finite set;

a modeler configured for producing at least one context tree model from at least part of said data sequence, wherein said context tree model comprises a set of conditional probabilities of symbols in said sequence,

a comparator configured for calculating a statistical distance between said context tree model and a reference model, and for comparing said calculated statistical distance to a user-defined level so as to determine if said context tree model and said reference model are statistically consistent; and

an output interface configured for outputting said determination to a display, to a user, in a graphical format, or in a user readable format, thereby allowing monitoring of said spatially related data.

2. The apparatus according to claim 1, wherein said modeler comprises:

a tree builder for expressing said symbols as a series of counters within nodes in said context tree model, each node having a counter for each symbol, each node having a position within said context tree model, said position expressing a symbol sequence and each counter indicating a number of its corresponding symbol which follows a symbol sequence of its respective node, and

a tree reducer for reducing said context tree model to an irreducible set of conditional probabilities of relationships between symbols in said input data sequence.

3. The apparatus according to claim 1, said reference model being a model constructed using another part of said input spatially related data sequence.

4. The apparatus according to claim 1, said comparator comprising a statistical processor for determining a statistical distance between said context tree model and said reference model.

5. The apparatus according to claim 1, wherein said comparator comprises a statistical processor for determining a difference in statistical likelihood between said context tree model and said reference model.

6. The apparatus according to claim 1, said statistical distance being a relative complexity measure.

7. The apparatus according to claim 4, wherein said statistical distance comprises an SPRT statistic.

8. The apparatus according to claim 4, wherein said statistical distance comprises an MDL statistic.

9. The apparatus according to claim 4, wherein said statistical distance comprises a Multinomial goodness of fit statistic.

10. The apparatus according to claim 4, wherein said statistical distance comprises a Weinberger Statistic.

11. The apparatus according to claim 4, wherein said statistical distance comprises a KL statistic.

12. The apparatus according to claim 2, said tree reducer comprising a tree pruner for removing from said tree any node whose counter values are within a threshold distance of counter values of a preceding node in said tree.

13. The apparatus according to claim 12, wherein said threshold distance is user selectable.

14. The apparatus of claim 13, wherein user selectable parameters further comprise a tree maximum depth.

15. The apparatus of claim 13, wherein user selectable parameters further comprise an algorithm buffer size.

16. The apparatus of claim 13, wherein user selectable parameters further comprise a value of at least one pruning constant.

17. The apparatus of claim 13, wherein user selectable parameters further comprise a length of input sequences.

18. The apparatus of claim 13, wherein user selectable parameters further comprise an order of input symbols.

19. The apparatus according to claim 12, wherein said tree reducer further comprises a path remover operable to remove any path within said tree that is a subset of another path within said tree.

20. The apparatus according to claim 1, wherein said data comprises a nucleic acid sequence.

21. The apparatus according to claim 1, wherein said data comprises an amino-acid sequence.

22. The apparatus according to claim 1, wherein said sequential data is an output of a medical sensor sensing bodily functions.

23. The apparatus according to claim 20, wherein said nucleic acid sequence is a promoter sequence and another nucleic acid sequence is a non-promoter sequence, wherein said stochastic modeler is operable to build models of said promoter sequence and said non-promoter sequence and said comparator is operable to compare a third nucleic acid sequence with each of said models to determine whether said third sequence is a promoter sequence or a non-promoter sequence.

24. The apparatus according to claim 20, wherein said nucleic acid sequence is a coding sequence and another nucleic acid sequence is a non-coding sequence, wherein said stochastic modeler is operable to build models of said coding sequence and said non-coding sequence and said comparator is operable to compare a third nucleic acid sequence with each of said models to determine whether said third sequence is a coding sequence or a non-coding sequence.

25. The apparatus according to claim 20, wherein said nucleic acid sequence is a repetitive sequence and another nucleic acid sequence is a non-repetitive sequence, wherein said stochastic modeler is operable to build models of said repetitive sequence and said non-repetitive sequence and said comparator is operable to compare a third nucleic acid sequence with each of said models to determine whether said third sequence is a repetitive sequence or a non-repetitive sequence.

26. The apparatus according to claim 20, wherein said nucleic acid sequence is a non-coding sequence and another nucleic acid sequence is a non-non-coding sequence, wherein said stochastic modeler is operable to build models of said non-coding sequence and said non-non-coding sequence and said comparator is operable to compare a third nucleic acid sequence with each of said models to determine whether said third sequence is a non-coding sequence or a non-non-coding sequence.

27. The apparatus according to claim 4, wherein said data sequence comprises image data of a first image.

28. The apparatus according to claim 27, said distance being indicative of a statistical distribution within said image.

29. The apparatus according to claim 28, further comprising an image comparator for comparing said statistical distribution with a statistical distribution of another image.

30. The apparatus according to claim 29, said other image being of a same view as said first image taken at a different time, said distance being indicative of time dependent change.

31. The apparatus according to claim 27, said image data comprising medical imaging data, said statistical distance being indicative of deviations of said data from an expected norm.

32. The apparatus according to claim 1, applicable to a database to perform data mining on said database.

33. The apparatus according to claim 1, said stochastic model being constructed from descriptions of a plurality of enzymes for carrying out a given task, said model thereby providing a generic structural description of an enzyme for carrying out said task.

34. The apparatus according to claim 1, said model being usable to analyze results of a nucleic acid micro array.

35. The apparatus according to claim 1, said model being usable to analyze results of a protein microarray.

44. The apparatus according to claim 1, wherein said input spatially related data is representative of one of an image, a molecule and a microarray.

36. An apparatus for distinguishing between data sequences of a first kind and data sequences of a second kind, each kind being expressible in terms of a same finite set of symbols, the apparatus comprising:

a first sequence input and modeler unit configured for obtaining a set of data sequences of said first kind and building a first context tree model thereof,

a second sequence input and modeler unit configured for obtaining a set of data sequences of said second kind and building a second context tree model thereof,

a sequence input and comparison unit configured for taking a further data sequence and comparing it with each of said first and second context tree models;

the sequence input and comparison unit further configured for determining whether said further data sequence belongs to one of said first and second context tree models; and

an output unit associated with said sequence input and comparison unit and configured for outputting said determination to a display, to a user, in a graphical format, or in a user readable format thereby allowing monitoring of spatially related data.

37. The apparatus of claim 36, wherein said biological sequences are amino acid sequences.

38. The apparatus of claim 36, wherein the sequences of said first kind are nucleic acid promoter sequences.

39. The apparatus of claim 36, wherein the sequences of said first kind are nucleic acid coding sequences and the sequences of said second kind are nucleic acid non-encoding sequences.

40. The apparatus of claim 39, wherein the sequences are non-species specific, thereby constructing models which are non-species specific.

41. The apparatus of claim 36, wherein the data sequences are biological sequences.

42. The apparatus of claim 36, wherein the data sequences comprises image data of a first image.

43. The apparatus of claim 41, wherein said biological sequences are amino acid sequences.

45. The apparatus according to claim 36, applicable to a database to perform data mining on said database.