Patent Publication Number: US-2005136457-A1

Title: Method for analyzing genome

Description:
BACKGROUND OF THE INVENTION  
      1) Field of the Invention  
      The present invention relates to a technology for analyzing a genome for a genetic site prediction or a genome structure analysis.  
      2) Description of the Related Art  
      Genetic information on a living organism is coded and stored in an arrangement of base sequences of a chromosome in a cell of the living organism. This arrangement of the base sequences is called “genome sequence”. It is noted, however, the genetic information is not included in the whole genome sequence, and the genome sequence includes a site that includes the genetic information and a site that does not include the genetic information. The former site are referred to as a “genetic site” that controls the genetic information.  
      At present, there are following three methods proposed for a genetic site prediction using a computer to predict which site in a genome sequence acts as a gene. 
      (1) A gene discovery method by comparison of the genome sequence with an open reading frame sequence    

      In this method, an arrangement of open reading frame sequences in an experimentally obtained site is compared with that of base sequences in a genome sequence. If the arrangements compared are similar to each other, it is predicted that a gene sequence, which corresponds to the open reading frame sequence, is present in the site. 
      (2) A gene discovery method by a statistical scheme    

      In this is a method, an arrangement of sequences in a known genetic site is modeled using, for example, a hidden Markov Model. A genetic site is predicted by determining whether an arrangement of base sequences corresponds to the model. 
      (3) A gene discovering method by comparison of genome sequences    

      In this is a method, it is determined that a genome site similar in the arrangement of sequences among closely related species is a genetic site, assuming that the genome site has been preserved in evolution.  
      Conventionally, the methods (1) and (2) are mainly used. However, the method (3) is increasingly expected to realize a higher accuracy in gene discovery.  
      Various software programs (for example, Harr plot and Dotter) that realize the method (3) are present. However, such computer programs is made in consideration of permitting non-matching of a certain ratio in comparison target sites matched in arrangement of the genome sequence. Due to this, a processing rate is relatively low and large quantities of calculator resources including a memory are used. A size of each possible comparison target genome is about 1 mega base pair (Mbp) (one million bases) at most, so that the conventional software programs are disadvantageously unsuitable for comparison of such genome sites of a size of over 100 Mbp. Furthermore, a calculation time is disadvantageously as long as 30 days or more if the Dotter is used for comparison of genome sites of a size of 5 Mbp.  
      Furthermore, the genome site includes a part in which sequences identical in arrangement pattern repeatedly appear. Such sequence is referred to as “repeat sequence”. The repeat sequence is used as a marker that indicates a position on the genome sequence or indicates signs of an evolution during a genome structure analysis. Thus, various analyses are performed using the repeat sequences.  
      Conventionally, a repeat sequence having a relatively short pattern (for example, in units of a few bases) is detected using software program for a repeat sequence detection (for example, Repeat Masker or repmask), and a repeat sequence having a relatively long pattern is detected using software program for a matrix display such as the Harr plot. However, if a size of comparison target genomes is large, it disadvantageously takes considerable time for the detection.  
     SUMMARY OF THE INVENTION  
      It is an object of the present invention to solve at least the above problems in the conventional technology.  
      A method for analyzing a genome according to one aspect of the present invention is realized in a computer system and includes inputting first genome-sequence information and second genome-sequence information including base sequences that indicates four bases of adenine, thymine, guanine, and cytosine arranged in the base sequences; creating a partial sequence that includes creating a first partial sequence by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in the first genome-sequence information such that the first partial sequence composed of (n+1) pieces of partial sequences; and creating a second partial sequence by successively deleting 0 th  to m th  pieces of the character information that indicates bases, where m is a positive integer, from a top of the base sequences in the second genome-sequence information such that the second partial sequences composed of (m+1) pieces of partial sequences; searching, in the first partial sequence, the partial sequence that prefix-matches completely or partially with pieces of character information, which indicates the bases of the respective partial sequence in the second partial sequence created at the creating the partial sequence, are arranged; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      A method for analyzing a genome according to another aspect of the present invention is realized in a computer system and includes inputting first partial sequence created by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in first genome-sequence information such that the first partial sequence is composed of (n+1) partial sequences, the first genome-sequence information including base sequences, in which pieces of character information that indicate four bases of adenine, thymine, guanine, and cytosine are arranged, and second partial sequence that is created by successively deleting 0 th  to m th  pieces of the character information that indicate bases, where m is a positive integer, from a top of the base sequences in second genome-sequence information such that the second partial sequence is composed of (m+1) pieces of partial sequences, the second genome-sequence information including base sequences, in which pieces of the character information that indicate the four bases of adenine, thymine, guanine, and cytosine are arranged; searching, in the first partial sequence, a partial sequence that prefix-matches completely or partially with pieces of character information that indicates bases of a partial sequence in the second partial sequence input; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      A computer program for analyzing a genome according to still another aspect of the present invention makes a computer execute inputting first genome-sequence information and second genome-sequence information including base sequences that indicates four bases of adenine, thymine, guanine, and cytosine arranged in the base sequences; creating a partial sequence that includes creating a first partial sequence by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in the first genome-sequence information such that the first partial sequence composed of (n+1) pieces of partial sequences; and creating a second partial sequence by successively deleting 0 th  to m th  pieces of the character information that indicates bases, where m is a positive integer, from a top of the base sequences in the second genome-sequence information such that the second partial sequences composed of (m+1) pieces of partial sequences; searching, in the first partial sequence, the partial sequence that prefix-matches completely or partially with pieces of character information, which indicates the bases of the respective partial sequence in the second partial sequence created at the creating the partial sequence, are arranged; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      A computer program for analyzing a genome according to still another aspect of the present invention makes a computer execute inputting first partial sequence created by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in first genome-sequence information such that the first partial sequence is composed of (n+1) partial sequences, the first genome-sequence information including base sequences, in which pieces of character information that indicate four bases of adenine, thymine, guanine, and cytosine are arranged, and second partial sequence that is created by successively deleting 0 th  to m th  pieces of the character information that indicate bases, where m is a positive integer, from a top of the base sequences in second genome-sequence information such that the second partial sequence is composed of (m+1) pieces of partial sequences, the second genome-sequence information including base sequences, in which pieces of the character information that indicate the four bases of adenine, thymine, guanine, and cytosine are arranged; searching, in the first partial sequence, a partial sequence that prefix-matches completely or partially with pieces of character information that indicates bases of a partial sequence in the second partial sequence input; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      An apparatus for analyzing a genome according to still another aspect of the present invention includes input unit that accepts input of first genome-sequence information and second genome-sequence information including base sequences that indicates four bases of adenine, thymine, guanine, and cytosine arranged in the base sequences; a creating unit that creates partial sequences that includes a first partial sequence by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in the first genome-sequence information such that the first partial sequence composed of (n+1) pieces of partial sequences; and a second partial sequence by successively deleting 0 th  to m th  pieces of the character information that indicates bases, where m is a positive integer, from a top of the base sequences in the second genome-sequence information such that the second partial sequences composed of (m+1) pieces of partial sequences; a searching unit that searches, in the first partial sequence, the partial sequence that prefix-matches completely or partially with pieces of character information, which indicates the bases of the respective partial sequence in the second partial sequence created at the creating the partial sequence, are arranged; and an extracting unit that extracts match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      An apparatus for analyzing a genome according to still another aspect of the present invention includes an input unit that accepts input of first partial sequence created by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in first genome-sequence information such that the first partial sequence is composed of (n+1) partial sequences, the first genome-sequence information including base sequences, in which pieces of character information that indicate four bases of adenine, thymine, guanine, and cytosine are arranged, and second partial sequence that is created by successively deleting 0 th  to m th  pieces of the character information that indicate bases, where m is a positive integer, from a top of the base sequences in second genome-sequence information such that the second partial sequence is composed of (m+1) pieces of partial sequences, the second genome-sequence information including base sequences, in which pieces of the character information that indicate the four bases of adenine, thymine, guanine, and cytosine are arranged; a searching unit that searches, in the first partial sequence, a partial sequence that prefix-matches completely or partially with pieces of character information that indicates bases of a partial sequence in the second partial sequence input; and an extracting unit that extracts match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      A computer-readable recording medium according to still another aspect of the present invention stores a computer program for analyzing a genome that makes a computer execute inputting first genome-sequence information and second genome-sequence information including base sequences that indicates four bases of adenine, thymine, guanine, and cytosine arranged in the base sequences; creating a partial sequence that includes creating a first partial sequence by successively deleting 0 th  to n th  pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in the first genome-sequence information such that the first partial sequence composed of (n+1) pieces of partial sequences; and creating a second partial sequence by successively deleting 0 th  to m th  pieces of the character information that indicates bases, where m is a positive integer, from a top of the base sequences in the second genome-sequence information such that the second partial sequences composed of (m+1) pieces of partial sequences; searching, in the first partial sequence, the partial sequence that prefix-matches completely or partially with pieces of character information, which indicates the bases of the respective partial sequence in the second partial sequence created at the creating the partial sequence, are arranged; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      A computer-readable recording medium according to still another aspect of the present invention stores a computer program for analyzing a genome that makes a computer execute inputting first partial sequence created by successively deleting 0 th  to n pieces of character information that indicates bases, where n is a positive integer, from a top of the base sequences in first genome-sequence information such that the first partial sequence is composed of (n+1) partial sequences, the first genome-sequence information including base sequences, in which pieces of character information that indicate four bases of adenine, thymine, guanine, and cytosine are arranged, and second partial sequence that is created by successively deleting 0 th  to m th  pieces of the character information that indicate bases, where m is a positive integer, from a top of the base sequences in second genome-sequence information such that the second partial sequence is composed of (m+1) pieces of partial sequences, the second genome-sequence information including base sequences, in which pieces of the character information that indicate the four bases of adenine, thymine, guanine, and cytosine are arranged; searching, in the first partial sequence, a partial sequence that prefix-matches completely or partially with pieces of character information that indicates bases of a partial sequence in the second partial sequence input; and extracting match information that includes information on the partial sequence in the first partial sequence searched at the searching, information on the partial sequence in the second partial sequence, and information on a number of the pieces of prefix-matched character information.  
      The other objects, features, and advantages of the present invention are specifically set forth in or will become apparent from the following detailed description of the invention when read in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       FIG. 1  is an explanatory view for an outline of a sequence comparison process in a genome analysis according to an embodiment of the present invention;  
       FIG. 2  is a block diagram of one example of a hardware configuration of a genome analyzing apparatus according to the embodiment;  
       FIG. 3  is a block diagram of one example of a functional configuration of the genome analyzing apparatus according to the embodiment;  
       FIG. 4  is a flowchart of procedures (for development to partial sequences) performed by the genome analyzing apparatus according to the embodiment;  
       FIG. 5  is an explanatory view for one example of contents of a first partial sequence;  
       FIG. 6  is an explanatory view for one example of contents of a second partial sequence;  
       FIG. 7  is a flowchart of another procedure (for creation of base sequences in a dictionary order) performed by the genome analyzing apparatus according to the embodiment;  
       FIG. 8  is an explanatory view for one example of contents of a rearranged partial sequence;  
       FIG. 9  is a flowchart of still another procedure (for a search and match information extraction) performed by the genome analyzing apparatus according to the embodiment;  
       FIG. 10  is an explanatory view for a binary search method;  
       FIG. 11  is an explanatory view for one example of contents of match information (a matched site sequence);  
       FIG. 12  is a flowchart of still another procedure (for deletion of duplications) performed by the genome analyzing apparatus according to the embodiment; and  
       FIG. 13  is an explanatory view for one example of contents of a matched sequence from which the duplications are deleted. 
    
    
     DETAILED DESCRIPTION  
      Exemplary embodiments of a method for analyzing a genome, a genome analyzing program, and a genome analyzing apparatus according to the present invention will be explained below in detail with reference to the accompanying drawings.  
      An outline of a sequence comparison process in a genome analysis according to an embodiment of the present invention will be explained first.  FIG. 1  is an explanatory view for the outline of the sequence comparison process in the genome analysis according to the embodiment. As shown in  FIG. 1 , the genome analysis according to the embodiment includes partial-sequence creation processes  101  and  102 , a search process  103 , and an extraction process  104 .  
      If two pieces of base sequences (a first base sequence  111  and a second base sequence  112 ) are compared, a first partial sequence (a partial sequence a1 to an+1)  113  is first created from the first base sequence  111  by the partial-sequence creation process  101 . A second partial sequence (partial sequences b1, b2, . . . and bm+1)  114  is then created from the second base sequence  112  by the partial-sequence creation process  102 . Each partial sequence is obtained by deleting an arbitrary number of characters from the top.  
      A character string search is performed on the first partial sequence  113  using each partial sequence  114  as a key by the search process  103 . The extraction process  104  is performed to extract a search result, and removes duplication in the search result to obtain matched sequence information  115 .  
      A hardware configuration of a genome analyzing apparatus according to the embodiment will be explained next.  FIG. 2  is a block diagram of one example of the hardware configuration of the genome analyzing apparatus according to the embodiment.  
      AS shown in  FIG. 2 , the genome analyzing apparatus includes a central processing unit (CPU)  201 , a read-only memory (ROM)  202 , a random access memory (RAM)  203 , a hard disk drive (HDD)  204 , a hard disk (HD)  205 , a flexible disk drive (FDD)  206 , a flexible disk (FD)  207  as an example of a detachable recording medium, a display  208 , an interface (I/F)  209 , a keyboard  211 , a mouse  212 , a scanner  213 , and a printer  214 . Each of components is connected to one another through a bus  200 .  
      The CPU  201  controls the entire genome analyzing apparatus. The ROM  202  stores programs such as a boot program. The RAM  203  is used as a work area for the CPU  201 . The HDD  204  controls read/write of data from/to the HD  205  under control of the CPU  201 . The HD  205  stores the data written by controlling the HDD  204 .  
      The FDD  206  controls read/write of data from/to the FD  207  under control of the CPU  201 . The FD  207  stores the data written by controlling the FDD  206  or allows the data stored in the FD  207  to be read by an information processor. Examples of the detachable recording medium may include a compact disc-read-only memory (CD-ROM) (or a compact disc-recordable (CD-R) or a compact disc-rewritable (CD-RW)), a magneto optic disc (MO), a digital versatile disk (DVD), and a memory card as well as the FD  207 . The display  208  displays data such as a document, an image, and function information as well as cursors, icons, and tool boxes. The display  208  is, for example, a CRT, a TFT liquid crystal display, or a plasma display.  
      The I/F  209  is connected to a network  215  such as a LAN or the Internet through a communication line  210 , and also connected to another server or the information processor through the network  215 . The I/F  209  interfaces the network  215  with an internal unit, and controls input/output of data from/to the other server or the information processor. The I/F  209  is, for example, a modem.  
      The keyboard  211  includes keys for inputting characters, numbers, various instructions, and the like, and inputs data. The keyboard  211  may be a touch panel input pad or a numeric key pad. The mouse  212  changes a position of a cursor, makes a range selection, moves a window, and changes a window size. As long as equivalent functions as that of the mouse  212  are included, other pointing device such as a track ball or a joystick may be used.  
      The scanner  213  optically reads image information such as a document, and captures information read into an image processor as image data. The scanner also includes an OCR function that enables the scanner  213  to read printed genome sequence information as data. The printer  214  prints data such as matched sequence information  115 . The printer  214  is, for example, a laser printer or an inkjet printer.  
      A functional configuration of the genome analyzing apparatus will be explained next.  FIG. 3  is a block diagram of one example of the functional configuration of the genome analyzing apparatus according to the embodiment. As shown in  FIG. 3 , the genome analyzing apparatus includes an input unit  301 , a first partial-sequence creating unit  302 , a first partial-sequence information storage unit  303  a rearranging unit  304 , a second partial-sequence creating unit  305 , a second partial-sequence information storage unit  306 , a search unit  307 , a match-information extracting unit  308 , and a match-information storage unit  309 .  
      The input unit  301  inputs first genome-sequence information including information on the first base sequence  111  and information on the second base sequence  112  each composed of a base sequence in which character information (A, T, G, and C) that indicate four bases of adenine (A), thymine (T), guanine (G), and a cytosine (C) are arranged.  
      Specifically, a function of the input unit  301  is realized by, for example, causing the I/F  209  to receive the first and the second genome-sequence information from the network  215 . In addition, the function of the input unit  301  may be realized by the FD  207  that is one example of the detachable recording medium, in which the first and the second genome-sequence information are stored, and the FDD  206 . Further, the function may be realized by the scanner  213  that includes the OCR function, the keyboard  211 , and the mouse  212 .  
      The first partial-sequence creating unit  302  controls the partial-sequence creation process  101  shown in  FIG. 1 . Namely, the first partial-sequence creating unit  302  successively deletes character information indicating 0 th  to n th  (where n is a positive integer) bases from the top of the first base sequence  111  that is the base sequence of the first genome-sequence information input by the input unit  301 . In addition, the first partial-sequence creating unit  302  creates a first partial sequence  113  that is a partial sequence including (n+1) pieces of partial sequences. While in the embodiment, the character information is successively deleted from the top, the character information may be successively deleted from the end conversely.  
      The first partial-sequence information storage unit  303  stores information on the first partial sequence  113  created by the first partial-sequence creating unit  302 . Alternatively, the first partial-sequence information storage unit  303  may store the information on the first partial sequence  113  that is created by another apparatus or the like in advance. A function of the first partial-sequence information storage unit  303  is realized by the ROM  202 , the RAM  203 , the HD  205  and the HDD  204 , or the FD  207  and the FD  206 .  
      The rearranging unit  304  rearranges the partial sequences in the information on the first partial sequence  113  created by the first partial-sequence creating unit  302  and stored in the first partial-sequence information storage unit  303  in a predetermined order. The predetermined order may be, for example, a dictionary order of pieces of character information that indicate bases of the respective partial sequences in the first partial sequences  113 , that is, an alphabetical order. In the rearrangement in the dictionary order (alphabetical order), if top bases are composed of a same character, a character that appears next in the partial sequence is compared. By repeating this comparison, orders of all partial sequences are determined. For example, if the partial sequences “aa”, “ac”, “aaa”, and “aaaa” are compared, the partial sequences are rearranged in an order of (1) “aa”, (2) “aaa”, (3) “aaaa”, and (4) ac.  
      The second partial-sequence creating unit  305  successively deletes character information indicating 0 th  to m th  (where m is a positive integer) bases from the top of the second base sequence  112  that is the base sequence of the second genome-sequence information input. In addition, the second partial-sequence creating unit  305  constructs second partial sequences  114  that are partial sequences composed of (m+1) pieces of partial sequences. While in the embodiment, the character data is successively deleted from the top, the character information may be successively deleted conversely from the end.  
      The second partial-sequence information storage unit  306  stores information on the second partial sequences  114  created by the second partial-sequence creating unit  305 . Alternatively, the second partial-sequence information storage unit  306  may store the information on the second partial sequences  114  constructed by another apparatus or the like in advance. A function of the second partial-sequence information storage unit  306  is realized by the ROM  202 , the RAM  203 , the HD  205  and the HDD  204 , or the FD  207  and the FD  206 .  
      The search unit  307  searches for partial sequences in the first partial sequences, which are created by the first partial-sequence creating unit  305  or stored in the first partial-sequence information storage unit  303 , and in which pieces of character information prefix-matched completely or partially to the pieces of character information indicating the bases of information on the respective second partial sequences created by the second partial-sequence creating unit  305  or stored in the second partial-sequence information storage unit  306  are arranged. The partial sequences in the first partial sequences stored in the first partial-sequence information storage unit  303  may be rearranged by the rearranging unit  304 .  
      The search unit  307  may search for partial sequences in the first partial sequences  113  in which pieces of character information prefix-matched completely or partially to the pieces of character information indicating the bases of the respective second partial sequences created by the partial-sequence creating unit are arranged, by a binary search method. The binary search method will be explained later.  
      The search unit  307  may search for a partial sequence having a largest number of pieces of the character information that prefix-matches completely or partially to the pieces of character information indicating the bases of the respective partial sequences  114  created by the partial-sequence creating unit among those in the first partial sequences  113  in which the pieces of character information prefix-matched completely or partially to the pieces of character information indicating the bases of the respective partial sequences  114  are arranged.  
      The match-information extracting unit  308  extracts match information (matched site sequences) that includes information on the partial sequences in the first partial sequence searched by the search unit  307 , information on the partial sequences  114 , and information on the number of pieces of the character information prefix-matched. Further, it is preferable that if there are duplicate pieces of the match information in the match information extracted, the match-information extracting unit  308  leaves any one of the duplicate pieces of the match information, and does not extract the other duplicate pieces of match information.  
      Functions of the first partial-sequence creating unit  302 , the rearranging unit  304 , the second partial-sequence creating unit  305 , the search unit  307 , and the match-information extracting unit  308  are realized by making the CPU  201  execute a program stored in the ROM  202 , the RAM  203 , the HD  205 , or the FD  207 .  
      Furthermore, the match-information storage unit  309  stores the match information extracted by the match-information extracting unit  308  in a state in which the information can be used. A function of the match-information storage unit  309  is realized by the ROM  202 , the RAM  203 , the HD  205  and the HDD  204 , or the FD  207  and the FDD  206 .  
      A process procedure performed by the genome analyzing apparatus will be explained next. The process includes (1) a process for developing a base sequence A to partial sequences, (2) a process for developing a base sequence B to partial sequences, (3) a process for creating base sequences in a dictionary-order, (4) a process for searching and extracting the match information, and (5) a process for deleting duplication. The processes (1) to (3) may be performed in advance as pre-processes.  
      It is assumed herein that base sequences to be a comparison target are the following two pieces of sequences. The following explanation applies even when the base sequences A and B are replaced. The base sequences to be the comparison target may be equal in length.  
                              Base sequence A:   aactctcgcacggtcacacg (20 bases)                   Base sequence B:   tccaactcgcacaactcacga (21 bases)          
 
      If it is detected that the two pieces of the base sequences of the comparison target are matched in an arrangement, it is assumed that they are matched in a direction of arrangement, that is, they are prefix-matched. To detect that the two pieces of the base sequences of the comparison target are matched in an opposite direction of the arrangement to the former direction, one of the base sequences may be arranged in an opposite direction. 
          (1) Development of base sequence A to partial sequences        

      One of the base sequences to be the comparison target (the base sequence A in the embodiment) is developed to partial sequences by deleting one base from the top of the base sequence A. Each of the partial sequences is denoted by Ai. The development of the base sequence A to the partial sequences is performed until the number of characters of a last partial sequence is the smallest number of matched bases (a smallest length of a part matched in arrangement of bases detected by comparing arrangements). For example, the smallest number of matched bases is four in this embodiment.  
       FIG. 4  is a flowchart of the process (for development to the partial sequences) performed by the genome analyzing apparatus according to the embodiment. As shown in the flowchart in  FIG. 4 , the base sequence A (aactctcgcacggtcacacg (20 bases)) serving as the first base sequence  111  is input (read) (step S 401 ). The base sequence A (aactctcgcacggtcacacg (20 bases)) is output (step S 402 ). This base sequence output is a partial sequence A1.  
      One base (a) positioned at the top of the partial sequence A1 output at the step S 402  is deleted (step S 403 ). Therefore, the partial sequence A1 is developed to a sequence (actctcgcacggtcacacg (19 bases)), which is a partial sequence A2. It is determined whether the number of bases of the base sequence is smaller than the smallest number of matched sequences (step S 404 ). If it is determined that the number of bases of the base sequence is larger than or equal to the smallest number of matched sequences (“NO” at step S 404 ), the process returns to the step S 402 , at which the partial sequence A2 (actctcgcacggtcacacg (19 bases)) is output. Furthermore, one base (a) positioned at the top of this partial sequence A2 is deleted (step S 403 ), thus, the partial sequence A2 is developed to a sequence (ctctcgcacggtcacacg (18 bases)), which is a partial sequence A3.  
      The steps S 402  to S 404  are repeatedly executed. If it is determined that the number of bases of the base sequence is smaller than the smallest number of matched bases at the step S 404  (“YES” at step S 404 ), the process is finished. Since the smallest number of matched bases is set at “4”, if the number of bases is “4” as a result of deletion at the step S 403 , the partial base sequence is output (at the step S 402 ), and if the number of bases is “3”, the processing is finished. In  FIG. 5 , 17 pieces of the partial sequences (the first partial sequences  113 ) A1 to A17 created through the above steps are shown. 
          (2) Development of base sequence B to partial sequences        

      With similar procedures, partial sequences are created from the base sequence B (tccaactcgcacaactcacga (21 bases)). In  FIG. 6 , 18 pieces of partial sequences B1 to B18 created similarly through the above steps are shown. 
          (3) Creation of base sequences in a dictionary-order        

      The partial sequences Ai are rearranged in the dictionary order. It is assumed herein that a set of the partial sequences thus arranged herein is a rearranged partial sequence set {Ai}.  FIG. 7  is a flowchart of the other process (for constructing the dictionary-order base sequence set). As shown in the flowchart of  FIG. 7 , the respective partial sequences Ai in the first partial sequence  113  are input (read) (step S 701 ).  
      The partial sequences Ai input are rearranged in the dictionary order (alphabetical order), in other words, the partial sequences Ai are sorted (step S 702 ). The rearrangement is made in the dictionary order (alphabetical order). Namely, the partial sequences Ai are rearranged in an order of (1) A (adenine), (2) T (thymine), (3) G (guanine), and (4) C (cytosine). Bases positioned at the top in the partial sequences are compared so as to rearrange the partial sequences in the predetermined order, irrespective of lengths of the base sequences. If the bases at the top in the partial sequences are same, bases that appear next are compared to rearrange the partial sequences in the predetermined order. By repeating this comparison, all partial sequences are arranged in the predetermined order.  
      Thereafter, the rearranged partial sequences {Ai} are output (step S 703 ), and the process is finished. In  FIG. 8 , the rearranged partial sequences {Ai} are shown. 
          (4) Search and extraction of match information        

      The binary search method is applied to the partial sequences {Ai} in the dictionary order to search the partial sequence Ai that includes bases that prefix-matches to the partial sequences Bi (where i=1 to 17) for equal to or more than the smallest number (four bases in the following case) of matched bases.  FIG. 9  is a flowchart of the other process (for searching and extracting the match information) performed by the genome analyzing apparatus according to the embodiment.  
      As shown in the flowchart in  FIG. 9 , the first partial sequence, which is the rearranged partial sequence {A1} is input (step S 901 ). Then, a query, which is a second partial sequence By is input (step S 902 ). An example of inputting “B4 (aactcgcacaactcacga)” as the query will be explained herein. A partial sequence Ai (1) that is middle in the order in the rearranged partial sequences {A1} is extracted (step S 903 ). As shown in  FIG. 10 , the middle partial sequence is a ninth partial sequence in the order “A11 (cggtcacacg)” since, for example, the total number (17) of the rearranged partial sequences {A1}÷2=8.5.  
      The query By is compared with the partial sequence Ai (1), and the number of prefix-matched bases is calculated (step S 904 ). A number of bases obtained at a present comparison is compared with a number of bases obtained at a previous comparison. If the number of bases obtained at the present comparison is equal to or larger than the number of bases obtained at the previous comparison (“NO” at step S 905 ), the number of bases of the present comparison is stored in a predetermined storage region (step S 906 ). If the number of bases of the previous comparison is larger than the number of bases of the present comparison (“YES” at step S 905 ), the process goes to a step S 911  without executing anything. Namely, at the step S 911 , the number of bases of the previous comparison is set as the match information.  
      When the query B4 (aactcgcacaactcacga) is compared with the partial sequence A11 (cggtcacacg), the number of bases prefix-matched is “0”. Since information on the number of bases obtained at the previous comparison is not present in the comparison of the query B4 with the partial sequence A11, this number of bases “0” is stored.  
      The query By is compared in order with the partial sequence Ai (1) (step S 907 ). If they are completely matched to each other (By =Ai (1) at step S 907 ), this indicates that the partial sequence to be searched is discovered. Therefore, nothing is performed thereafter, and the process goes to the step S 911 .  
      If the comparison of the query By with the partial sequence Ai (1) in order indicates that the query By is higher in order than the partial sequence A (1) (By &lt;Ai (1) at step S 907 ), the partial sequence to be searched can be judged to be located in direction toward the top. Therefore, a partial sequence located in the direction toward the top relative to the partial sequence Ai (1) is extracted (step S 908 ).  
      If the comparison of the query By with the partial sequence Ai (1) in order indicates that the query By is lower in order than the partial sequence A (1) (By&gt;Ai (1) at the step S 907 ), the partial sequence to be searched can be judged to be located in a direction toward the end. Therefore, a partial sequence located in the direction toward the end relative to the partial sequence Ai (1) is extracted (at a step S 909 ).  
      It is determined whether the partial sequence is present in either the direction toward the top or the end (at a step S 910 ). If the partial sequence is present (“YES” at step S 910 ), the processing returns to the step S 903 . If no partial sequence is present (“NO” at step S 910 ), this indicates that no further matched sequence is present and the process proceeds to the step S 911 .  
      If the query B4 (aactcgcacaactcacga) is compared in order with the partial sequence A11 (cggtcacacg), bases located at the top the query B4 and the partial sequence A1 are “a” and “c”, respectively. In addition, the query B4 is higher in order than the partial sequence A11, the process goes to the step S 908 , at which eight pieces of partial sequences (A1, A16, A10, A2, A15, A17, A9, and A7) located in the direction toward the top are extracted. The process then returns to the step S 903 .  
      At the step S 903 , the partial sequence middle in the order among the eight pieces of the partial sequences is extracted. Specifically, since the total number (8)+2=4, “the partial sequence A2 (actctcgcacggtcacacg)” that is the fourth from the top is extracted. If the query B4 (aactcgcacaactcacga) is then compared with the partial sequence A2 (actctcgcacggtcacacg), the number of prefix-matched bases “a” is “1”. Since the information on the number of bases of the previous comparison of the query B4 with the partial sequence A11 is “0”, the number of bases “1” is stored.  
      If the query B4 (aactcgcacaactcacga) is compared in order with the partial sequence A2 (actctcgcacggtcacacg), bases located at the top of the query B4 and the partial sequence A2 are both “a” and second bases are “a” and “c”, respectively. In addition, the query B4 is higher in order than the partial sequence A2. Therefore, the process goes to the step S 908  at which three pieces of the partial sequences (A1, A16, and A10) in the direction toward the top are extracted. The process then returns to the step S 903 .  
      At the step S 903 , the partial sequence middle in the order among the three pieces of the partial sequences is extracted. Specifically, since the total number (3)÷2=1.5, the “partial sequence A16 (acacg)” that is the second from the top is extracted. If the query B4 (aactcgcacaactcacga) is then compared with the partial sequence A16 (acacg), the number of bases prefix-matched “a” is “1”. Since the information on the number of bases of the previous comparison of the query B4 with the partial sequence A11 is “1”, the number of bases “1” is stored.  
      If the query B4 (aactcgcacaactcacga) is compared in order with the partial sequence A16 (acacg), bases located at the top of the query B4 and the partial sequence A16 are both “a” and second bases are “a” and “c” respectively. In addition, the query B4 is higher in order than the partial sequence A16. Therefore, the process goes to the step S 908  at which one partial sequence (A1) in the direction toward the top is extracted. The process then returns to the step S 903 .  
      At the step S 903 , the partial sequence middle in the order among the one piece of partial sequence is extracted. Since only one piece of the partial sequence is present, the “partial sequence A1 (aactctcgcacggtcacacg)” is extracted. If the query B4 (aactcgcacaactcacga) is then compared with the partial sequence A1 (aactctcgcacggtcacacg), the number of prefix-matched bases “a” is “9”. Since the information on the number of bases of the previous comparison of the query B4 with the partial sequence A1 is “1”, the number of bases “9” is stored.  
      If the query B4 (aactcgcacaactcacga) is compared in order with the partial sequence A1 (aactctcgcacggtcacacg), ninth bases from the top are same and tenth bases of the query B4 and the partial sequence A1 are “g” and “c” respectively. In addition, the query B4 is higher in order than the partial sequence A16. Therefore, the process goes to the step S 908  at which one piece of partial sequence (A1) in the direction toward the top is extracted. However, since no partial sequence is left (“NO” at step S 910 ), the comparison is not repeated any longer and the process goes to a step S 911 .  
      At the step S 911 , the largest value among those stored at the step S 906  is set at “z” and an index of the partial sequence Ai at the value z is set at “x”, an index of the query By at the value z is set at “y”, and a set of three numbers [x y z] is output (step S 911 ). If a plurality of largest values is present, sets of three numbers [x y z] are respectively output. As for a query B4, the number of bases is “9” and the partial sequence is A1. Therefore, a set of three numbers is [1 4 9]. This means that the arrangement of nine bases from the top in the base sequence A is matched to that of nine bases from the fourth base in the base sequence B.  
      It is then determined whether the search is conducted to all the queries (step S 912 ). If the search is not conducted to all the queries (“NO” at step S 912 ), remaining other queries are input (step S 913 ) and the process returns to the step S 903 . If the search is conducted to all the queries (“YES” at step S 912 ), the process is finished. If the process is simply repeated from B1 to B17, data shown in  FIG. 11  is obtained. This data is match information (matched site sequences {Ci}). 
          (5) Deletion of duplication        

      Among the match site sequences {Ci}, C2 means that the arrangement of eight bases from the second in the base sequence A is matched to that of eight sequences from the fifth in the base sequence B. C1 means that the arrangement of nine bases from the first in the base sequence A is matched to that of nine bases from the fourth in the base sequence B. Accordingly, the matched sequence C2 is included in the matched sequence C1. To delete such duplication, a following process is performed. It is noted that this process can be performed while performing the search and extraction of the match information.  
      Ci [ai bi ni] is compared with Ck [ak bk nk]. If they satisfy a relationship of the following equation (1), it is defined that the matched sequence Ci includes the matched sequence Ck and the sequence Ck is deleted. It is noted, however, that the sequences Ci and Ck that satisfy i&lt;k are selected. 
 
 ak−ai=bk−bi=ni−nk   (1) 
 
       FIG. 12  is a flowchart of the other process (for deleting duplication) performed by the genome analyzing apparatus according to the embodiment. As shown in the flowchart in  FIG. 12 , the matched site sequences Ci and Ck are input (read) (step S 1201 ). 1 is substituted to the sequence Ci and 2 is substituted to the sequence Ck, whereby specifying the comparison target sequences C1 and C2 (step S 1202 ).  
      It is determined whether the sequence Ci is present, in other words, whether the Ci is deleted at a previous step S 1205  (step S 1203 ). If the Ci is deleted and not present (“NO” at step S 1203 ), nothing is performed and the process proceeds to a step S 1206 . If the Ci is not deleted and is present (“YES” at step S 1203 ), the process goes to a step S 1204 . As for the C1 and C2 initially specified, since the C1 is not deleted (the C1 is not to be deleted), the process goes to the step S 1204 .  
      At the step S 1204 , it is determined whether the Ci and Ck satisfy the equation (1). If they do not satisfy the equation (1) (“NO” at step S 1204 ), nothing is performed and the process proceeds to a step S 1206 . If they satisfy the equation (1) (“YES” at step S 1204 ), the Ck is deleted from the matched site sequences (at step S 1205 ). If the sequences C1 [1 4 9] and C2 [2 5 8] are applied to the equation (1), then ak−ai=1, bk−bi=1, and ni−nk=1, and a relationship of ak−ai=bk−bi=ni−nk is established. Accordingly, the C2 is deleted from the matched site sequences.  
      After 1 is subtracted from i (step S 1206 ), it is determined whether the resultant i is smaller than 1 (step S 1207 ). If the i is not smaller than 1 (“NO” at step S 1207 ), the process returns to the step S 1203  and the steps S 1203  to S 1207  are repeated. If it is determined at the step S 1207  that the i is smaller than 1, which means the i is 0 (“YES” at step S 1207 ), a value k is substituted to the i and 1 is added to the k (step S 1208 ).  
      It is determined whether the value k to which 1 is added at the step S 1208  exceeds an upper limit, in other words, whether the total number of matched site sequences input at the step S 1201  (step S 1209 ). If the k does not exceed the upper limit (“NO” at step S 1209 ), the process returns to the step S 1203  and the steps S 1203  to S 1209  are repeated. If it is determined at the step S 1209  that the k exceeds the upper limit (“YES” at step S 1209 ), the matched site sequences that have not been deleted but remained are output (at step S 1210 ) and the process is finished.  
      As for the C1, since 1 is subtracted from i, a result is 0. Therefore, at the step S 1208 , the C1 is replaced by C2 and the C2 is replaced by C3. Since the C3 does not exceed the upper limit, the process returns to the step S 1203 . However, since the C2 is already deleted and not present, the C2 is further changed to the C1 and the process returns again to the step S 1203 . Since the C1 is present this time, it is determined whether C1 [1 4 9] and C3 [3 6 7] satisfy the relationship of the equation (1). If the C1 [1 4 9] and the C3 [3 6 7] are applied to the equation (1), ak−ai=2, bk−bi=2, and ni−nk=2 and a relationship of ak−ai=bk−bi=ni−nk is established. Accordingly, the C3 is also deleted from the matched site sequences.  
      The same process is then repeated. It is determined whether C1 and C4, C1 and C5, C1 and C6, C1 and C7, C7 and C8, C1 and C8, C8 and C9, C8 and C10, C7 and C10, C1 and C10, C10 and C11, C8 and C11, C7 and C11, C1 and C11, C11 and C12, C10 and C12, C8 and C12, C7 and C12, and C1 and C12 satisfy the relationship of the equation (1) respectively in this order. As a result of the determination, the C1 and C4, the C1 and C5, the C1 and C6, and the C8 and C9 satisfy the equation (1). Accordingly, the C4, C5, C6 and C9 are deleted from the matched site sequences. Details of the determination are as follows.  
      [1] Compare the C1 with the C2. If i=1 and k=2, the C1 and C2 satisfy the equation (1) and the C1 includes the C2. The C2 is, therefore, deleted.  
      [2] Compare the C1 with the C3. If i=1 and k=3, the C1 and C3 satisfy the equation (1) and the C1 includes the C3. The C3 is, therefore, deleted.  
      [3] Compare the C1 with the C4. If i=1 and k=4, the C1 and C4 satisfy the equation (1) and the C1 includes the C4. The C4 is, therefore, deleted.  
      [4] Compare the C1 with the C5. If i=1 and k=5, the C1 and C5 satisfy the equation (1) and the C1 includes the C5. The C5 is, therefore, deleted.  
      [5] Compare the C1 with the C6. If i=1 and k=6, the C1 and C6 satisfy the equation (1) and the C1 includes the C6. The C6 is, therefore, deleted.  
      [6] Compare the C1 with the C7. If i=1 and k=7, the C1 and C7 do not satisfy the equation (1). The C7 is, therefore, not deleted.  
      [7] Compare the C7 with the C8. If i=7 and k=8, the C7 and C8 do not satisfy the equation (1). The C8 is, therefore, not deleted.  
      [8] Compare the C1 with the C8. If i=1 and k=8, the C7 and C8 do not satisfy the equation (1). The C8 is, therefore, not deleted.  
      [9] Compare the C8 with the C9. If i=8 and k=9, the C1 and C8 satisfy the equation (1) and the C8 includes the C9. The C9 is, therefore, deleted.  
      [10] Compare the C8 with the C10. If i=8 and k=10, the C8 and C10 do not satisfy the equation (1). The C10 is, therefore, not deleted.  
      [11] Compare the C7 with the C10. If i=7 and k=10, the C7 and C10 do not satisfy the equation (1). The C10 is, therefore, not deleted.  
      [12] Compare the C1 with the C10. If i=1 and k=10, the C1 and C10 do not satisfy the equation (1). The C10 is, therefore, not deleted.  
      [13] Compare the C10 with the C11. If i=10 and k=11, the C10 and C11 do not satisfy the equation (1). The C11 is, therefore, not deleted.  
      [14] Compare the C8 with the C11. If i=8 and k=11, the C8 and C11 do not satisfy the equation (1). The C11 is, therefore, not deleted.  
      [15] Compare the C7 with the C11. If i=7 and k=11, the C7 and C11 do not satisfy the equation (1). The C1 is, therefore, not deleted.  
      [16] Compare the C1 with the C11. If i=1 and k=11, the C1 and C1 do not satisfy the equation (1). The C11 is, therefore, not deleted.  
      [17] Compare the C1 with the C12. If i=11 and k=12, the C11 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      [18] Compare the C10 with the C12. If i=10 and k=12, the C10 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      [19] Compare the C9 with the C12. If i=9 and k=12, the C9 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      [20] Compare the C8 with the C12. If i=8 and k=12, the C8 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      [21] Compare the C7 with the C12. If i=7 and k=12, the C7 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      [22] Compare the C1 with the C12. If i=1 and k=12, the C1 and C12 do not satisfy the equation (1). The C12 is, therefore, not deleted.  
      As a consequence, the match information (matched site sequence) from which duplication is deleted is shown in  FIG. 13 . The match information thus obtained is stored in the match-information storage unit  309  to be used in the genetic site prediction or the genome structure analysis.  
      As explained above, according to the embodiment, a comparison over a whole genome size of 100 Mbp (several hundred million bases) can be performed, and the match information on the genome sequences to be the comparison target for the genetic site prediction or the genome structure analysis can be efficiently acquired. Specifically, to perform a 5-Mbp comparison, it takes about one month if the Dotter is used. The genome analyzing apparatus according to the embodiment, by contrast, can perform calculation within about one hour.  
      Moreover, the method for analyzing a genome according to the embodiment may be a computer-readable program prepared in advance, and may be realized by making a computer, such as a personal computer or a workstation, execute the program. This program is recorded in a computer-readable recording medium, such as an HD, an FD, a CD-ROM, an MO, or a DVD, and executed by being read from the recording medium by the computer. This program may be a transmission medium that can be distributed through a network such as the Internet.  
      As explained above, according to the present invention, the match information of the genome sequences that are the comparison target for the genetic site prediction or the genome structure analysis can be efficiently acquired, and displayed so as to facilitate recognition of the information. Thus, it is possible to obtain the method for analyzing a genome, the genome analyzing program, the genome analyzing apparatus, and the genome analyzing terminal capable of performing the genetic site prediction or the genome structure analysis swiftly and efficiently.  
      Although the invention has been described with respect to a specific embodiment for a complete and clear disclosure, the appended claims are not to be thus limited but are to be construed as embodying all modifications and alternative constructions that may occur to one skilled in the art which fairly fall within the basic teaching herein set forth.