Data relationship model

• US 7,039,238 B2
• Filed: 12/03/2001
• Issued: 05/02/2006
• Est. Priority Date: 12/01/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Lincoln, Patrick Denis, Karp, Peter D., Sonmez, Kemal, Toll, Lawrence R.
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/004,580
• Publication Number:
  US 20030169926A1
• Time in Patent Office: 1,611 Days
• Field of Search: 382/159, 382/165, 382/181, 382/209, 382/218, 382/219, 382/224, 382/228, 707/3, 707/6
• US Class Current: 382/219
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search

Abstract

A model is used to represent a set of structured data objects that include elements at defined positions. The model includes distributions of vectors, each distribution corresponding to particular positions in the respective structured data objects, each of the vectors comprising values for the particular positions; and comparing a given set of structured data objects to the model to determine a likelihood that the given set is represented by the model. At least some of the distributions of the model differ such that different states of matching are indicated. Distributions of the model can indicate: dissimilarity between the structured data objects at defined positions; similarity between the structured data objects at defined positions; or similarity to a reference structure data object at defined positions.

Claims

1. A method comprising:

specifying a model that (i) represents a set of structured data objects that include elements at a plurality of positions, and (ii) comprises distributions of vectors, each distribution corresponding to a particular position in the respective structured data objects, each of the vectors comprising values for the particular position, at least some distributions indicating dissimilarity at various positions of said pluralty of positions of the structured data objects; and

comparing a given set of structured data objects to the model to determine a likelihood that the given set is represented by the model.

2. The method of claim 1 in which the structured data objects comprise sequences.

3. The method of claim 2 in which the sequences comprise audio information.

4. The method of claim 3 in which in which the audio information comprises representations of speech.

5. The method of claim 2 in which the sequences comprise financial or economic information.

6. The method of claim 2 in which the sequences comprise biopolymer sequences.

7. The method of claim 2 in which elements of each of the sequences consist of a single value.

8. The method of claim 2 in which elements of each of the sequences comprise at least two values.

9. The method of claim 1 in which the structured data objects comprise multi-dimensional maps.

10. The method of claim 9 in which the structured data objects comprise two-dimensional maps.

11. The method of claim 10 in which the particular positions of the two dimensional map comprise pixels.

12. The method of claim 11 in which each pixel comprises color information.

13. The method of claim 12 in which the color information comprises at least two values.

14. The method of claim 1 in which the structured data objects each comprises an image.

15. The method of claim 14 in which the image comprises a photographic image.

16. The method of claim 1 in which the model is trained to determine at least some of the distributions.

17. The method of claim 1 in which at least some others of the distributions indicate similarity.

18. The method of claim 17 in which at least some of the distributions that indicate similarity are different.

19. The method of claim 1 further comprising repeating the comparing for multiple given sets.

20. The method of claim 19 further comprising ranking the multiple given sets by the likelihoods returned by the model for each given set.

21. The method of claim 1 in which the given sets consist of two structured data objects.

22. The method of claim 19 in which the multiple given sets comprise pairwise combinations of a first and second group of structured data objects, each pairwise combination including an object of the first group and an object of the second group.

23. The method of claim 1 in which each distribution is represented as a node in a network of nodes.

24. The method of claim 23 in which the network further comprises nodes that represent an insertion or deletion in an object of the set relative to another object of the set.

25. The method of claim 23 in which interconnections between nodes are associated with a probability.

26. The method of claim 25 in which the network of nodes comprises a hidden Markov model.

27. The method of claim 23 in which the comparing comprises identifying a path that traverses the network of nodes, the path corresponding to the given set, and evaluating the likelihood of the path.

28. An apparatus comprising a processor and storage, the storage comprising (i) a model that represents a set of structured data objects “

that includes elements at a plurality of positions”

, the model comprising distributions of vectors, each distribution corresponding to a particular position in the respective structured data objects such that each of the vectors comprises values for the particular position, wherein at least some distributions indicating dissimilarity at various positions “

of said plurality of positions”

of the structured data objects, and (ii) a computer readable medium containing an executable program for causing the processor to compare a given set of structured data objects to the model.

29. A method comprising:

specifying a model that (i) represents a set of structured data objects that include elements at “

a plurality of”

positions, and (ii) comprises distributions of vectors, each distribution corresponding to a particular positions in the respective structured data objects such that each of the vectors comprises values for the particular position,

wherein at least some distributions indicate similarity between the structured data objects at various positions “

of said plurality of positions”

“

other distributions” and

at least some others indicate matching to a reference structure data object at various positions “

of said plurality of positions”

; and

comparing a given set of structured data objects to the model to determine a likelihood that the given set is represented by the model.

30. The method of claim 29 in which at least some of the

distributions that indicate similarity are different.

31. A computer readable medium containing an executable program, where the program performs the steps of:

specifying a model that (i) represents a set of structured data objects that include elements at a plurality of positions, and (ii) comprises distributions of vectors, each distribution corresponding to a particular position in the respective structured data objects, each of the vectors comprising values for the particular position, at least some distributions indicating dissimilarity at various positions of said plurality of positions of the structured data objects; and

comparing a given set of structured data objects to the model to determine a likelihood that the given set is represented by the model.