US 2002/0177138 A1 · Methods for the indentification of textual and physical structured query fragments for the analysis of textual and biopolymer information

Abstract

We disclose a combinatorial, hierarchical process that uses “process-patterns” in one preferred embodiment to identify, classify, and compare substrings within strings; and in another preferred embodiment to identify, classify, compare, generate, and separate fragments derived from one or more physical samples of polynucleotides. These substrings (and their physical polynucleotide counterparts) are called “partition” fragments, and the process-pattern-defined derivatives that some, but not all, “partition” fragments may yield are called “structured query fragments” (SQFs). A process-pattern is both: (i) an ordered set of short “target” (one from each major search class) sites that must be present (and whose higher-ranked members of the same major search class must not have any sites) within the relevant search area of a partition fragment, and (ii) a step-wise delimitation process (where each step has a defined polarity and occurs after a target is found) that restricts the region of a partition fragment where the next class-specific, pre-emptive target-search takes place. In one preferred embodiment, the computer software disclosed herein locates the process-patterns and SQFs of interest within the partition fragments in the string(s) under study (e.g., a set of polynucleotide sequence data), stores the results, and provides for access to this data by database query and analysis tools. These computational analyses are emulated by another preferred embodiment using physical samples of polynucleotides and the laboratory methods disclosed herein. In the latter, sequence-specific, double-stranded cleavage effectors utilize as substrates and generate as products progressively expanding sets of asymmetrically end-immobilized DNA, a process that ultimately yields extremely large numbers of individually distinguishable SQFs (called “ranged” SQFs) with lengths between 100-700 nucleotides. In almost all cases, the known process-pattern and observed length of an experimentally obtained ranged SQF provide sufficient information for the computer software disclosed herein to map the ranged SQF automatically to its partition fragment (and location) within a set of polynucleotide sequence data that characterizes the physical sample(s) of polynucleotides under study.

Claims34

Dependent claims

A method for characterizing a set of strings, said method comprising:

a) receiving the set of strings comprising process-pattern containing substrings;
b) defining a series of search target string patterns effective for searching the set of strings;
and
c) processing the set of strings through an ordered series of search steps each search step being specific for one of the search classes and involving an attempted discovery of an appropriate search target site to define a delimited search region for the next step, thereby characterizing the set of strings.

1 more element

A method for characterizing sets of strings, the method comprising:

(a) receiving one or more sets of strings of any length, wherein may be found occurrences of relatively short search-target-strings of interest;
and where one or more of the short search-target-strings are used to define a distinct search target;
and where several distinct search targets or targets are assembled into structured entities known as search target groups, where a search target group is comprised of:
(i) a partition search target that is used to partition the sets of strings under study into substrings or partition fragments bounded by consecutive occurrences of the partition search target;
and (ii) a small array of a limited number M of major classes or ordered sets of search targets, where each major class is comprised of a limited number of ranked member search targets;
and where a search target group or target group, or two or more search target groups or target groups of distinct composition or structure, may be used to characterize search target group-defined substrings found within the sets of strings under study;
(b) using the structure and composition of a search target group with M major classes to define a search process comprised of a series of M search steps that are to be effected within each of the partition fragments obtained, from the sets of strings under study, using the partition search target of the target group;
and where the search process defines patterns, of occurrence within the partition fragments of search targets that are members of the target group;
and where partition fragments or regions therein may be characterized by the occurrence therein of instances, of the process-patterns that may be defined by the structure and composition of the target group;
and
(c) using the structure and composition of a search target group with M major classes to effect a search process comprised of a series of M search steps within each of the partition fragments obtained, from the sets of strings under study, using the partition search target of the target group;
and where the search process results in the detection of process-pattern entities, where each process-pattern entity is comprised of a pattern of M search target sites, which together include a search target site representing one member of each of the M major classes in the target group;
and where each of the sites must be present and where sites representing higher-ranked members of the same major class must be absent within the relevant search area for the major class in the partition fragment;
and where the process-pattern entities are obtained as a result of a stepwise search and delimitation process after each site is found that restricts the region of the partition fragment where the next class-specific target-search occurs;
and where partition fragments or regions therein may be characterized by the occurrence therein of process-pattern entities, where the process-pattern entities represent instances of the process-patterns that may be defined by the structure and composition of the target group;
and where partition fragments or regions therein may be characterized by the occurrence therein of structured query fragments (SQFS) that are fragments bounded any two search target sites in a process-pattern entity, and whose lengths can be calculated by the positions of the constituent sites that comprise the process-pattern entity wherein the SQFs are found;
and where the SQFs of particular interest are typically the SQFs bounded by the last two search target sites detected in the identification of a process-pattern entity.

14 more elements

A laboratory method for the physical characterization of a sample of polynucleotides of the same general type, the method comprising:

(a) obtaining a sample of polynucleotides, wherein may be found occurrences of relatively short recognition sequences for sequence-specific, polynucleotide cleavage effectors of interest;
and where each of the recognition sequences is used to define a distinct search target for their respective sequence-specific polynucleotide cleavage effector;
and where several distinct search targets or targets are assembled into structured entities known as search target groups, where a search target group is comprised of (i) a partition search target whose sequence-specific polynucleotide cleavage effector is used to cleave the polynucleotide sample under study into partition fragments bounded by consecutive occurrences of the partition search target;
and (ii) a small array of a limited number M of major classes or ordered sets of search targets, where each major class is comprised of a limited number of ranked member search targets;
and where a target group may be used for the physical characterization of a sample of polynucleotides, or two or more target groups of distinct composition or structure may each be used separately for the physical characterization of separate, identical samples of polynucleotides, where the physical characterization is summarized by following series of steps, comprising:
(i) blocking of random termini of the polynucleotide fragments that comprise the sample of polynucleotides, in order to prevent addition of derivatizing reagents thereto;
(ii) cleavage of the sample of polynucleotides using the sequence-specific, polynucleotide cleavage effector whose recognition sequence represents the partition search target;
(iii) derivatization of non-random termini of the partition fragments obtained in the previous step, using a derivatizing reagent that allows for their subsequent termini-specific immobilization, where the non-random termini were generated by the action of the sequence-specific, polynucleotide cleavage effector whose recognition sequence represents the partition search target;
(iv) termini-specific immobilization of the derivatized polynucleotide fragments on a reactively appropriate solid support, where the reactively appropriate solid support is one that reacts appropriately with, and thereby permits the termini-specific immobilization of, the derivatized polynucleotide fragments;
(v) blocking of any unreacted sites on the solid support;
(vi) iterated, sequence-specific cleavage of the immobilized partition fragments using, in rank order, the sequence-specific polynucleotide cleavage effectors representing the ranked members of the first major class of search targets to be used;
and where after each reaction, the product obtained thereby in solution contains liberated polynucleotide fragments of interest and is isolated for subsequent use;
and where the immobilized substrate polynucleotide fragments that remain on the solid support are available for subsequent iterated, sequence-specific cleavage reactions using, in rank order, the remaining members of the same major class;
(vii) recursive immobilization of the isolated reaction products obtained from the previous step, where the isolated products are immobilized via their termini on physically distinct, reactively appropriate solid supports as described earlier;
and where any unreacted sites on the solid support are subsequently blocked as described earlier;
and where the freshly immobilized polynucleotide fragments on the blocked support are derivatized at their distal-to-the-support termini to permit the subsequent recursive immobilization of fragments that have derivatized termini and are liberated by the activity of a sequence-specific polynucleotide cleavage effector in the next step;
(viii) iterated, sequence-specific cleavage of the immobilized fragments from the previous step, using, in rank order, the sequence-specific polynucleotide cleavage effectors representing the ranked members of the next major class of search targets to be used;
and where after each reaction, the product obtained thereby in solution contains liberated polynucleotide fragments of interest and is isolated for subsequent use;
and where the immobilized substrate polynucleotide fragments that remain on the solid support are available for subsequent iterated, sequence-specific cleavage reactions using, in rank order, the remaining members of the same major class;
(ix) the stepwise generation of progressively expanding, process-pattern defined subsets of polynucleotide fragments, where the fragments are generated by the repeated execution of the previous two steps, and where each of the major classes that comprise the search target group used for the analysis are employed, resulting in the isolation of process-pattern defined structured query fragment (SQF) fractions that for a given SQF fraction contain all of the SQFs that may be obtained from the sample of polynucleotides using the process-pattern definition associated with the SQF fraction;
and where the SQFs present in a given SQF fraction represent fragments bounded by the last two search target sites that are cleaved in all of the process-pattern entities that share the process-pattern definition associated with the SQF fraction, and that may be obtained from the sample of polynucleotides.

18 more elements

A method for characterizing sets of strings, the method comprising:

(a) receiving one or more sets of strings of any length, wherein may be found occurrences of relatively short search-target-strings of interest;
and where one or more of the short search-target-strings are used to define a distinct search target;
and where several distinct search targets or targets are assembled into structured entities known as search target groups, where a search target group is comprised of:
(i) a partition search target that is used to partition the sets of strings under study into substrings or partition fragments bounded by consecutive occurrences of the partition search target;
and (ii) a small array of a limited number M of major classes or ordered sets of search targets, where each major class is comprised of a limited number of ranked member search targets;
and where a search target group or target group, or two or more search target groups or target groups of distinct composition or structure, may be used to characterize search target group-defined substrings found within the sets of strings under study;
(b) using the structure and composition of a search target group with M major classes to define a search process comprised of a series of M search steps that are to be effected within each of the partition fragments obtained, from the sets of strings under study, using the partition search target of the target group;
and where the search process defines patterns of occurrence within the partition fragments of search targets that are members of the target group;
and where partition fragments or regions therein may be characterized by the occurrence therein of instances of the process-patterns that may be defined by the structure and composition of the target group or using a search target group with M major classes, and defining process-patterns using all of the M! permutations of the M major classes of search targets in the search target group, where each major-class permutation defines the order with which the major classes of the target group are used;
(c) obtaining or estimating mean recurrence length or mean fragment length data for each search target used in the search target group, where the mean fragment length data is for the search targets in the set of strings used in the analysis;
(d) obtaining or estimating the overall length of the set of strings used in the analysis;
(e) assuming that the distribution of the fragment length between consecutive occurrences of each search target used in the search target group may be approximated by the exponential distribution;
(f) using the properties of the exponential distribution, together with the mean fragment length data and the overall length of the set of strings, to derive a simple, recursive calculation method to estimate the following for a given set of strings under study and for each of the process-patterns that are defined by the search target group used for the analysis:
(i) the number of SQFs of any size;
(ii) the number of SQFs within a given size range;
and (iii) the mean fragment length of SQFs of any size.

13 more elements

Dependencies are inferred from the claim text.

Methods for the indentification of textual and physical structured query fragments for the analysis of textual and biopolymer information

Life of this patent

Methods for the indentification of textual and physical structured query fragments for the analysis of textual and biopolymer information

Life of this patent

Abstract

Claims34