Using dotplots for comparing and finding patterns in sequences of data points

• US 8,463,733 B2
• Filed: 11/10/2009
• Issued: 06/11/2013
• Est. Priority Date: 11/11/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Helfman, Jonathan, Goldberg, Joseph H.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Hill, Stanley K
• Application Number:
  US12/615,749
• Publication Number:
  US 20100121812A1
• Time in Patent Office: 1,309 Days
• Field of Search: None
• US Class Current: 706/54
• CPC Class Codes: A61B 3/113 for determining or recording eye movement
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids

Abstract

Embodiments of the invention provide systems and methods for analyzing sequential data. The sequential data can comprise a sequence of data points arranged in a particular order and thus representing a sequence. A number of such sequences can be analyzed, for example, to identify patterns or commonalities within the sequences or portions of sequences represented by the data. According to one embodiment, a method of identifying patterns in sequences of data points can comprise reading a set of sequential data. The sequential data can comprises a plurality of sequences and each of the plurality of sequences can represent an ordered sequence of tokens. A dotplot representing matches between each sequence of the plurality sequences can be generated. One or more patterns within the sequential data can then be identified based on the dotplot.

Claims

1. A method for identifying one or more patterns in a plurality of sequences, the method comprising:

reading a set of sequential data with an analysis system, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens;

generating, with the analysis system, a dotplot based on the tokens and representing matches between each sequence of the plurality sequences; and

identifying, with the analysis system, one or more patterns within the sequential data based on the dotplot by identifying linear relationships between the tokens and wherein identifying linear relationships between the tokens comprises;

determining a dotplot sub-matrix plotting tokens from two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold;

fitting a linear regression line to the filtered points;

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion; and

re-computing the linear regression line using the points within the variance criterion.

2. The method of claim 1, wherein identifying one or more patterns further comprises removing the points having linear relationships from the set of points, identifying another linear relationship within the dataset by repeating said fitting a linear regression line to the filtered points, computing variance criterion based on Euclidean distances between the regression line and the filtered points, filtering the filtered points to those within the variance criterion, and re-computing the linear regression line using the points within the variance criterion.

3. The method of claim 2, wherein the tokens represent data points comprising fixation points of eye tracking data and the sequences represent scanpaths.

4. The method of claim 2, wherein the tokens represent data points comprising Uniform Resource Locators (URLs) and the sequences represent sequences of requested URLs in a client web browsing session.

5. The method of claim 2, wherein the tokens represent data points comprising Uniform Resource Locators (URLs) and the sequences represent sequences of requested URLs in a web server log file.

6. The method of claim 2, wherein the tokens represent data points comprising text strings and the sequences represent sequences of the strings within one or more documents.

7. The method of claim 2, wherein the tokens represent data points comprising stock prices and the sequences represent the stock prices over time.

8. The method of claim 2, wherein the tokens represent genes and the sequences represent sequences of DeoxyriboNucleic Acid (DNA) or RiboNucleic Acid (RNA).

9. A system for identifying one or more patterns in a plurality of sequences, the system comprising:

a processor; and

a memory communicatively coupled with and readable by the processor and having stored therein a series of instructions which, when executed by the processor, cause the processor to read a set of sequential data, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens, generate a dotplot representing matches between each sequence of the plurality sequences, and identify one or more patterns within the sequential data based on the dotplot by identifying linear relationships between the tokens and wherein identifying linear relationships between the tokens comprises;

determining a dotplot sub-matrix plotting tokens from two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold;

fitting a linear regression line to the filtered points;

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion; and

re-computing the linear regression line using the points within the variance criterion.

10. The system of claim 9, wherein identifying one or more patterns further comprises removing the points having linear relationships from the set of points, identifying another linear relationship within the dataset by repeating said fitting a linear regression line to the filtered points computing variance criterion based on Euclidean distances between the regression line and the filtered points, filtering the filtered points to those within the variance criterion, and re-computing the linear regression line using the points within the variance criterion.

11. The system of claim 9, wherein the tokens represent data points selected from a group consisting of:

fixation points of eye tracking data;

Uniform Resource Locators (URLs);

text strings;

stock prices; and

genes.

12. A machine-readable memory device having stored thereon a series of instructions which, when executed by a processor, cause the processor to identify one or more patterns in a plurality of sequences by:

reading a set of sequential data, wherein the sequential data comprises a plurality of sequences, each of the plurality of sequences representing an ordered sequence of tokens;

generating a dotplot representing matches between each sequence of the plurality sequences; and

identifying one or more patterns within the sequential data based on the dotplot by identifying linear relationships between the tokens and wherein identifying linear relationships between the tokens comprises;

determining a dotplot sub-matrix plotting tokens from two sequences;

identifying a set of points in the sub-matrix that corresponds to matching tokens in corresponding sub-sequences;

filtering the identified points against a pre-determined high-pass threshold;

fitting a linear regression line to the filtered points;

computing variance criterion based on Euclidean distances between the regression line and the filtered points;

filtering the filtered points to those within the variance criterion; and

re-computing the linear regression line using the points within the variance criterion.

13. The machine-readable memory device of claim 12, wherein identifying one or more patterns further comprises removing the points having linear relationships from the set of points, identifying another linear relationship within the dataset by repeating said fitting a linear regression line to the filtered points, computing variance criterion based on Euclidean distances between the regression line and the filtered points, filtering the filtered points to those within the variance criterion, and re-computing the linear regression line using the points within the variance criterion.

14. The machine-readable memory device of claim 12, wherein the tokens represent data points selected from a group consisting of:

fixation points of eye tracking data and wherein the sequences represent scanpaths;

Uniform Resource Locators (URLs) and wherein the sequences represent sequences of requested URLs in a client web browsing session or requested URLs in a web server log file;

text strings and wherein the sequences represent sequences of the strings within one or more documents;

stock prices and wherein the sequences represent the stock prices over time; and

genes and wherein the sequences represent sequences of DeoxyriboNucleic Acid (DNA) or RiboNucleic Acid (RNA).