Abstract:
A method for discovering a fuzzy bi-cluster is disclosed. The method includes reading a matrix comprising rows and columns and reading at least one input parameter specifying a fuzzy bi-cluster. The method further includes discovering in the matrix at least one fuzzy bi-cluster that was specified and storing the at least one fuzzy bi-cluster that was discovered.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     Not Applicable.  
       STATEMENT REGARDING FEDERALLY SPONSORED-RESEARCH OR DEVELOPMENT  
       [0002]     Not Applicable.  
       INCORPORATION BY REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC  
       [0003]     Not Applicable.  
       FIELD OF THE INVENTION  
       [0004]     The invention disclosed broadly relates to the field of data mining and more particularly relates to the field of finding bi-clusters in multi-feature data.  
       BACKGROUND OF THE INVENTION  
       [0005]     A DNA microarray is usually a silicon chip or a nylon membrane, onto which sequences from different genes are immobilized, or attached, at fixed locations, called a spot. The spot is DNA, cDNA, or a fragment of the gene (oligonucleotide) and its location in the array is used to identify the particular DNA sequence. The slide, also called a “DNA chip”, contains thousands of genes and the spots are usually 200 microns or less in size.  
         [0006]     One of the fundamental questions of biology is to understand the nature and extent of interactions of genes and gene products. Genetic interactions are vital to understanding cellular metabolism, development of cells and tissues, response of organisms to their environments and also molecular structure and function. Every cell of every living organism contains a repertoire of identical genes, with only a few exceptions. However, not all of the genes are used in each cell and only a fraction of these genes are turned on—it is the subset that is expressed that confers unique properties to each cell type.  
         [0007]     For example, liver cells express genes for poison-detoxifying enzymes while pancreas cells express insulin-making genes. To know how cells achieve such specialization, there is a need to identify which genes each type of cell expresses. The active genes are transcribed into messenger RNA (mRNA) molecules that are then translated into the proteins that perform most of the critical functions of cells. Thus, the detection of the mRNA produced by a cell indicate which genes are expressed. Gene expression is a highly complex and tightly regulated process that allows a cell to respond dynamically both to environmental stimuli and to its own changing needs. This mechanism acts both as a trigger (an “on/off” switch) to control which genes are expressed in a cell as well as the extent of expression (a “volume control”) that increases or decreases the level as necessary.  
         [0008]     Protein microarrays are also termed “protein chips.” The spots here are that of proteins which are deposited in a manner that preserves their functions: this way, the function of thousands of proteins can be measured simultaneously. The proteome is the cell&#39;s array of proteins and the protein chips provide a glimpse into this data. Although one gene may encode one protein, usually proteins are subject to post-translational modifications and these will always missed be by the DNA or RNA profiling. Protein arrays have been demonstrated in protein-protein, protein-enzyme and protein-small molecule interactions.  
         [0009]     DNA microarray technology allows us to look at many genes at once and determine which are expressed and to what extent, in a particular cell type. Protein microarrays can be viewed similarly, although recent work is more focused on DNA microarrays. This document focuses on DNA microarrays, although any other microarray could be subject to a similar analysis.  
         [0010]     Microarrays usually involve a series of protocols that introduce variability at each step. It is only natural to separate the informatics aspects from understanding this variability in the microarray measurements. Thus, the subject of interpreting the measurements in this emerging microarray technology is far from straightforward and thus this document focuses only on the data that has been appropriately preprocessed.  
         [0011]     The problem is that of finding fuzzy bi-clusters in the microarray data which can be viewed as a two-dimensional array of real numbers with no particular significance to horizontal or vertical adjacency. The current literature allows for discovery of fixed patterns where the columns and rows of a matrix (i.e., a bi-cluster) have a specific value. However, the problem of pattern discovery is compounded with the introduction of approximate (i.e., fuzzy) patterns where most columns or rows, but not all, have a specified value. Approximate patterns are more relevant in finding patterns in gene expressions that are characteristic of a disease and are therefore useful for diagnostics.  
         [0012]     Therefore, there is a need to overcome problems with the prior art as discussed above, and more particularly a need to make the process of discovering patterns in multi-feature data more efficient.  
       SUMMARY OF THE INVENTION  
       [0013]     Briefly, according to an embodiment of the invention, a method for discovering a fuzzy bi-cluster is disclosed. The method includes reading a matrix comprising rows and columns and reading at least one input parameter specifying a fuzzy bi-cluster. The method further includes discovering in the matrix at least one fuzzy bi-cluster that was specified and storing the at least one fuzzy bi-cluster that was discovered.  
         [0014]     In another embodiment of the present invention, an information processing system for discovering a fuzzy bi-cluster is disclosed. The information processing system includes an interface for receiving a matrix comprising rows and columns, and at least one input parameter specifying a fuzzy bi-cluster. The information processing system includes a processor configured for discovering in the matrix at least one fuzzy bi-cluster that was specified. The information processing system further includes a memory for storing the at least one fuzzy bi-cluster that was discovered.  
         [0015]     In yet another embodiment of the present invention, a computer readable medium including computer instructions for discovering a fuzzy bi-cluster is disclosed. The computer instructions includes instructions for reading a matrix comprising rows and columns and reading at least one input parameter specifying a fuzzy bi-cluster. The computer instructions further include instructions for discovering in the at lest one fuzzy bi-cluster that was specified and storing the at least one fuzzy bi-cluster that was discovered.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]     The subject matter, which is regarded as the invention, is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other features and also the advantages of the invention will be apparent from the following detailed description taken in conjunction with the accompanying drawings. Additionally, the left-most digit of a reference number identifies the drawing in which the reference number first appears.  
         [0017]      FIG. 1  is a block diagram illustrating the fuzzy bi-cluster discovery process of one embodiment of the present invention.  
         [0018]      FIG. 2  is an exemplary input matrix, in one embodiment of the present invention.  
         [0019]      FIG. 3  is the input matrix of  FIG. 2  including some selected elements.  
         [0020]      FIG. 4  is the input matrix of  FIG. 2  including some selected elements.  
         [0021]      FIG. 5  is an exemplary input matrix including some selected elements representing a discovered fuzzy bi-cluster, in one embodiment of the present invention.  
         [0022]      FIG. 6  is a high level block diagram showing an information processing system useful for implementing one embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION  
       [0023]      FIG. 1  is a block diagram illustrating the fuzzy bi-cluster discovery process of one embodiment of the present invention.  FIG. 1  includes an input array  102 , representing a two dimensional matrix of values (i.e., a bi-cluster).  FIGS. 2-5  are examples of an input array  102 .  FIG. 1  also includes input parameters  104 , which provide criteria (i.e., a specification or definition) of an approximate fuzzy bi-cluster, which is a two dimensional matrix of values where most columns or rows, but not all, have a specified value, i.e., a fuzzy bi-cluster. Fuzzy bi-clusters are more relevant in gene expressions that are characteristic of a disease and are therefore useful for diagnostics.  FIGS. 3-5  include selected (in bold) elements of an input array  102  that qualify as discovered fuzzy bi-clusters. The input array  102  and the input parameters  104  can be a file, such as a text file, or an electronic transmission including the data of the input array  102  or the approximate fuzzy bi-cluster  104 .  
         [0024]     In an embodiment of the present invention, the input parameters  104  can include one or more defined variables or constants. The values of the input parameter values  104  can be whole numbers or real numbers. For example, the input parameters  104  can include any, or all, of the following defined values. A value k defines the quorum or the minimum number of rows in the fuzzy bi-cluster. A value δ defines a parameter that determines when two real values can be deemed equal (in the instance where the values of the input parameters  104  are real numbers). A value           defines the fraction of the columns of the input array  102  that can deviate from the bi-cluster value. The input parameter values k and           can be different for each column in the bi-cluster.  
         [0025]      FIG. 1  also includes an algorithm  110  for discovering instances of a fuzzy bi-cluster, as specified by input parameters  104 , in the input array  102 . The algorithm  110  is described in greater detail below.  FIG. 1  further includes a result  112  that includes the instances of the fuzzy bi-cluster, as specified by input parameters  104 , that were discovered by the algorithm  110  in the input array  102 . The data represented in the result  112  is described in greater detail below. The result  112  can be a file, such as a text file, or an electronic transmission including the data of the result  112 .  
         [0026]     The algorithm  110  can be executed by a computer system. In an embodiment of the present invention, the computer system implementing the features of the present invention is one or more Personal Computers (PCs) (e.g., IBM or compatible PC workstations running the Microsoft Windows operating system, Macintosh computers running the Mac OS operating system, or equivalent), Personal Digital Assistants (PDAs), hand held computers, palm top computers, smart phones, game consoles or any other information processing devices. In another embodiment, the computer system is a server system (e.g., SUN Ultra workstations running the SunOS operating system or IBM RS/6000 workstations and servers running the AIX operating system). Such as computer system is described in greater detail below with reference to  FIG. 6 .  
         [0027]     As explained above, the algorithm  110  discovers instances of a fuzzy bi-cluster, as specified by input parameters  104 , in the input array  102 . Below is a detailed description of the algorithm  110 , wherein the input array  102  is represented by a matrix A and the input parameters  104  include the values δ, k, and          , as defined more fully above.  
         [0000]     Given A, an r×c array of real numbers and a δ&gt;0. A[i,j] denotes the element in row i and column j. Let R i  represent row i, 1≦i≦r and let C j  represent column j, 1≦j≦c. Below are a few definitions.  
         [0000]     (x 1 ≡x 2  given δ&gt;0) Given δ&gt;0 and x 1 , x 2 εR, x 1 ≡x 2  holds if |x 1 −x 2 |≦δ. If x 1  or x 2  is an interval on          , then x 1 ≡x 2  holds if x 1 ∩x 2 ≠{ }.  
         [0028]     (pattern m, size of m, location list            m ) Given A, an r×c array of real numbers, δ&gt;0 and a positive integer k≦r, a pattern m is a collection of columns of the form m={C j     1   =X 1 , C j     2   =X 2 , . . . C j =X l } occurs at row R i  if A[i, j a ]≡X a , 1≦s≦1. Size of m is denoted by |m| is defined to be l.            m ={i|m occurs at row i} and            m  is complete, i.e., if there exists i such that m occurs at i then iε           m . Also, |           m ≧k holds, i.e., the pattern m occurs at least k times on A.  
         [0000]     (m 1           m 2 ) If for each C j =xεm 1 , there exists C j =x′εm 2  with x1 ⊂ x 2 , then m 1           m 2  holds.  
         [0000]     For example if m 1 ={C 1 =1.2, C 2 =3.6, C 3 =0.3} and m 2 ={C 1 =1.2, C 3 =0.3} then m 2           m 1 . If m 3 ={C 3 =1.2, C 3 =1.3} then m 3           m 2  and m 2           m 3 . Also m 3           m 1  and m 1           m 3 .  
         [0000]     (maximal m) A pattern m={C j     1   =x 1 , C j     2   =x 2 , . . . C j     s   =x 1 } is maximal if there exists no m′ such that m         m′ and            m =           m′ .  
         [0000]     Notice that maximality is a notion with respect to all patterns on a given array A. The basic idea is that if all the information about pattern m 1  is already contained in pattern m 2 , then m 1  is not of any interest.  
         [0000]     Given A, an r×c array of real numbers, δ&gt;0 and a positive integer k≦r, the problem is to find all maximal patterns that occur at least k times on A.  
         [0029]     Notice that for any xε         , for all yε[x−δ, x+δ], x≡y. Consider the example in  FIG. 2 . Let the input A be as follows with δ=0.5 and k=2. Then m 1 ={C 1 =[0.95, 1.45], C 2 =[1.75, 2.25], C 4 =[2.9, 3.4]} with            m     1   ={1, 3}, m 2 ={C 1 =[0.85, 1.35], C 3 =[3.5, 4.5]} with            m     2   ={1, 2} are the maximal patterns. Consider a pattern m 3 ={C 1 =[0.95, 1.45], C 2 =[1.5, 2.5]} with            m     3   ={1, 3}. Notice that m 3  is not maximal and neither is a pattern m 4 ={C 1 =[1.15, 0.95], C 3 =[3.75, 4.25]} with            m     4   ={1, 2}. m 3  is not maximal with respect to m 1  which has the added component C 4 . m 4  is not maximal with respect to m 2  since C 1  interval in m 4  is a contained in the C 1  interval in m 2 . These are illustrated in  FIGS. 3 and 4 . 
 
 For a maximal pattern m, each column interval is of the form C j =[x 1 ,x 2 ] where x 2 −x 1 =δ. Alternatively, the column interval of a maximal pattern is of the form C j =[x−δ/2, x+δ/2]. Further  
       x   =         ∑     i   ∈     L   m         ⁢     A   ⁡     [     i   ,   j     ]                L   m                
 
 This is straightforward to verify and we omit the formal arguments here. 
 
 Following is a natural variation of the pattern on arrays which arises in many practical situations. An approximate pattern defined as follows: (approximate pattern) Given A, an r×c array of real numbers, δ&gt;0 and a positive integer k≦r, and additionally two reals, 0&lt;ε c , ε c ≦1, an approximate pattern m is a collection of columns of the form m={C j     1   =X 1 , C j     2   =X 2 , . . . C j     s   =X l } if 
 
         [0030]     1. for each i, A[i,j]≡X j  holds for no less than s(1−ε c ) j&#39;s.  
         [0031]     2. for each j, A[i,j]≡X j  holds for no less than k(1−ε r ) i&#39;s.  
         [0032]     Following is a simple example in  FIG. 5  to show that an approximate pattern is an interesting phenomenon in an array. Consider the following input array A with k=8 and δ=0.5. It is natural to expect a pattern as indicated by the arrows on the array. However the underlined values in the array show that they differ from the rest of the pattern. Allowing some error (say ε r =ε c =0.05) allows us to bring them in as a single pattern as one expects naturally.  
         [0000]     Algorithm:  
         [0033]     Given A, an (r×c) array of real numbers, δ j &gt;0, 1≦j≦c and a positive integer (quorum) k≦r. Further assume that ε r =0 and if m={C j     1   =X 1 , C j     2   =X 2 , . . . C j     s   =X l } and if i∉           m , then A[i,j J ]≢X j , 1≦J≦s, then the following algorithm is guaranteed to detect all such approximate patterns.  
         [0034]     Initialize:  
         [0035]     (1) For each j 
        C j   0 ←φ, C j   l ←{i 1 , i 2 ||A[i 1 ,j]−A[i 2 ,j]|≦δ j }
            (l is an indexing counter)    
            For each j the sets are: C j   0 , C j   1 , C j   2 , . . . , C j   1     j            
 
         [0039]     (2) For each j, Ans[j][0]←φ, Ans[j][1]←φ 
         [0040]     (3) For each C 1   − , 
        R←Ans[j][1]←C 1   −      Recurse(Ans, R, 1)        
 
         [0043]     Recurse(Ans, R, j)  
         [0044]     { 
         [0045]     (1) If (j≧c) then output Ans and exit  
         [0046]     (2) For each l  
         [0047]     (2.1) Ans′←Ans  
         [0048]     (2.2) C 0 ←C j+1   l ∩R, C 1 ←R\C j+1   l , C 2 ←C j+1   l \R  
         [0049]     (2.3) If (C 2 =φ) OR  
         [0050]     (2.1) for each  
         J   ≤   j     ,     (       (                  Ans   ′     ⁡     [   J   ]       ⁡     [   1   ]       ⋃     C   2                     (           Ans   ′     ⁡     [   j   ]       ⁡     [   0   ]       ≠   ϕ     )     ⋃     C   2              )     ≤     δ   J       )         
        Ans′[J][1]←Ans′[J][1]∪C 2 , R←R∪C 2          
 
         [0052]     (2.2) Ans′[j+1][0]←C 0 , Ans′[j+1][1]←(C 1 ∪C 2 )  
         [0053]     (2.3) Recurse(Ans′, R, j+1)  
         [0054]     (3) Recurse(Ans, R, j+1)  
         [0055]     } 
         [0056]     Following is a more detailed description of the algorithm described above. The input A is a two dimensional array of real values with r rows and c columns. Also included are the following input parameters  104 : value k that defines the quorum or the minimum number of rows in the fuzzy bi-cluster, a value δ that defines a parameter that determines when two real values can be deemed equal, and a value           that defines the fraction of the columns of the input array  102  that can deviate from the bi-cluster value. The input parameter values k and           can be different for each column in the bi-cluster.  
         [0057]     First, for each column in the input array A, the sets are formed that group the rows in that column using the δ value. This step is annotated as step (1) of the algorithm above. These sets are called C j1  where j denotes the column number and l is an index for the collection of sets for that column. For each column, these sets could be overlapping. For example for column 1, C j1  could be the set of rows  1 ,  2  and  3 , and C j2  could be the set of rows.  3 ,  4  and  5 , with row  3  common to both the sets. The initialization of the result in the matrix Ans is described in step (2) of the algorithm above. In step (3) of the algorithm above, the main method is called, starting with each set computed in step (1).  
         [0058]     The main method, Recurse( ), is recursive in nature and helps save the state of the computation in a systematic fashion, thereby adding to its efficiency. Ans is a two dimensional array that stores for each accumulating bi-cluster, the number of rows that satisfy the bi-cluster requirements in Ans[j][1] and number of rows including the ones that deviate from the requirement in Ans[j][0], where j is the column number. The resulting set of rows is accumulated in R of the Recurse( ) routine. For each set C of the next column (step (2) of the Recurse( ) routine), three sets are computed 1) C 0  which is the common rows of the set C and R, 2) C 1  which is the rows of R minus the rows of the new set, and 3) C 2  which is the rows of the new set minus the rows of R (step (2.2) of the Recurse( ) routine).  
         [0059]     If the C condition is satisfied, in step (2.1), for each of the preceding columns in R that is stored in the variable Ans[ ][1], then R is updated appropriately with the columns C 2 . The method continues to all the other sets of the current column, in step (2.3). In step (3), the method continues by ignoring the current column j. The method terminates when all the columns are processed (see step (1)).  
         [0060]     The present invention can be realized in hardware, software, or a combination of hardware and software. A system according to a preferred embodiment of the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods described herein—is suited. A typical combination of hardware and software could be a general-purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein.  
         [0061]     An embodiment of the present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods. Computer program means or computer program in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: a) conversion to another language, code or, notation; and b) reproduction in a different material form.  
         [0062]     A computer system may include, inter alia, one or more computers and at least a computer readable medium, allowing a computer system, to read data, instructions, messages or message packets, and other computer readable information from the computer readable medium. The computer readable medium may include non-volatile memory, such as ROM, Flash memory, Disk drive memory, CD-ROM, and other permanent storage. Additionally, a computer readable medium may include, for example, volatile storage such as RAM, buffers, cache memory, and network circuits. Furthermore, the computer readable medium may comprise computer readable information in a transitory state medium such as a network link and/or a network interface, including a wired network or a wireless network, that allow a computer system to read such computer readable information.  
         [0063]      FIG. 6  is a high level block diagram showing an information processing system useful for implementing one embodiment of the present invention. The computer system includes one or more processors, such as processor  604 . The processor  604  is connected to a communication infrastructure  602  (e.g., a communications bus, cross-over bar, or network). Various software embodiments are described in terms of this exemplary computer system. After reading this description, it will become apparent to a person of ordinary skill in the relevant art(s) how to implement the invention using other computer systems and/or computer architectures.  
         [0064]     The computer system can include a display interface  608  that forwards graphics, text, and other data from the communication infrastructure  602  (or from a frame buffer not shown) for display on the display unit  610 . The computer system also includes a main memory  606 , preferably random access memory (RAM), and may also include a secondary memory  612 . The secondary memory  612  may include, for example, a hard disk drive  614  and/or a removable storage drive  616 , representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive  616  reads from and/or writes to a removable storage unit  618  in a manner well known to those having ordinary skill in the art. Removable storage unit  618 , represents a floppy disk, a compact disc, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive  616 . As will be appreciated, the removable storage unit  618  includes a computer readable medium having stored therein computer software and/or data.  
         [0065]     In alternative embodiments, the secondary memory  612  may include other similar means for allowing computer programs or other instructions to be loaded into the computer system. Such means may include, for example, a removable storage unit  622  and an interface  620 . Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units  622  and interfaces  620  which allow software and data to be transferred from the removable storage unit  622  to the computer system.  
         [0066]     The computer system may also include a communications interface  624 . Communications interface  624  allows software and data to be transferred between the computer system and external devices. Examples of communications interface  624  may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, etc. Software and data transferred via communications interface  624  are in the form of signals which may be, for example, electronic, electromagnetic, optical, or other signals capable of being received by communications interface  624 . These signals are provided to communications interface  624  via a communications path (i.e., channel)  626 . This channel  626  carries signals and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link, and/or other communications channels.  
         [0067]     In this document, the terms “computer program medium,” “computer usable medium,” and “computer readable medium” are used to generally refer to media such as main memory  606  and secondary memory  612 , removable storage drive  616 , a hard disk installed in hard disk drive  614 , and signals. These computer program products are means for providing software to the computer system. The computer readable medium allows the computer system to read data, instructions, messages or message packets, and other computer readable information from the computer readable medium.  
         [0068]     Computer programs (also called computer control logic) are stored in main memory  606  and/or secondary memory  612 . Computer programs may also be received via communications interface  624 . Such computer programs, when executed, enable the computer system to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor  604  to perform the features of the computer system. Accordingly, such computer programs represent controllers of the computer system.  
         [0069]     What has been shown and discussed is a highly-simplified depiction of a programmable computer apparatus. Those skilled in the art will appreciate that other low-level components and connections are required in any practical application of a computer apparatus.  
         [0070]     Therefore, while there has been described what is presently considered to be the preferred embodiment, it will be understood by those skilled in the art that other modifications can be made within the spirit of the invention.