Tandem repeat detection using pattern discovery
AssigneeInternational Business Machines Corporation
InventorsAris Floratos, Isidore Rigoutsos, Gustavo A. Stolovitzky
Life of this patent
Estimating the term…
Abstract
An algorithm which detects tandem repeats (TR) is provided. In an illustrative embodiment, a set of repeating units contained in an input sequence is identified, wherein each given repeating unit satisfies at least the following conditions: (a) a first measure of similarity between adjacent repeating units in the set is greater than a first user defined threshold, and (b) the given repeating unit includes at least one unit having a second measure of similarity with any other unit in the set that is a greater than a second user defined threshold. The method then provides for reporting positions in the input sequence that are covered by the set of repeating units.
Claims24
A computer-implemented method for identifying at least one region of interest in a one-dimensional input sequence, the method comprising the steps of:
- identifying patterns contained in said input sequence;
- grouping said patterns into sets, wherein each pattern in a given set shares a period;
- for at least one set of patterns,
- for each position P in said input sequence that lies in at least one pattern within said one set of patterns, generating a data value representing a number of patterns in said set of patterns whose extremes flank said position P;
- applying a low-pass transformation to said data values for said one set of patterns;
- subsequent to said transformation of said data values, identifying at least one pair of said data values that satisfy a predetermined criterion;
- and
- identifying said region of interest based upon position in said input sequence corresponding to said pair of data values.
Apparatus for identifying at least one region of interest in a one-dimensional input sequence, the apparatus comprising:
- at least one processor operative to:
- (i) identify patterns contained in said input sequence;
- (ii) group said patterns into sets, wherein each pattern in a given set shares a period;
- (iii) for at least one set of patterns, for each position P in said input sequence that lies in at least one pattern within said one set of patterns, generate a data value representing a number of patterns in said set of patterns whose extremes flank said position P;
- apply a low-pass transformation to said data values for said one set of patterns;
- subsequent to said transformation of said data values, identify at least one pair of said data values that satisfy a predetermined criterion;
- and (iv) identify said region of interest based upon position in said input sequence corresponding to said pair of data values;
- and
- a memory, coupled to the at least one processor, operative to store said region of interest.
An article of manufacture for identifying at least one region of interest in a one-dimensional input sequence, comprising a machine readable medium containing one or more programs which when executed implement the steps of:
- identifying patterns contained in said input sequence;
- grouping said patterns into sets, wherein each pattern in a given set shares a period;
- for at least one set of patterns,
- for each position P in said input sequence that lies in at least one pattern within said one set of patterns, generating a data value representing a number of patterns in said set of patterns whose extremes flank said position P;
- applying a low-pass transformation to said data values for said one set of patterns;
- subsequent to said transformation of said data values, identifying at least one pair of said data values that satisfy a predetermined criterion;
- and
- identifying said region of interest based upon position in said input sequence corresponding to said pair of data values.
Dependencies are inferred from the claim text.