METHOD AND APPARATUS FOR REARRANGEMENT OF SEQUENCE IN NEXT GENERATION SEQUENCING

摘要

PURPOSE: A method and an apparatus for rearrangement of a sequence of NGS(next generation sequencing) are provided to recombine short sequence fragments and to improve rearrangement speed. CONSTITUTION: A method for rearrangement of a sequence of NGS comprises: a step of dividing a sequence fragment(510) with n sequence length into 6 parts; a step of generating a hash value of a reference sequence by each sub-string unit of n/6 and preparing a has table; a step of using each 3 pieces placed at front portion as a seed among 6-divided pieces of the sequence fragment(520); a step of calculating a hash value of 3 seeds; and a step of searching a hash value corresponding to the hash value of three seeds from the hash table and searching a mapping candidate location. An apparatus for rearrangement of a sequence of the NGS comprises: a division part which divides the sequence fragment into 6; a seed generation unit in which 3 pieces placed at front portion as the seed; a hash value generator which calculates the hash value of 3 seeds; a hash table generator which generates the hash value and forms the hash table; and a searching unit for searching the hash table corresponding to the hash value of 3 seeds from the hash table and searching the mapping candidate location. [Reference numerals] (AA) Sequence length: n; (BB) Length: n/6; (CC) Divide into 6 parts; (DD,GG) Seed 1; (EE,HH) Seed 2; (FF,II) Seed 3; (JJ,LL) Seed rank; (KK) Search in a hash table; (MM) Hash value; (NN) Starting position