US 2006/0235845 A1 · Identifying patterns of symbols in sequences of symbols using a binary array representation of the sequence

Abstract

The present invention relates to computer-implemented methods for finding patterns in patterns in a set of k-sequences of symbols (where k≧2) and to a computer readable medium having instructions for controlling a computer system to perform the methods. Patterns of symbols common to each 2-tuple of sequences are identified. Each identified pattern of symbols is represented by a position index binary array (PIBA) which is a set of binary digits. The binary digit in each place in the array that corresponds to a location in a selected reference sequence of a symbol in the identified pattern has a first predetermined binary value. All of the other binary digits in the array have a second predetermined binary value. The position index binary array (PIBA) representations of patterns of each tuple at any order “n” may be combined with the PIBA pattern representations of all other tuples at that same order “n” or with the pattern representations in any selected m-tuple, where m may have any integer value from 2 to (n−1). The patterns of the resulting tuple are identified from the position index binary arrays (PIBAs) produced by the intersection of the set of binary digits in each position index binary array (PIBA) in the n-tuple with the set of binary digits in each position index binary array (PIBA) in the other tuple. The intersections are accomplished logically, as by performing a logical AND operation in a bit-by-bit manner on the binary arrays. Using the places in the position index binary array (PIBA) produced by the intersections having the first predetermined binary value as a guide, the symbols in corresponding locations in the reference sequence are identified. These symbols comprise the symbols in the identified pattern in the resulting tuple.

Claims34

Dependent claims

A method for identifying patterns in a set of k-sequences of symbols, where k is greater than or equal to two and wherein the location of a symbol in a sequence is denoted by a position index, the method comprising the steps of:

(a) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(b) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in a position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(c) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBAs) that each represent a pattern in a 3-tuple of patterns.

5 more elements

(a) for each pair-wise combination of sequences,
(i) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(ii) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in the position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(iii) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a 3-tuple of patterns;
(b) for pair-wise combinations of n-tuples from n=3 to n=(k-1) that share a common reference sequence,
intersecting the set of binary digits of each position index binary array (PIBA) in a first n-tuple with the set of binary digits of each position index binary array (PIBA) in the other n-tuple, provided there exists patterns in each n-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a resultant tuple of patterns;
and
(c) from the patterns identified in step (b), identifying the symbols in the reference sequence at the locations therein corresponding to the places in the position index binary arrays (PIBAs) having the first predetermined binary value.

11 more elements

(a) for each pair-wise combination of sequences,
(i) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(ii) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in the position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(iii) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a 3-tuple of patterns;
(b) for each n-tuple from n=3 to n=(k-1),
intersecting the set of binary digits of each position index binary array (PIBA) in one n-tuple with the set of binary digits of each position index binary array (PIBA) in any selected m-tuple from m=2 to m=(n−1) that shares a common reference sequence with that n-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a resultant tuple of patterns;
and
(c) from the patterns identified in step (b), identifying the symbols in the reference sequence at the locations therein corresponding to the places in the position index binary arrays (PIBAs) having the first predetermined binary value.

11 more elements

A computer-readable medium containing instructions for controlling a computer system to identify patterns in a set of k-sequences of symbols, where k is greater than or equal to two, and wherein the location of a symbol in a sequence is denoted by a position index, by performing the steps of:

(a) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(b) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in a position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(c) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBAs) that each represent a pattern in a 3-tuple of patterns.

5 more elements

(a) for each pair-wise combination of sequences,
(i) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(ii) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in the position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(iii) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a 3-tuple of patterns;
(b) for pair-wise combinations of n-tuples from n=3 to n=(k-1) that share a common reference sequence,
intersecting the set of binary digits of each position index binary array (PIBA) in a first n-tuple with the set of binary digits of each position index binary array (PIBA) in the other n-tuple, provided there exists patterns in each n-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a resultant tuple of patterns;
and
(c) from the patterns identified in step (b), identifying the symbols in the reference sequence at the locations therein corresponding to the places in the position index binary arrays (PIBAs) having the first predetermined binary value.

11 more elements

(a) for each pair-wise combination of sequences,
(i) identifying a 2-tuple of patterns of symbols common to each pair-wise combination of sequences;
(ii) for each pattern of symbols in each identified 2-tuple of patterns, creating a position index binary array (PIBA) representing that pattern,
each position index binary array (PIBA) comprising a set of binary digits,
the binary digit in each place in the position index binary array (PIBA) that corresponds to a location in a selected reference sequence of a symbol in the identified pattern being a first predetermined binary value, all other binary digits in the position index binary array (PIBA) being a second predetermined binary value;
and
(iii) taking all 2-tuples that share a common reference sequence in pair-wise combination,
intersecting the set of binary digits of each position index binary array (PIBA) in one 2-tuple with the set of binary digits of each position index binary array (PIBA) in the other 2-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a 3-tuple of patterns;
(b) for each n-tuple from n=3 to n=(k-1),
intersecting the set of binary digits of each position index binary array (PIBA) in one n-tuple with the set of binary digits of each position index binary array (PIBA) in any selected m-tuple from m=2 to m=(n−1) that shares a common reference sequence with that n-tuple,
thereby to define one or more position index binary arrays (PIBA) that each represent a pattern in a resultant tuple of patterns;
and
(c) from the patterns identified in step (b), identifying the symbols in the reference sequence at the locations therein corresponding to the places in the position index binary arrays (PIBAs) having the first predetermined binary value.

11 more elements

Dependencies are inferred from the claim text.

Identifying patterns of symbols in sequences of symbols using a binary array representation of the sequence

Life of this patent

Identifying patterns of symbols in sequences of symbols using a binary array representation of the sequence

Life of this patent

Abstract

Claims34