Abstract:
A new portion of an input string is selected. The input string has a number of characters from an alphabet. The new portion differs from a previously selected portion of the input string by one or more new characters of the input string. One or more values are determined for how many of the one or more new characters are in the portion of the input string. It is determined which, if any, names in a number of sets of names have changed by selection of the new portion. The number of sets have a first set and a number of additional sets, wherein the first set corresponds to all of the characters in the alphabet and to values of how many of the characters of the alphabet are in the previously selected portion. The values are names for the first set. Each additional set comprises names corresponding to selected pairs of names from a single other set. Changes in the names are used to determine the permutation patterns. Each name generally corresponds to a permutation pattern and permutation patterns may be found by keeping track of changes to the names. When a name is changed greater than or equal to a predetermined value, the permutation pattern corresponding to the name may be output.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to pattern discovery and, more particularly, relates to discovery of permutation patterns.  
       BACKGROUND OF THE INVENTION  
       [0002]     A permutation pattern is a pattern where the characters in the pattern can be in any order. For instance, in the input string, S=abc . . . cab, a permutation pattern can be described as {a, b, c} and the permutation pattern occurs at locations  1  and  7  in the input string. Permutation patterns have a variety of practical uses.  
         [0003]     For example, genes that appear together consistently across genomes are believed to be functionally related: these genes in each other&#39;s neighborhood often code for proteins that interact with one another, suggesting a common functional association. However, the order of the genes in the chromosomes may not be the same. In other words, a group of genes appear in different permutations in the genomes. For example in plants, the majority of snoRNA genes are organized in polycistrons and transcribed as polycistronic precursor snoRNAs. Also, the olfactory receptor(OR)-gene superfamily is the largest in the mammalian genome. Several of the human OR genes appear in clusters, with ten or more members located on almost all human chromosomes. Furthermore, some chromosomes contain more than one cluster, where a cluster has one or more permutation patterns.  
         [0004]     As the available number of complete genome sequences of organisms grows, it becomes a fertile ground for investigation along the direction of detecting gene clusters by comparative analysis of the genomes. A gene G is compared with its orthologs G′ in the different organism genomes. Even phylogenetically close species are not immune from gene shuffling, such as in Haemophilus influenzae and  Escherichia Coli.  Also, a multicistronic gene cluster sometimes results from horizontal transfer between species and multiple genes in a bacterial operon fuse into a single gene encoding multi-domain protein in eukaryotic genomes.  
         [0005]     If the functions of genes, say G 1 G 2 , are known, the function of its corresponding ortholog clusters G′ 2 G′ 1  may be predicted. Such positional correlation of genes as clusters and their corresponding orthologs have been used to predict functions of ABC transporters and other membrane proteins.  
         [0006]     The local alignment of nucleic or amino acid sequences, called the multiple sequence alignment problem, is based on similar subsequences; however the local alignment of genomes is based on detecting locally conserved gene clusters. A measure of gene similarity is used to identify the gene orthologs. For example, genes G 1 G 2 G 3  may be aligned with G′ 1 G′ 2 G′ 3 , and such an alignment is never detected in subsequence alignments.  
         [0007]     Domains are portions of the coding gene (or the translated amino acid sequences) that correspond to a functional sub-unit of the protein. Often, these are detectable by conserved nucleic acid sequences or amino acid sequences. The conservation helps in a relative easy detection by automatic motif discovery tools. However, the domains may appear in a different order in the distinct genes giving rise to distinct proteins. But, they are functionally related due to the common domains. Thus these represent functionally coupled genes such as forming operon structures for co-expression.  
         [0008]     Thus, it can be seen that it would be useful to determine permutation patterns for genes or proteins. Consequently, there is a need for improved techniques for determining permutation patterns.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention provides techniques for determining permutation patterns.  
         [0010]     In an exemplary aspect of the present invention, a new portion of an input string is selected. The input string has a number of characters from an alphabet. The new portion differs from a previously selected portion of the input string by one or more new characters of the input string. One or more values are determined for how many of the one or more new characters are in the portion of the input string. It is determined which, if any, names in a number of sets of names have changed by selection of the new portion. The sets have a first set and a number of additional sets, wherein the first set corresponds to all of the characters in the alphabet and to values of how many of the characters of the alphabet are in the previously selected portion. The values are names for the first set. Each additional set comprises names corresponding to selected pairs of names from a single other set. Changes in the names are used to determine the permutation patterns.  
         [0011]     Each name generally corresponds to a permutation pattern and permutation patterns may be found by keeping track of changes to the names. When a name is changed greater than or equal to a predetermined value, the permutation pattern corresponding to the name may be output.  
         [0012]     A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]      FIG. 1  shows an example of permutation patterns discovered in an exemplary input string;  
         [0014]      FIG. 2  is an exemplary method for determining permutation patterns, in accordance with a preferred embodiment of the present invention;  
         [0015]      FIGS. 3A and 3B  are exemplary naming trees used to describe techniques of the present invention; and  
         [0016]      FIG. 4  is an exemplary system for determining permutation patterns from an input string, in accordance with a preferred embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0017]     For ease of reference, the present disclosure is divided into the following sections: Introduction; The Permutation Pattern Problem; Maximal Patterns; and Techniques for Finding Permutation Patterns.  
         [0018]     Introduction  
         [0019]     The present invention allows permutation patterns to be discovered. In this disclosure, the abstract problem of discovering permutation patterns is formed as a discovery problem called the π pattern problem and techniques that automatically discover permutation patterns in, for instance, multiple input patterns are given. As there is generally not enough knowledge about forming an appropriate model to filter the meaningful from the apparently meaningless permutation patterns, a model-less approach is taken herein, which allows all permutation patterns that appear a number of times to be determined. Additionally, a notation is introduced for maximal permutation patterns that drastically reduces the number of valid cluster patterns, without any loss of information, making it easier to study the results from an application viewpoint.  
         [0020]     The Permutation Pattern Problem  
         [0021]     The permutation pattern problem is described below. A permutation pattern will sometimes be referred to through a “π pattern” shorthand.  
         [0022]     The section begins by relating some definitions.  
         [0023]     Let S=s 1 s 2  . . . s n  be a string of length n, and P=p 1 p 2  . . . p m  a pattern, both over alphabet {1, . . . , |Σ|}.  
         [0024]     Definition (Π(s), Π′(s)). Given a string s on alphabet Σ, 
        Π(s)={a∈Σ|a], for some 1≦i≧|s|} and     Π(s)={a(t)|a∈Π(s), t is the number of times that a appears in s}       
 
         [0027]     For example if s=abcda, Π(s)={a, b, c, d}. As another example, if s=abbccdac, Π′(s)={a( 2 ),b( 2 ),c( 3 ),d}. Note that d appears only once and the annotations are ignored altogether.  
         [0028]     Definition of “p-occurs.” A pattern P p-occurs, which means that there is a permuted occurrence of the pattern, in a string S at location i if: Π′(P)=Π′(s i  . . . s i+m−1 ).  
         [0029]     Definition of a permutation pattern, called a “π pattern.” Given an integer K, a pattern P is a π pattern on S if: 
        |P|&gt;1, where this step rules out trivial single character patterns; and     P p-occurs at some k′≧K distinct locations on S. £ p ={i 1 , i 2 , . . . , i k } is the location list of p.        
 
         [0032]     For example, consider Π′(P)={a(2), b(3), c(3)}, and the string S=aacbbxxabcbab. Clearly, P p-occurs at positions 1 and 9.  
         [0033]     A problem of π pattern discovery. Given a string S and K&lt;n, find all π patterns of S together with their location lists.  
         [0034]     For example, if S=abcdbacdabacb, then P={a,b,c} is a 4-π pattern with location list £ p ={1, 5, 10, 11 }.  
         [0035]     The total number of π patterns is O(n 2 ), but is this number actually attained? Consider the following example.  
         [0036]     Let S=abcdefghijabdcefhgij and k=2. The π patterns shown in  FIG. 1  show that their number could be quadratic in the size of the input.  
         [0037]     Maximal Patterns  
         [0038]     A general definition is given below of maximality, and this definition holds even for different kinds of substring patterns such as rigid, flexible, with or without wild cards. Maximal patterns are also described in Parida, “Some Results on Flexible-Pattern Matching,” Proc. of the 11th Symp. on Comp. Pattern Matching, vol. 1848 of Lecture Notes in Comp. Sci., 33-45 (2000), the disclosure of which is hereby incorporated by reference.  
         [0039]     In the following, assume that           is the set of all π patterns on a given input string S.  
         [0040]     Definitions of “non-maximal” and “maximal” patterns are as follows. P a ∈          is non-maximal if there exists P b ∈          such that: (1) each p-occurrence of P a  on S is covered by a p-occurrence of P b  on S (each occurrence of P a  is a substring in an occurrence of P b ) and, (2) each p-occurrence of P b  on S covers l≧1, p-occurrence(s) of P a  on S. A pattern P b  that is not non-maximal is maximal.  
         [0041]     Clearly, Π(P a )⊂Π′(P b ). Although it seems counter-intuitive, it is possible that |£ pa |&lt;|£ pb |. Consider the input S=abcdebca . . . abcde. P a ={d,e} p-occurs only two times but P b ={a, b, c, d, e} p-occurs three times and by the definition P a  is non-maximal with respect to P b .  
         [0042]     To illustrate the case of l&gt;1 in the definition, consider 
        S=abcdbac . . . abcabcd . . . abcdabc.        
 
         [0044]     P a ={a, b, c} p-occurs two times in the first and third, and, four times in the second p-occurrence of P b ={(a)2, (b)2, (c)2, d}. Also, by the definition, P a  is non-maximal with respect to P b . It is also claimed that such a non-maximal pattern P a  can be “deduced” from P b  and the p-occurrences of P a  on S can be estimated to be within the p-occurrences of P b . This is shown in more detail below.  
         [0045]     The following can be shown. Let M={P j ∈         |P j  is maximal}. M is unique.  
         [0046]     This is straightforward to see. This result holds even when the patterns are substring patterns.  
         [0047]     In example shown in  FIG. 1 , pattern P 7  is the only maximal π pattern in S.  
         [0048]     Maximality notation will now be described. Recall that in case of substring patterns, the maximal pattern very obviously indicates the non-maximal patterns as well. For example, a maximal pattern of the form abcd implicates ab, bc, cd, abc, bcd as possible non-maximal patterns, unless they have occurrences not covered by abcd. Do maximal π patterns have such an obvious form? In this section, a special notation is introduced based on observations discussed below. It is then demonstrated how this notation makes it possible to represent maximal π patterns.  
         [0049]     Let Q∈          and ∂={Q′|Q═ is non-maximal w.r.t. Q}. Then there exists a permutation, {overscore (Q)}, of Π′(Q) such that for each element Q′∈∂, a permutation of Π′(Q′) is a substring of {overscore (Q)}.  
         [0050]     Without loss of generality, let the ordering of the elements be as the one in the leftmost occurrence of Q on S as {overscore (Q)}. Clearly, there is a permutation of Π′(Q′) that is a substring of {overscore (Q)}, else Q′ is not a non-maximal pattern by the definition.  
         [0051]     The ordering is not necessarily complete. Some elements may have no order with respect to some others.  
         [0052]     Consider S=abcdef . . . cadbfe . . . abcdef Then P 1 ={a,b,c,d}, P 2 ={e,f} and P 3 ={a, b, c, d, e, f} are the π patterns with three occurrences each on S. Then the intervals denoted by brackets can be represented as 
 
( 3 ( 1 a,b,c,d) 1 ,( 2 e,f) 2 ) 3 , 
 
 where the elements within the brackets can be in any order. A pair of brackets ( i  . . . ) i  corresponds to the π pattern P i . An element is either a character from the alphabet or bracketed elements. 
 
         [0054]     A representation that captures the order of the elements of Q along with the intervals that correspond to each Q′ encodes the entire set Q. This representation will appropriately annotate the ordering. The representation using brackets works except that there may intersecting intervals that could lead to clutter. When the intervals intersect, the brackets need to be annotated. For example, (a(b,d)c) can have at least two distinct interpretations: (1) ( 1 a( 2 b,d) 2 c) 1 , or, (2) ( 1 a( 2 b,d) 1 c) 2 .  
         [0055]     Consider the input string S=abcd . . . dcba . . . abcd. The π patterns are P 1 =ab, P 2 =bc, p 3 =cd, P 4 =abc, P 5 =bcd, P 6 =abcd, each occurring three times. Using only annotated brackets will yield a cluttered representation as follows: 
 
( 6 ( 1 ( 4 a( 2 ( 5 b) 1 ( 3 c) 2 ) 4 d) 3 ) 5 ) 6 . 
 
         [0056]     The annotation of the brackets is beneficial to keep the pairing of the brackets unambiguous. It is clear that if two intervals intersect, then the intersection elements are immediate neighbors of the remaining elements. For example, if  1 a( 2 b,c) 1 d) 2 , then (b,c) must be immediate neighbors of (a) as well as (d). If a symbol “-” is introduced to denote immediate neighbors, then the intervals never intersect. Further, they do not need to be annotated if they do not intersect. Thus the previous example can be simply given as a-(b,c)-d. The earlier cluttered representation can be cleanly put as the following: 
 
a-b-c-d. 
 
         [0057]     Next, consider the example shown in  FIG. 1 . Using the notation, there is only one maximal π pattern given by M=a-b-(c,d)-e-f-(g,h)-i-j at locations  1  and  11  on S. Notice that II(P 7 )=II(M) and every other π pattern can be deduced from M.  
         [0058]     Techniques for Finding Permutation Patterns  
         [0059]     When finding patterns, the input is generally a set of strings of total length n. In order to simplify the explanation, one string S of length n over an alphabet Σ will be considered. It should also be noted that each string can comprise sets of characters at each location in the string. However, for simplicity, one character per location will be described herein.  
         [0060]     The techniques presented below compute the maximal π patterns in S. The maximal π patterns can be determined in two stages: (1) find all the π patterns in S, and (2) find the maximal π patterns in S. In an exemplary implementation, in Stage 2, a straightforward computation is used that uses location lists of all the π patterns in S obtained at Stage 1. The location lists of each pair of π patterns are checked to find if one π pattern is covered by another one. Assume that Stage 1 outputs p π patterns, and the maximum length of a location list is l, Stage 2 runs in O(p 2 l) time. From now on, only Stage 1 will be discussed.  
         [0061]     It is assumed that the size of the longest pattern is L. Step l of Stage 1, where 2≦l≦L, finds π patterns of length l. Stage 1 is described broadly by the method of  FIG. 2 . Steps of method  100  will be described broadly, then more detailed description of the steps will be given.  
         [0062]     Method  100  of  FIG. 2  selects a window size (step  110 ), and then moves a window of size l along string S, adding and deleting a letter in each iteration. In step  115 , the window  170  is placed at the beginning of the string S, as shown by reference  155 . In this example, the window size, l, is four.  
         [0063]     A naming tree, described in detail below, is updated in step  120 . It should be noted that this step can include determining new names. In step  125 , a search is made for updated names in the naming tree. It is this search that lessens the time spent while determining π patterns. Counters are updated in step  130  for the updated names. This step may also comprise updating location lists. In step  135 , it is determined if the end of the string has been reached. If it has not (step  135 =NO), then the window  170  is moved one character to the right (in this example), as shown by reference  160 . Method  100  continues until the end of the string is reached (step  135 =YES), when the window size is changed in step  140 . If the window size is not greater than the size of the string (step  145 =NO), method  100  continues in step  110 . If the window size is greater than the size of the string, the method ends in step  150 , where the patterns that appear greater than K times are output as permutation patterns.  
         [0064]     Method  100  will now be described in more detail.  
         [0065]     The method  100  maintains, in step  120  for instance, an array NAME [1 . . . |Σ|] where NAME[q] keeps count of the number of appearances of letter q in the current window. Hence, the sum of the values of the elements of the NAME array is l. In each iteration the window shifts one letter to the right, and at most 2 variables of the NAME array are changed: one is increased by one (e.g., adding the rightmost letter) and one is decreased by one (e.g., deleting the leftmost letter of the previous window).  
         [0066]     Note that for a given window s a s a +1 . . . s a+l−1  the NAME array represents Π′(s a s a+1  . . . s a+l−1 ). There is one difference between the NAME array and Π′, and that is that in Π′ only the letters of Π are considered and, in the NAME array, all letters of Σ are considered, but the values of letters that are not in Π are zero. At iteration j of steps  115  through  135 , the NAME array is defined to represent the substring s j  . . . s j+l−1 .  
         [0067]     An observation can be made that substrings of S, of length l, that are permutations of the same string are represented by the same array NAME.  
         [0068]     It has been explained how the NAME arrays of all substrings of length l of S are computed. The NAME arrays that appear more than K times still need to be found.  
         [0069]     In an embodiment of the present invention, each distinct NAME array is given a unique name, which is an integer in the range 0 . . . n. The choice of assigning an integer is arbitrary, as any code could be used for a name. The names are given by using the naming technique, described below.  
         [0070]     A suitable naming technique is described as follows. Assume, for the sake of simplicity, that |Σ| is a power of 2. (If |Σ| is not a power of 2, the NAME array can be extended to an appropriate size by concatenating to its end repeated −1. The size of the resulting array is no more than twice the size of the original array.) A name is given to each subarray of size 2 i  that starts on a position j2 i +1 in the array, where 0≦i≦log |Σ| and 0≦j≦|Σ|/2 i . Names are given first to subarrays of size 1 then 2, 4, . . . |Σ|, at the end a name is given to the entire array.  
         [0071]     A subarray of size 2 i  is a concatenation of 2 subarrays of size 2 i-1 . The names of these 2 subarrays are used as the input for the computation of the name of the subarray of size 2 i . The process may be viewed as constructing a naming tree, which can be considered, in an exemplary embodiment, to be a binary tree. The naming tree has a number of levels. The leaves of the tree (e.g., at level 0, as shown below) are the elements of the initial array. Node x in level i is the parent of nodes 2x−1 and 2x in level i−1.  
         [0072]     An exemplary naming strategy is as follows. A name is a pair of previous names. At level j of the naming, we compute the name of subarray NAME 1 NAME 2  of size 2 j , where NAME 1  and NAME 2  are consecutive subarrays of size 2 j-1  each. In an exemplary embodiment, names are given as natural numbers in increasing order. Notice that every level only uses the names of the level below it, thus the names used at every level are numbers from the set {1, . . . , n}.  
         [0073]     To give an array a name, it is only necessary to know if the pair of names of the composing subarrays has appeared previously. If it did, then the array gets the name of this pair. Otherwise, it gets a new name. It is necessary, therefore, to show a quick way to dynamically access pairs of numbers from a bounded range universe.  
         [0074]     An example will help to explain this. Let the alphabet be as follows: Σ={a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p}, |Σ|=16. Assume a substring cboljikgikl of S, the NAME that represents this substring is as shown in  FIG. 3A . The term NAME refers to row  250  and each entry in rows  210 - 240 . Each name also represents a pattern, which will be used to determine permutation patterns (e.g., patterns that occur≦K times). Additionally, the rows  210 - 250  can be considered sets of names. The row  250  has the leaves, and each entry  250 - 1  through  250 - 16  corresponds to a character of the alphabet. For instance, entry  250 - 1  has a value of zero and corresponds to the number of characters “a” there are in the substring. Entry  250 - 2  has a value of one and corresponds to the number of characters “b” there are in the substring. Similary, entry  250 - 9  has a value of two and corresponds to the number of characters “i” there are in the substring, while entry  250 - 16  has a value of zero and corresponds to the number of characters “p” there are in the substring. The entry  240 - 1  is a name assigned to the value “ 01 ” from the pair  250 - 1  and  250 - 2 . Similarly, the entry  230 - 1  is a name assigned to the value “ 43 ” from the pair  240 - 1  and  240 - 2 .  
         [0075]     Suppose the window move adds the character n. (It should be noted that no character drops off in this example; instead the window grows in size to encompass the character n.) In the diagram shown in  FIG. 3B , the names that changed as a result of the change to the naming tree are shown in shading.  
         [0076]     From this example, one can see that a single change in the array NAME causes at most |Σ| names to change, since there is at most one name change in every level  210  through  250 .  
         [0077]     It can be shown that at every iteration, only O(log |Σ|) names need to be handled, since only two elements of array NAME are changed.  
         [0078]     It has been shown that the name of the NAME array can be maintained at a cost of O(log |Σ|) per iteration. What should be found is whether the updated NAME array gets a new name, or a name that appeared previously. Before an efficient implementation of this task is shown, the maximum number is bound for different names needed to generate for a fixed window size l.  
         [0079]     It can be shown that the maximum number of different names generated by the techniques of the present invention&#39;s naming of size l window on a text of length n is O(n log |Σ|). The maximum number of names generated at a fixed level j in the naming tree is  0 (n).  
         [0080]     A pair recognition problem is now discussed. It was shown earlier that it is beneficial to show a quick way to dynamically access pairs of numbers from a bounded range universe. Formally, a solution to the following problem is to be found:  
         [0081]     The dynamic pair recognition problem is the following: 
        INPUT: A sequence of queries {(a j , b j )} j=1   ∞  where a,b j ∈{1, . . . , j}.     OUTPUT: Dynamically decide, for every query (a j , b j ), whether there exist c, c&lt;i such that (a j , b j )=(a c , b c ).        
 
         [0084]     At any point j, the pairs being considered all have their first element no greater than j. Thus, accessing the first element can be done in constant time by direct access. This suggests “gathering” all pairs in trees rooted at their first element. However, if it can be assured that these trees are ordered by the second element and balanced, elements can be found by binary search in time that is logarithmic in the tree size.  
         [0085]     The above solution, for the pair recognition problem, can be determined, when solving each query (a j , b j ), through a search on a balanced search tree with all previous queries whose first pair element is a j . Since in every level there are at most O(n) different numbers, the time for searching such a balanced search tree is O(log |BAL[a]|)=O(log(n)). Balanced search trees are described in Introduction to Algorithms, T. Cormen, C. Leiserson, and R. Rivest, MIT Press, 381-399 (1991), the disclosure of which is hereby incorporated by reference.  
         [0086]     The above technique gives names to many parts of NAME. Special attention is given to leaves, in the balanced search trees, that represent names of the entire array NAME. In other words, a leaf could represent one row  250  of  FIG. 3 . In Step l of method  100  of  FIG. 2 , all the patterns of one π pattern will reach the same leaf. A counter can be added to each leaf that finds if the number of occurrences is at least K. Additionally, a location list can be added to each leaf.  
         [0087]     The time complexity of Stage 1, method  100  of  FIG. 1 , may be computed as follows. Stage 1 runs L times. In a step l, NAME and the naming tree are initialized in O(l+|Σ|) time and then compute n-l iterations are computed. Each iteration includes at most two changes in NAME, and the computation of O(log |Σ|) names. Computing a name takes O(log n) time. Hence the total running time of Stages 1 and 2 is O(Ln log |Σ| log n).  
         [0088]     Turning now to  FIG. 4 , an exemplary computer system  300  is shown for determining permutation patterns, in this example maximal permutation patterns  340 , from an input string  340 . Computer system  300  comprises a processor  310  coupled to memory  315 , which comprises a pattern discovery process  320 , a naming tree  325 , counters  330 , location lists  335 , and database  337 . The pattern discovery process  320  takes one or more input strings  305  and determines maximal permutation patterns  340 , as described above. The pattern discovery process  320  performs Stages 1 and 2 as described above. In the example of  FIG. 1 , the counters are used to store how many times each named pattern occurs and are stored separately, in this example, from the location lists  335  and naming tree  325 . The location lists  335  tell where the patterns occur. As described above, one way to implement naming tree  325 , counters  330 , and location lists  335  is through a balanced search tree  345 . Balanced search tree  345  comprises a number of nodes  350 - 1  through  350 - 5 , of which nodes  350 - 2 ,  350 - 3 , and  350 - 5  are leaves.  
         [0089]     Database  337  may be used to store results from previous calculations using the present invention. Database  337  may be used, for instance, in the following manners. Given a database  337 , D, and a query sequence s, then D may be used to check how similar s is to zero elements, one element or several elements in D. The similarity could be in terms of “local composition.” This translates to finding permutation patterns that are common to s and D. Then the techniques of the present invention may be used to detect these regions of similarity.  
         [0090]     The present invention described herein may be implemented as an article of manufacture comprising a machine-readable medium, as part of memory  315  for example, containing one or more programs that when executed implement embodiments of the present invention. For instance, the machine-readable medium may contain a program configured to perform steps in order to perform Stages 1 and 2 described above. The machine-readable medium may be, for instance, a recordable medium such as a hard drive, an optical or magnetic disk, an electronic memory, or other storage device.  
         [0091]     It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.