# US 7,613,572 B2 · Stochastic modeling of spatial distributed sequences > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,572 B2 - Document ID: US7613572B2 - Status: Granted - Kind: B2 - Application number: 10/468,101 - Filed: 2002-02-20 - Published: 2004-04-08 - Granted: 2009-11-03 - Earliest claimed: 2001-02-20 - Assignees: Context-Based 4 Casting (C-B4) Ltd. - Inventors: Irad Ben-Gal; Armin Shmilovici; Gail Morag; Gonen Zinger - Web page: https://patentgrep.com/patent/US7613572B2 ## CPC - G06Q 40/00: Finance; Insurance; Tax strategies; Processing of corporate or income taxes - G06F 18/24323: {Tree-organised classifiers} - G06Q 40/04: Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange - G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The apparatus according to claim 1, said reference model being a model constructed using another part of said input spatially related data sequence. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) The apparatus according to claim 1, said statistical distance being a relative complexity measure. ### Claim 7 (depends on 4) The apparatus according to claim 4, wherein said statistical distance comprises an SPRT statistic. ### Claim 8 (depends on 4) The apparatus according to claim 4, wherein said statistical distance comprises an MDL statistic. ### Claim 9 (depends on 4) The apparatus according to claim 4, wherein said statistical distance comprises a Multinomial goodness of fit statistic. ### Claim 10 (depends on 4) The apparatus according to claim 4, wherein said statistical distance comprises a Weinberger Statistic. ### Claim 11 (depends on 4) The apparatus according to claim 4, wherein said statistical distance comprises a KL statistic. ### Claim 12 (depends on 2) 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. ### Claim 13 (depends on 12) The apparatus according to claim 12, wherein said threshold distance is user selectable. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein user selectable parameters further comprise a tree maximum depth. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein user selectable parameters further comprise an algorithm buffer size. ### Claim 16 (depends on 13) The apparatus of claim 13, wherein user selectable parameters further comprise a value of at least one pruning constant. ### Claim 17 (depends on 13) The apparatus of claim 13, wherein user selectable parameters further comprise a length of input sequences. ### Claim 18 (depends on 13) The apparatus of claim 13, wherein user selectable parameters further comprise an order of input symbols. ### Claim 19 (depends on 12) 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. ### Claim 20 (depends on 1) The apparatus according to claim 1, wherein said data comprises a nucleic acid sequence. ### Claim 21 (depends on 1) The apparatus according to claim 1, wherein said data comprises an amino-acid sequence. ### Claim 22 (depends on 1) The apparatus according to claim 1, wherein said sequential data is an output of a medical sensor sensing bodily functions. ### Claim 23 (depends on 20) 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. ### Claim 24 (depends on 20) 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. ### Claim 25 (depends on 20) 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. ### Claim 26 (depends on 20) 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. ### Claim 27 (depends on 4) The apparatus according to claim 4, wherein said data sequence comprises image data of a first image. ### Claim 28 (depends on 27) The apparatus according to claim 27, said distance being indicative of a statistical distribution within said image. ### Claim 29 (depends on 28) The apparatus according to claim 28, further comprising an image comparator for comparing said statistical distribution with a statistical distribution of another image. ### Claim 30 (depends on 29) 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. ### Claim 31 (depends on 27) 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. ### Claim 32 (depends on 1) The apparatus according to claim 1, applicable to a database to perform data mining on said database. ### Claim 33 (depends on 1) 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. ### Claim 34 (depends on 1) The apparatus according to claim 1, said model being usable to analyze results of a nucleic acid micro array. ### Claim 35 (depends on 1) The apparatus according to claim 1, said model being usable to analyze results of a protein microarray. ### Claim 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. ### Claim 37 (depends on 36) The apparatus of claim 36, wherein said biological sequences are amino acid sequences. ### Claim 38 (depends on 36) The apparatus of claim 36, wherein the sequences of said first kind are nucleic acid promoter sequences. ### Claim 39 (depends on 36) 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. ### Claim 40 (depends on 39) The apparatus of claim 39, wherein the sequences are non-species specific, thereby constructing models which are non-species specific. ### Claim 41 (depends on 36) The apparatus of claim 36, wherein the data sequences are biological sequences. ### Claim 42 (depends on 36) The apparatus of claim 36, wherein the data sequences comprises image data of a first image. ### Claim 43 (depends on 41) The apparatus of claim 41, wherein said biological sequences are amino acid sequences. ### Claim 44 (depends on 1) The apparatus according to claim 1, wherein said input spatially related data is representative of one of an image, a molecule and a microarray. ### Claim 45 (depends on 36) The apparatus according to claim 36, applicable to a database to perform data mining on said database.