System and method for aligning genome sequence

Abstract

A system and a method for aligning a genome sequence are provided. The system for aligning a genome sequence includes a fragment sequence production unit configured to produce a plurality of fragment sequences from a read, a filtering unit configured to constitute a candidate fragment sequence group including only the fragment sequences mapped to a reference sequence among the plurality of produced fragment sequences, a mapping number calculation unit configured to divide the reference sequence into a plurality of sections and calculate total mapping numbers of the candidate fragment sequences for the sections, and an alignment unit configured to select the sections in which the calculated total mapping numbers are greater than or equal to a reference number and perform global alignment on the read with respect to the selected sections.

What is claimed is: 
     
         1 . A system, intended for use in aligning a genome sequence, the system comprising a computer executing program commands and thereby implementing:
 a fragment sequence production unit configured to produce a plurality of fragment sequences from a read;   a filtering unit configured to constitute, from among the produced plurality of fragment sequences, a candidate fragment sequence group including mapped fragment sequences, of the plurality of fragment sequences, that map to a reference sequence;   a mapping number calculation unit configured to:
 divide the reference sequence into a plurality of reference sequence sections; and 
 calculate total mapping numbers of the candidate fragment sequence group with respect to the reference sequence sections; and 
   an alignment unit configured to:
 select ones of the reference sequence sections in which the calculated total mapping numbers are at least a predetermined reference number; and 
 perform a global alignment operation on the read with respect to the selected ones of the reference sequence sections. 
   
     
     
         2 . The system of  claim 1 , wherein the fragment sequence production unit is further configured to produce the fragment sequences by reading a value of the read by a predetermined size, while advancing from a first base of the read sequence by a predetermined shift size. 
     
     
         3 . The system of  claim 1 , wherein the mapped fragment sequences each have a number of unmatched bases, from the results of exact matching with the reference sequence, not exceeding a predetermined number. 
     
     
         4 . The system of  claim 1 , further comprising a fragment sequence expansion unit configured to:
 calculate respective mapping repeat numbers of the mapped fragment sequences in the reference sequence;   selects the mapped fragment sequences having respective mapping repeat numbers exceeding the predetermined number to provide selected fragment sequences; and   expand respective fragment sizes of the selected fragment sequences until the respective mapping repeat numbers do not exceed the predetermined number.   
     
     
         5 . The system of  claim 4 , wherein the fragment sequence expansion unit is further configured to append bases, in the read, at positions corresponding to the beginnings or ends of the selected fragment sequences. 
     
     
         6 . The system of  claim 1 , wherein the alignment unit is further configured to:
 select ones of the candidate fragment sequence group mapped to the selected ones of the reference sequence sections to provide selected candidate fragment sequences; and   perform a global alignment operation on the read at mapping positions of the selected candidate fragment sequences in the reference sequence.   
     
     
         7 . The system of  claim 6 , wherein the alignment unit is further configured to:
 divide a selected section of the reference sequence sections into a plurality of subsections;   make a pre-performance determination as to whether a global alignment is pre-performed in the plurality of subsections to which positions in the reference sequence, on which the global alignment is to be performed, belong; and   perform the global alignment only when the pre-performance determination indicates that the global alignment is not pre-performed.   
     
     
         8 . The system of  claim 1 , wherein:
 the mapping number calculation unit is further configured to calculate respective total mapping lengths of the candidate fragment sequences for the respective reference sequence sections, together with the total mapping number; and   the alignment unit is further configured to:
 further select, from the ones of the reference sequence sections in which the calculated total mapping numbers are at least a predetermined reference number, one or more further selected reference sequence sections in which the calculated total mapping lengths are at least a predetermined mapping length; and 
 perform a global alignment operation on the read with respect to the further selected reference sequence sections. 
   
     
     
         9 . The system of  claim 8 , wherein, when the further selected reference sequence sections include a plurality of the reference sequence sections, the global alignment operation is sequentially performed on the read in an order based on one of the total mapping numbers and the total mapping lengths. 
     
     
         10 . The system of  claim 8 , wherein the predetermined mapping length is greater than or equal to 2. 
     
     
         11 . The system of  claim 8 , wherein the predetermined reference length is a relatively higher one of values calculated by the following expressions:
     H=L−f*e− 2 s , and       H=f+s      where:
 H represents the predetermined reference length, 
 L represents a length of a read, 
 f represents a length of a fragment sequence, 
 e represents a maximum error margin of the read, and 
 s represents a shift size of each fragment sequence. 
   
     
     
         12 . The system of  claim 11 , wherein the reference length satisfies the following expression:
     f+s≦H≦L −( f+s ).
   
     
     
         13 . The system of  claim 8 , wherein the reference length is in a range of 16 to 59. 
     
     
         14 . A method, intended for use in aligning a genome sequence, the method comprising:
 using a fragment sequence production unit to produce a plurality of fragment sequences from a read;   using a filtering unit to constitute, from among the produced plurality of fragment sequences, a candidate fragment sequence group including mapped fragment sequences, of the plurality of fragment sequences, that map to a reference sequence;   using a mapping number calculation unit to:
 divide the reference sequence into a plurality of reference sequence sections; and 
 calculate total mapping numbers of the candidate fragment sequence group with respect to the reference sequence sections; and 
   using an alignment unit to:
 select ones of the reference sequence sections in which the calculated total mapping numbers are at least a predetermined reference number; and 
 perform a global alignment operation on the read with respect to the selected ones of the reference sequence sections; 
   wherein the mapped fragment sequences each have a number of unmatched bases, from the results of exact matching with the reference sequence, not exceeding a predetermined number.   
     
     
         15 . The method of  claim 14 , wherein the producing of the fragment sequences is carried out by reading a value of the read by a predetermined size, while advancing from a first base of the read by a predetermined shift size. 
     
     
         16 . The method of  claim 14 , wherein the constituting of the candidate fragment sequence group further comprises using a fragment sequence expansion unit to:
 calculate respective mapping repeat numbers of the mapped fragment sequences in the reference sequence;   select the mapped fragment sequences having respective mapping repeat numbers exceeding the predetermined number to provide selected fragment sequences; and   expand respective fragment sizes of the selected fragment sequences until the respective mapping repeat numbers do not exceed the predetermined number;   wherein the expanding of the fragment sizes of the selected fragment sequences comprises appending bases, in the read, at positions corresponding to the beginnings or ends of the selected fragment sequences.   
     
     
         17 . The method of  claim 14 , wherein the performing of the global alignment comprises:
 selecting ones of the candidate fragment sequence group mapped to the selected ones of the reference sequence sections to provide selected candidate fragment sequences;   performing a global alignment operation on the read at mapping positions of the selected candidate fragment sequences in the reference sequence;   dividing each of the selected sections of the reference sequence sections into a plurality of subsections;   making a pre-performance determination as to whether a global alignment is pre-performed in the plurality of subsections to which positions in the reference sequence, on which the global alignment is to be performed, belong; and   performing the global alignment only when the pre-performance determination indicates that the global alignment is not pre-performed.   
     
     
         18 . The method of  claim 14 , wherein:
 the calculating of the total mapping numbers further comprises calculating respective total mapping lengths of the candidate fragment sequences for the respective reference sequence sections; and   the performing of the global alignment comprises:
 further selecting, from the ones of the reference sequence sections in which the calculated total mapping numbers are at least a predetermined reference number, one or more further selected reference sequence sections in which the calculated total mapping lengths are at least a predetermined mapping length; and 
 performing a global alignment operation on the read with respect to the further selected reference sequence sections. 
   
     
     
         19 . The method of  claim 18 , wherein, when the further selected reference sequence sections include a plurality of the reference sequence sections, the global alignment operation is sequentially performed on the read in an order based on one of the total mapping numbers and the total mapping lengths. 
     
     
         20 . The method of  claim 18 , wherein the reference length is in a range of 16 to 59.