Stochastic modeling of spatial distributed sequences

• US 20040068332A1
• Filed: 08/15/2003
• Published: 04/08/2004
• 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
• Granted Patent: US 7,613,572 B2
• Time in Patent Office: Days
• US Class Current: 700/51
• 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. Apparatus for building a stochastic model of a data sequence, said data sequence comprising spatially related 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.

2. Apparatus according to claim 1, 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.

3. Apparatus according to claim 2, wherein said threshold distance and tree construction parameters are user selectable.

4. The apparatus of claim 3, wherein said user selectable parameters further comprise a tree maximum depth.

5. The apparatus of claim 3, wherein said user selectable parameters further comprise an algorithm buffer size

6. The apparatus of claim 3, wherein said user selectable parameters further comprise values of at least one pruning constants.

7. The apparatus of claim 3, wherein said user selectable parameters further comprise a length of input sequences.

8. The apparatus of claim 3 wherein, said user selectable parameters further comprise an order of input symbols.

9. Apparatus according to claim 2, 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.

10. Apparatus according to claim 1, wherein said sequential data is a string comprising consecutive symbols selected from a finite set.

11. The apparatus of claim 10, further comprising an input string permutation unit for carrying out permutations and reorganizations of the input string using external information about a process generating said string.

12. Apparatus according to claim 9, wherein said string is a nucleic acid sequence.

13. The Apparatus of claim 12, wherein said string is a promoter and said tree is operable to identify other promoters.

14. The apparatus of claim 12, wherein said string is a string of coding DNA, and said tree is operable to identify other coding strings.

15. The apparatus of claim 12, wherein said string is a string of non-coding DNA, and said tree is operable to identify other non-coding strings.

16. The apparatus of claim 12, wherein said string is a DNA string and said tree is operable to identify poly-A terminators.

17. The apparatus of claim 12, wherein said string has a given property, and said tree is operable to identify other strings having said given property.

18. Apparatus according to claim 9, wherein said string is an amino-acid sequence and the symbols comprise at least some of the 20 amino-acids.

19. The apparatus of claim 9, wherein said string is an amino acid string and said tree is operable to identify at least one of primary, secondary and three dimensional protein structure.

20. The apparatus of claim 18, wherein said string has a given property, and said tree is operable to identify other strings having said given property.

21. Apparatus according to claim 12, 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.

22. Apparatus according to claim 12, 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.

23. Apparatus according to claim 12, 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.

24. Apparatus according to claim 12, wherein said nucleic acid sequence is a non-coding sequence and another nucleic acid sequence is a coding sequence, wherein said stochastic modeler is operable to build models of said non-coding sequence and said 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 coding sequence.

25. Apparatus according to claim 12, wherein said nucleic acid sequence is an exon sequence, wherein said stochastic modeler is operable to build a model of said exon sequence and said comparator is operable to compare a second nucleic acid sequence with said model to determine whether said second sequence is an exon sequence.

26. Apparatus according to claim 12, wherein said nucleic acid sequence is an intron sequence, wherein said stochastic modeler is operable to build a model of said intron sequence and said comparator is operable to compare a second nucleic acid sequence with said model to determine whether said second sequence is an intron sequence.

27. Apparatus according to claim 1, wherein said stochastic model is refinable using further data sequences, thereby to define a structure of a common attribute of said data sequences.

28. Apparatus for determining statistical consistency in spatially related data comprising a finite set of symbols, the apparatus comprising

a sequence input for receiving said spatially related data,

a stochastic modeler for producing at least one stochastic model from at least part of said spatially related data,

and a comparator for comparing said stochastic model with a prestored model, thereby to determine whether there has been a statistical change in said data.

29. Apparatus according to claim 28, wherein said stochastic modeler comprises:

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.

30. Apparatus according to claim 28, said prestored model being a model constructed using another part of said spatially related data.

31. Apparatus according to claim 28, said comparator comprising a statistical processor for determining a statistical distance between said stochastic model and said prestored model.

32. Apparatus according to claim 28, wherein said comparator comprises a statistical processor for determining a difference in statistical likelihood between said stochastic model and said prestored model.

33. Apparatus according to claim 31, said statistical distance being a relative complexity measure.

34. Apparatus according to claim 31, wherein said statistical distance comprises an SPRT statistic.

35. Apparatus according to claim 31, wherein said statistical distance comprises an MDL statistic.

36. Apparatus according to claim 31, wherein said statistical distance comprises a Multinomial goodness of fit statistic.

37. Apparatus according to claim 31, wherein said statistical distance comprises a Weinberger Statistic.

38. Apparatus according to claim 31, wherein said statistical distance comprises a KL statistic.

39. Apparatus according to claim 29, 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.

40. Apparatus according to claim 39, wherein said threshold distance is user selectable.

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

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

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

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

46. Apparatus according to claim 39, 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.

47. Apparatus according to claim 28, wherein said data comprises a nucleic acid sequence.

48. Apparatus according to claim 28, wherein said data comprises an amino-acid sequence.

49. Apparatus according to claim 28, wherein said sequential data is an output of a medical sensor sensing bodily functions.

50. Apparatus according to claim 47, 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.

51. Apparatus according to claim 47, 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.

52. Apparatus according to claim 47, 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.

53. Apparatus according to claim 47, 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.

54. Apparatus according to claim 31, wherein said data sequence comprises image data of a first image.

55. Apparatus according to claim 54, said distance being indicative of a statistical distribution within said image.

56. Apparatus according to claim 55, further comprising an image comparator for comparing said statistical distribution with a statistical distribution of another image.

57. Apparatus according to claim 56, 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.

58. Apparatus according to claim 54, said image data comprising medical imaging data, said statistical distance being indicative of deviations of said data from an expected norm.

59. Apparatus according to claim 31, applicable to a database to perform data mining on said database.

60. Apparatus according to claim 28, 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.

61. Apparatus according to claim 28, said model being usable to analyze results of a nucleic acid micro array.

62. Apparatus according to claim 28, said model being usable to analyze results of a protein microarray.

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

63. A method of designing a protein for carrying out a predetermined task, the method comprising:

taking a plurality of proteins known to carry out said predetermined task,

constructing a stochastic model using an amino acid sequence of said plurality of proteins,

using said stochastic model to predict a protein sequence.

64. A method of designing a protein for carrying out a predetermined

task, the method comprising:

taking a plurality of proteins known to carry out said predetermined task,

constructing a stochastic model using the 3D structure of said plurality of proteins,

using said stochastic model to determine a protein structure.

65. A method of distinguishing between biological sequences of a first kind and biological sequences of a second kind, each kind being expressible in terms of a same finite set of symbols, the method comprising:

obtaining a statistically significant set of sequences of said first kind and building a stochastic model thereof,

obtaining a statistically significant set of sequences of said second kind and building a stochastic model thereof, and

taking a further sequence and comparing it with each stochastic model to determine whether it belongs to either set.

66. The method of claim 65, wherein said biological sequences are nucleic acid sequences.

67. The method of claim 65, wherein said biological sequences are amino acid sequences.

68. The method of claim 66, wherein the sequences of said first kind are promoter sequences.

69. The method of claim 66, wherein the sequences of said first kind are coding and the sequences of said second kind are non-encoding sequences.

70. The method of claim 69, wherein the sequences are non-species specific, thereby constructing models which are non-species specific.