Patent Publication Number: US-7917305-B2

Title: System and method for identifying a gapped permutation pattern

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to a system and method for identifying gapped permutation patterns, as within a genome sequence. 
     2. Description of the Related Art 
     As research in genomic science evolves, there is a rapid growth in the number of available complete genome sequences. To date about a dozen species of animals have had their complete Deoxyribonucleic acid (hereinafter “DNA”) sequence determined and the list is growing. The knowledge of gene positions on a chromosome, combined with the strong evidence of a correlation between the position and the function of a gene makes the discovery of common gene clusters invaluable firstly for understanding and predicting gene/protein functions and secondly for providing insight into ancient evolutionary events. 
     The list of species whose complete DNA sequence have been read, is growing steadily and it is believed that comparative genomics is in its early stages. Permutations on sequences representing gene clusters on genomes across species are being studied under different models, to cope with this explosion of data. The challenge is to intelligently and efficiently analyze genomes in the context of other genomes. 
     In recent years, this problem has been modeled and studied intensively by the research community. One conventional method for modelling a genome sequence allows only orthologous genes. This conventional method models genomes as permutations. This method defines a “common interval” to be a pair of intervals of two given permutations consisting of the same set of genes. The number of such intervals, N O , can be quadratic in the size of the input, N I . This method gives an optimal O(N1+N0) time algorithm based on a clever observation of a monotonicity of certain integer functions. 
     This result was then extended to m≧2 permutations by another conventional method. This method introduced the idea of “irreducible” intervals, whose number can be only linear in the size of the input. This method offered an optimal O(N1) time algorithm to detect all of the irreducible intervals and, based on this, the method provides an optimal O(N1+N0) algorithm for the general problem with m≧2 permutations. 
     The problem of identification of common intervals has been revisited by another conventional method which formalized the notion of distance-based clusters: this allows the genes in a cluster to be separated by gaps that do not exceed a pre-defined threshold. Such clusters are termed gene teams and they are constrained to appear in all given m sequences. This conventional method presents an O(mn log 2  n) algorithm to detect the gene teams that occur in m sequences defined on n genes (alphabet). 
     A slightly modified conventional method for modeling a genome sequence allows paralogs and a pattern discovery framework was formalized for a setting in which a pattern is a gene cluster, that allows for multiplicity. In other words, paralogous genes within a cluster appearing a quorum of K&gt;1 times. K is a quorum parameter that is usually used in the context of patterns. 
     Formally, the following problem has been addressed: 
     Given m strings (with possible multiplicity) on Σ of length n i  each, and a quorum parameter K, the task is obtain all permutation patterns p that occur in at least K sequences. 
     This problem typically uses m=1, however, it can be trivially modified to deal with an m&gt;1 scenario. 
     The algorithm for solving this problem is based on Parikh-maps and has a time complexity of O(Ln log|Σ|log n) where L (&lt;max i (n i )) is the size of the largest cluster and n=Σ i (n i ). Then, the notion of “maximal” permutation patterns or clusters was introduced. Maximality is a non-trivial notion requiring a special notation. In this notation the maximality has been represented by a PQ tree, and a linear time algorithm has been used to compute the maximality for each pattern (cluster). 
     Using a similar model of genomes as sequences, rather than permutations, another conventional method uses an Θ(n 2 ) algorithm for extracting all common intervals of two sequences. This notion of gene teams was extended to clusters of orthologous genes (hereinafter “COG”) teams by allowing any number of paralogs and orthologs, and a O(mn) time algorithm to find such COG teams was devised for pairwise chromosome comparison where m and n are the number of orthologous genes in two chromosomes. 
     As the number of genomes under study grows in number, it becomes important to handle not only distance-based clusters (or gapped clusters), but also cluster co-occurrence in some subset and not necessarily all of the m genomes. Again, maximality is an important idea that not only preserves the internal structure, but also cuts down on the number of clusters without loss of information. The conventional systems have not been adequate in handling the above challenges. 
     Further, conventional systems and methods are not capable of handling wild cards or gaps and the occurrences of the sequences must be exact. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing and other exemplary problems, drawbacks, and disadvantages of the conventional methods and structures, an exemplary feature of the present invention is to provide a method and system in which gapped permutation patterns are identified. 
     In a first exemplary aspect of the present invention, a method of identifying gapped permutation patterns includes discovering all clusters in an input data sequence that occur with a predetermined gap. 
     In a second exemplary aspect of the present invention, a system for identifying gapped permutation patterns includes means for discovering all clusters in an input data sequence that occur with a predetermined gap. 
     In a third exemplary aspect of the present invention, a program embodied in a computer readable medium executable by a digital processing system for identifying gapped permutation pattern includes instructions for discovering all clusters in a input data sequence that occur with a predetermined gap. 
     An exemplary embodiment of the present invention provides a generalized model that uses three notions: (1) gapped gene clusters, with gap g; (2) genome clusters, via quorum parameter, K&gt;1; and (3) possible multiplicity in the clusters. This embodiment automatically discovers all clusters (with possible multiplicity), that occur with a gap, g, in at least, K genomes. 
     An exemplary embodiment of the present invention uses an output-sensitive algorithm to detect all maximal clusters and applies this to the study of comparisons of gene orders of chloroplast DNA data. 
     An exemplary embodiment of the present invention provides a generalized model that uses two of the notions discussed above: 1) gapped gene clusters, with gap g; and, (2) genome clusters, with possible multiplicity, via a quorum parameter, K&gt;1. This embodiment automatically discovers all permutation patterns (with possible multiplicity) occurring with a gap of at most g in at least K of the given m sequences. The use of (1) the quorum parameter (m≧K&gt;1) with multiplicity in the input and (2) multiple sequences (m≧2) distinguishes this embodiment from the previous gapped cluster models. In the first, K is fixed at m, without multiplicity, and in the second, m is fixed at 2. Although, for the purposes of the description in this specification, a gap g is defined in terms of the number of intervening genes, it can be simply generalized to other definitions of gap (such as actual location on the chromosome, distance from a target gene, and the like) as is understood by those of ordinary skill in the art. 
     In an exemplary embodiment of the present invention, when g=0, the problem has a O(Ln log|Σ|log n) time solution, where L is the size of the pattern. When g=0, the size of the output is no more than Σ i (n i   2 ). The inventors also note that when g&gt;0, multiple patterns may occur with the same imprint and, thus, the output size could be potentially exponential in the input parameter (e.g., m). When g is very large, the problem has an output-sensitive algorithm. 
     Note that if p∈P g , it is possible that p∉P 0  and there is no p′∈P 0  such that p can be deduced from p′. But if p∈P g , then there must exist p″∈P ∞  such that p ⊂ p″ and the occurrences of p can be deduced from the occurrences of p″. The inventors rely upon this as a handle to solve a 0&lt;g&lt;∞ case. This problem may be solved in two stages. In the first stage, the problem for large gaps (g=∞) is solved. In fact, since the number of patterns is very large, only the maximal permutation patterns are computed. The solution of the first stage is used to construct the solutions for the given gap g. The overall time complexity of this two-stage algorithm is:
 
O(log mN I +|Σ|log|Σ|N O )
 
     where: 
     N I  is the size of the input and N O  is the size of the output. 
     For the sake of completeness, a method is provided to extract all the non-maximal patterns out of the maximal patterns of the last stage. 
     These and many other advantages may be achieved with the present invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The foregoing and other exemplary purposes, aspects and advantages will be better understood from the following detailed description of an exemplary embodiment of the invention with reference to the drawings, in which: 
         FIG. 1A  illustrates instructions for a program executable by a digital processing unit for identifying gapped permutation patterns in accordance with an exemplary embodiment of the present invention; 
         FIG. 1B  illustrates a flowchart  100  of an exemplary method in accordance with the present invention; 
         FIG. 2A  illustrates a sample array of ordered lists for a dictionary in accordance with an exemplary embodiment of the present invention; 
         FIG. 2B  illustrates an implicit tree generated by a recursive routine in accordance with an exemplary embodiment of the present invention; 
         FIG. 3  illustrates further elements of the sample data from  FIGS. 2A and 2B  in accordance with the present invention; 
         FIG. 4  illustrates a typical hardware configuration which may be used for implementing an exemplary embodiment of the present invention; and 
         FIG. 5  illustrates a program embodied in a computer readable medium  500  and  502  executable by a digital processing unit in accordance with an exemplary method of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS OF THE INVENTION 
     Referring now to the drawings, and more particularly to  FIGS. 1A-5 , there are shown exemplary embodiments of the method and structures of the present invention. 
     For the purposes of the following detailed description, the following notations are described. 
     A genome or chromosome is denoted by a sequence s which is defined on the genes or a finite alphabet Σ. s[i . . . j] denotes the subsequence of s from ith to the jth element. Also, a gene cluster is referred to as a “pattern” (or permutation pattern or π pattern). 
     Given a sequence s on Σ: 
     Π(s)=σ∈Σ|, σ=s[i] (for some 1≦i≦|s|); and 
     Π′(s)=α(t)|α∈Π(s). 
     where:
         t is the number of times that α appears in s.       

     For example, if s=abcda, then Π(s) {a,b,c,d}. And, if s=abbccdac, then Π′(s)={a(2), b(2), c(3), d}. 
     Given a sequence s on Σ, a set p∈2 Σ  occurs at position i on s with gap g if all the following hold: 
     (1) s[i]∈p (this ensures that the very first character is not a gap); 
     (2) l is the smallest number such that p ⊂ Π(s[i . . . (i+l−1)]) (this ensures that the very last character is not a gap); and 
     (3) if for every pair i≦i 1 &lt;i 2 ≦(i+l−1) with s[i 1 ], s[i 2 ]∈p, and for all j, i 1 &lt;j&lt;i 2 , s[j]∉p, the distance between i 1  and i 2  is no more than g i.e., (i 2 −i 1 −1)≦g holds. In other words, there are at most g gaps between any two non-gap (solid) characters. 
     Further, the subsequence s[i . . . (i+l−1)] is an imprint of p at location i. For example, let p 1 {1,2,3} with s 1 =51382679 and gap g=1. Then the imprint of p 1  at location 2 is boxed in s 1 =51382679. Also, if p 2 ={1,2,7} with g=2, then the imprint of p 2  at location 2 is shown as s 1 =51382679. 
     Given m sequences s i (1≦i≦m) each on alphabet Σ, a quorum parameter 1&lt;K≦m and a gap 0≦g, p∈2 Σ  is a permutation pattern or a π pattern with quorum parameter K, if location list L g   p ={(i,l,u)|p occurs with gap g and imprints si[l,u]} is such that |L g   p |≧K. 
     In the following, assume that P is the set of all π patterns on the given m sequences. Note that if p∈P, it does not imply that any (p′⊂p)∈P. So, maximality in permutation patterns is not straightforward and is defined as: 
     Given P, p a ∈P is non-maximal if there exists p b ∈P such that: (1) the imprint of each occurrence of p a  is contained in the imprint of an occurrence of p b , and, (2) the imprint of each occurrence of p b  contains l≧1 imprints of occurrence(s) of p a . A pattern p b  that is not non-maximal is maximal. 
     It has been shown that when the gap g=0, there is a concise notation to represent all the non-maximal patterns of p and it has also been shown that these non-maximal patterns can be arranged as a PQ tree structure. It has also been demonstrated that when gap g=0, with multiplicity in the patterns, a single PQ tree may fail to capture all the non-maximal patterns. 
     The inventors illustrate here that when the gap g&gt;0, there is no straightforward representation using a single PQ structure. Consider the following example: Let s 1 =abcdefghj and s 2 =bjdgfehcl with a quorum parameter K=2 and a gap g=1. Consider the following: 
     p 0 ={c,e,g,j,b,d,f,h}, p 1 ={b,d,f,h}, p 2 ={c,e,g,j}, p 3 ={e,g,d,f}, p 4 ={c,e,d,f}, p 5 ={g,j,b,d}, p 6 ={c,e,b,d}, p 7 ={c,e,j,b}, p 8 ={c,b,d,h}, 
     For g= 1 , p 0 , p 1 , p 2 , p 3  and p 4  are π patterns but p 5 , p 6 , p 7  and p 8  are not. Note that p 1 , p 2 , p 3 , p 4  are non-maximal with respect to p 0 . It is easy to see that a single PQ structure cannot succinctly represent the π patterns. 
     The reason for using maximal patterns, although there is no convenient structure representing it, is that the number of patterns is smaller and the over-counting caused by non-maximal patterns is avoided here as is described below. 
     The inventors use the following definition of maximality: 
     Given P, p a ∈P is non-maximal if there exists (p b ⊃p a )∈P such that the imprint of each occurrence of p a  is contained in the imprint of an occurrence of p b . A pattern p b  that is not non-maximal is maximal. 
     For the remainder of the detailed description input size, N 1 , and output size, N 0 , are defined as follows: 
     
       
         
           
             
               
                 mod 
                 * 
                 0.5 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 in 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     N 
                     1 
                   
                   ⁡ 
                   
                     ( 
                     
                       s 
                       , 
                       m 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   m 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                      
                     si 
                      
                   
                   ⁢ 
                   mod 
                   * 
                   0.2 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   in 
                 
               
             
             ; 
           
         
       
       
         
           and 
         
       
       
         
           
             
               mod 
               * 
               0.2 
               ⁢ 
               
                   
               
               ⁢ 
               in 
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   N 
                   0 
                 
                 ⁡ 
                 
                   ( 
                   P 
                   ) 
                 
               
             
             = 
             
               
                 ∑ 
                 
                   p 
                   ∈ 
                   P 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   ( 
                   
                     
                        
                       p 
                        
                     
                     + 
                     
                        
                       
                         L 
                         p 
                       
                        
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
     Let P g  denote the maximal patterns with gap g. The following example demonstrates the case when the output size can be exponential. Let s 1 =2345, s 2 =1345, s 3 =2645, s 4 =2375, s 5 =2348 and K=2 and gap g=1. Then P 1 ={{2}, {3}, {4}, {5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {2,3,4}, {2,3,5}, {3,4,5}, {2,4,5}}. Thus P 1 =(2 m ) Next, a collection of sequence indices of a pattern p is defined as follows: (Lst(L g   p )) Given L g   p :
 
 Lst ( L   p   g )={ i| ( i ,−,−)∈ L   p   g }
 
     A gapped permutation problem may be defined as follows. Given m sequences s i  defined on a finite alphabet Σ and some integer g≧0 and K&gt;1, the task is to find P, which is the collection of maximal π patterns that occur on s with gap g and quorum K. 
     One of the main problems with permutation patterns is that they cannot be built from smaller units (as in sequence patterns, say). In other words, p 1  and p 2  may not be a permutation pattern, but p 1 ∪p 2  could be a permutation pattern. For example, consider s 1 =71234578, s 2 =624139 with K=2 p 1 ={1,2} and p 2 ={3,4} are not permutation patterns but p=p 1 ∪p 2 ={1,2,3,4} is a permutation pattern. 
     This problem is compounded with gapped occurrences of the patterns. Earlier the inventors described a Parikh-mapping based solution that used a fixed window size (pattern size). This is indeed the gapped π pattern problem with g=0. However, the use of a non-zero gap parameter makes a similar approach rather laborious and impractical. 
     If a g=g max  such that P g′ =P g     max    for all g′&gt;g max  is identified, then it is easy to see that:
 
 g   max =(max i=1   m   |s   i |)−2  (2)
 
     This identification may be performed in accordance with an exemplary embodiment of the present invention by executing the instructions that are illustrated in  FIG. 1 . 
     The application of the instructions of  FIG. 1A  is illustrated on sample data in  FIGS. 2   a  and  2   b  and  FIG. 1B  illustrates a flowchart  100  of one exemplary method in accordance with the present invention. 
     The exemplary method starts at step  102  and continues to step  104  where the method inputs the sequences and continues to step  106  where the method inputs a predetermined gap, g. 
     For sample data: s1=beda, s2=edbabed, sc=bbfcdb, and s4=cafbebb, with K=3. The dictionary Dic, which is an array of ordered lists, is illustrated by  FIG. 2   a .  FIG. 2   b  illustrates an implicit tree that is generated by a recursive routine MineMaxπPat( ) in accordance with step  108  of the flowchart of  FIG. 1B . Each call is shown as a node, labeled with S[1] and a (descending) branch, labeled with σj(l) (when l=1, the annotation is omitted). Also, if |S[1] (K=3) it is not shown, to avoid clutter. 
     The number of calls is 
                  Σ        ⁢       ∑     p   ∈     P   ∞         ⁢           ⁢          p        .             
Hence the algorithm takes (N I (s,m)+|Σ|N O (P ∞ )m log m) time where N I (s,m) and N O (P ∞ ) are the sizes of the input and output respectively (see Equation (1) for N I  and N O )
 
     In step  110  of the flowchart  100  of  FIG. 1B , using the results of the last section, the maximal permutation patterns that occur with gap g(&lt;∞) are extracted. 
     At the end of step  110 , the maximal permutation patterns, p that occur with ∞ gaps is stored in a balanced binary tree data structure. A maximal permutation pattern p′ that occurs with gap g is obtained from a maximal pattern p with p′ ⊂ p where p occurs with ∞ gap as follows: 
     Let the imprint of p in s i  be s i [j i1     ∞   , j i2     ∞   ], i∈Lst(L p   ∞ ). Let p′ ⊂ p be a maximal set (permutation pattern) such that imprint of p′ with gap g on s i  is given as s i [j i1     g   , j i2     g   ] where j i1     ∞   ≦j i2     g   ≦j i2     ∞   , for some i∈Lst(L p   ∞ ). Following this notation, the collection of i&#39;s for a p′ is defined as follows (i.e., the i&#39;s where p′ occurs with gap g):
 
 L′={ ( i∈Lst ( L   p   ∞ ))| j   i1     ∞     ≦j   i1     g     ≦j   i2     g     ≦j   i2     ∞   }.
 
     For the case where (p′=p), then L′=Lst(L p   ∞ ) and p is a maximal permutation pattern that occurs with gap g and Lgp=L∞p 
     For the case where (p′⊂p), in a first sub-case: 
     Let L′⊂Lst (L p   ∞ ) , then obtain p 1  and p 2  (not necessarily distinct) from the data structure that was computed in Stage 1), such that Lst(L P     1     ∞ ) ⊃ L′ ⊃ Lst(L P     2     ∞ ). It is easy to see that p ⊂ p 1   ⊂ p 2 . Now p′ is augmented to p″ where p″ ⊂ p 1 \(p\p′) and p″ occurs with gap g on each s i , i∈′. 
     For the case where (p′⊂p), in a second sub-case: 
     Let L′=Lst(L p   ∞ ). Then obtain p 1  and p 2  (not necessarily distinct) from the data structure T that was computed in Stage 1, such that p 1   ⊂ p′ ⊂ p 2 . Then it is easy to see that Lst (L p     1     ∞ )  ⊃ L′ ⊃ Lst (L p     2     ∞ ). Now L is augmented to L′ where L √   ⊂ Lst (L p     2     ∞ ) and p″ occurs with gap g on each s i , i∈L″. 
     The inventors next illustrate that p′ is a maximal permutation pattern that occurs with gap g. This can be easily verified (using proof by contradiction). Next, L is computed from L″ (recall L″=Lst (Lgp)). The search (for p 1  and p 2 ) in the two sub-cases can be done in (|Σ|) time Thus this stage takes time O(|Σ|N O (P g )). 
     If only the maximal permutation patterns are desired, then the method illustrated by the flowchart  100  of  FIG. 1B  may skip ahead to step  114 , where the patterns are output and continue to step  116  where the method stops. However, if it is desired to obtain all permutation patterns, step  112  may be optionally provided. In step  112 , each maximal permutation pattern is processed to obtain the non-maximal patterns and may subsequently continue to step  114  where all the patterns are output. 
     For a restricted g-gap π pattern problem, where g-RGPP(s, m, P)), the input is m sequences s i  each of length n i , defined on a finite alphabet Σ where Π′(s i )=Π′(s j ) for each 1≦i, j&lt;m. The output is all permutation patterns that occur with gap g in at least K sequences. 
     Since Π′(s i )=Π′(s j ), for all 1≦i, j≦m, an exemplary embodiment of the present invention assigns integers to the characters. The input is converted to integers as follows. First, all of the patterns that occur in s 1  are desired. So, let s 1  be the reference sequence. Since there is possible multiplicity in s 1 , the mapping is not necessarily one-to-one and if σ(l)∈Π′(s 1 ), then σ is mapped to a set of l integers. In other words, F(σ)={j|s 1 [j]=σ}. 
     The size of a pattern p is defined to be sz(p)=Σ σ(l)∈Π′(P) (l). Note that when p has no multiplicities, sz(p)=|Π(p)|, 
     Any pattern p that occurs with gap g on all k sequences is such that there exists an ordering f(σ 1 )&lt;f(σ 2 )&lt; . . . &lt;f(σ sz(p) ) satisfying the condition (f(σ i+1 )−f(σ i ))≦(g−1), for each 1≦i&lt;sz(p), where σ i ∈Π(p) (σ i  a not necessarily distinct from σ j  when i≠j), and f(σ i )∈F(σ i ) for 1≦i≦sz(p). Let s 1 =abcdb and s 2  dbbac. Using s 1  as the reference sequence, the integer mappings are as follows: F(a)={1}, F(b)={2,5}, F(c)={3}, F(d)={4}. Note that p={b(2),c(1)} is a pattern that occurs in both s 1  and s 2 , and, the ordering (f(b)=2)&lt;(f(c)=3)&lt;(f(b)=5) satisfies the condition of observation for gap g=1. 
     The inventive method performs an ordered search by scanning each string s i , i&gt;1, (s 1  is the reference sequence) from left to right. First, a left pointer is fixed at j l  and a right pointer j r  is moved from j l +1 to the end of the string. At each scan, the exemplary embodiment searches for a pattern that occurs on s i  with an imprint s i [j l  . . . j r ]. 
     This ordered search is best explained through an example. Continuing Example 1, s 2  is written in terms of integers as: s 2′ ={4}{2,5}{2,5}{1}{3}. Let j l =1 and j r =2. The elements of s 2′ [j l  . . . j r ] (4, and, 2 or 5) are shown boxed in  FIG. 3 . The two orderings (1) q 1 =2&lt;4 and (2) q 2 =4&lt;5, satisfy the conditions of observation. The p corresponding to an ordering q is defined as p={σ|k∈qandk ∈F(σ)}. In the running example, p={b,d} occurs in s 1  with imprints s 1 [2 . . . 4] and s 1 [4 . . . 5]. p occurs in s 2  with imprint s 2 [j l  . . . j r ]. Thus, L p   g ={(1,2,4),(1,4,5),(2,1,2)}. At each scan, there are two mandatory integers, corresponding to s 2′ [j l ] and s 2′ [j r ] (shown in bold in  FIG. 3 ). Any valid sub-sequence that satisfy conditions of observation must contain these mandatory elements and must occur on s 2  with a gap g at s 2 [j l  . . . j r ]. 
     Consider another example, where the patterns (and their location lists) generated as j l  is fixed at 1 and j r  moves from 2 to 5 on s 2′ . 
     Each pattern that is extracted in the last step is stored in a balanced tree data structure, say “Tg.” At the end of the process, the patterns on the node of this tree are checked to see if they appear in at least K of the given sequences. 
     The time taken at each scan to compute all the orderings is O(gL log L), where L=j r −j l +1. For a reference sequence, s i , the scan is repeated for each j l , 1≦j l &lt;n and for each sequence s j , j≠i. At the end, the data structure T needs to be scanned only once. Thus, the total time taken to obtain all the patterns is O(gm 2 n 2  log n). 
     The following briefly discusses the results of using gapped permutation patterns on a practical application in accordance with an exemplary embodiment of the present invention. One of the established methods to compare a collection of genomes is to infer a phylogeny amongst them and the inventors used such a study on gene orders of chloroplast DNA data. The inventors study involved simulated data as well as real data. In interest of brevity, this description presents only the results seen on the real data of a chloroplast gene order of Campanulaceae data. The data set has about 105 genes in 13 extant species. The details of the phylogeny construction algorithm appeared. 
     In  FIG. 3 , using a gap parameter of 1, 2 and 4. The inventors found that the number of maximal patterns with a gap g=1 is 193, with a gap g=2 is 209 and with a gap g=4 is 220. Also, a gap g=° gives 167 maximal patterns. The gap parameters 0 and 1 reconstruct the same phylogeny tree. Curiously, the gap parameters g=2 and g=4 give the phylogeny trees that are reconstructed using other approaches (such as reversal and breakpoint methods). Also, gaps of 2 and 3 give the same phylogeny tree. 
     The resulting phylogeny tree with gaps g=1,2,4 respectively. 
     An exemplary embodiment of the present invention provides a generalized model that uses maximal gapped patterns on a subset of genomes. The subset of the genomes is dictated by the quorum parameter K. The gaps also help to handle noisy and incomplete data. 
     An exemplary embodiment of the present invention provides an output that is sensitive to compute all of the permutation patterns. 
     Referring now to  FIG. 4 , system  400  illustrates a typical hardware configuration which may be used for implementing the inventive system and method for identifying a gapped permutation pattern. The configuration has preferably at least one processor or central processing unit (CPU)  410 . The CPUs  402  are interconnected via a system bus  412  to a random access memory (RAM)  414 , read-only memory (ROM)  416 , input/output (I/O) adapter  418  (for connecting peripheral devices such as disk units  421  and tape drives  440  to the bus  412 ), user interface adapter  422  (for connecting a keyboard  424 , mouse  426 , speaker  428 , microphone  432 , and/or other user interface device to the bus  412 ), a communication adapter  434  for connecting an information handling system to a data processing network, the Internet, and Intranet, a personal area network (PAN), etc., and a display adapter  436  for connecting the bus  412  to a display device  438  and/or printer  439 . Further, an automated reader/scanner  441  may be included. Such readers/scanners are commercially available from many sources. 
     In addition to the system described above, a different aspect of the invention includes a computer-implemented method for performing the above method. As an example, this method may be implemented in the particular environment discussed above. 
     Such a method may be implemented, for example, by operating a computer, as embodied by a digital data processing apparatus, to execute a sequence of machine-readable instructions. These instructions may reside in various types of signal-bearing media. 
     Thus, this aspect of the present invention is directed to a programmed product, including signal-bearing media tangibly embodying a program of machine-readable instructions executable by a digital data processor to perform the above method. 
     Such a method may be implemented, for example, by operating the CPU  410  to execute a sequence of machine-readable instructions. These instructions may reside in various types of signal bearing media. 
     Thus, this aspect of the present invention is directed to a programmed product, comprising signal-bearing media tangibly embodying a program of machine-readable instructions executable by a digital data processor incorporating the CPU  410  and hardware above, to perform the method of the invention. 
     This signal-bearing media may include, for example, a RAM contained within the CPU  410 , as represented by the fast-access storage for example. Alternatively, the instructions may be contained in another signal-bearing media, such as a magnetic data storage diskette  500  or CD-ROM  502 , ( FIG. 5 ), directly or indirectly accessible by the CPU  410 . 
     Whether contained in the computer server/CPU  410 , or elsewhere, the instructions may be stored on a variety of machine-readable data storage media, such as DASD storage (e.g., a conventional “hard drive” or a RAID array), magnetic tape, electronic read-only memory (e.g., ROM, EPROM, or EEPROM), an optical storage device (e.g., CD-ROM, WORM, DVD, digital optical tape, etc.), paper “punch” cards, or other suitable signal-bearing media including transmission media such as digital and analog and communication links and wireless. In an illustrative embodiment of the invention, the machine-readable instructions may comprise software object code, complied from a language such as “C,” etc. 
     While the invention has been described in terms of several exemplary embodiments, those skilled in the art will recognize that the invention can be practiced with modification. 
     Further, it is noted that, Applicant&#39;s intent is to encompass equivalents of all claim elements, even if amended later during prosecution.