GENOME SEQUENCE ALIGNMENT APPARATUS AND METHOD

• US 20140309945A1
• Filed: 11/23/2012
• Published: 10/16/2014
• Est. Priority Date: 11/30/2011
• Status: Abandoned Application

• Current Assignee: Industry Academic Cooperation Foundation, Samsung SDS (China) Co., Ltd. (Samsung Group)
• Original Assignee: Industry Academic Cooperation Foundation, Samsung SDS (China) Co., Ltd. (Samsung Group)
• Inventors: Park, Min Seo, Park, Sang Hyun, Yeu, Yun Ku
• Application Number:
  US14/357,133
• Publication Number:
  US 20140309945A1
• Time in Patent Office: Days
• US Class Current: 702/20
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding

Abstract

Provided are a sequence alignment apparatus and method for searching a reference sequence for a candidate position matching with a fragment that is a portion of a read sequence, and mapping the reference sequence and the read sequence to each other based on the candidate position. Accordingly, it is possible to form an alignment permitting all variations and errors that may exist in a read sequence, to search the entire area of a read sequence for variations and errors, and to form an alignment with less computation without permitting backtracking, unlike existing sequence alignment technology.

Claims

1. A method for aligning a read sequence to a reference sequence, the method comprising:

searching a reference sequence for a candidate position matched with a fragment, the fragment being a portion of a read sequence; and

mapping the read sequence to the reference sequence on the candidate position;

wherein the searching and the mapping are implemented at least in part by a hardware processor.

2. The method of claim 1, wherein the fragment has a predetermined length and begins at an arbitrary position in the read sequence.

3. The method of claim 1, wherein:

the fragment has a predetermined length; and

the predetermined length of the fragment is determined based on a value of an average frequency with which the fragment appears in the reference sequence.

4. The method of claim 3, wherein the average frequency is determined according to:

a length of the reference sequence, a total number of different bases contained in the reference sequence.

5. The method of claim 1, wherein the searching of the reference sequence for the candidate position includes selecting, in the reference sequence, at least one of:

a position exactly matched with the fragment, and

a position matched with the fragment within a predetermined error tolerance E.

6. The method of claim 1, wherein:

the searching of the reference sequence for the candidate position includes at least one operation of;

searching the reference sequence for at least one position exactly matched with the fragment; and

performing a modification operation on the fragment within a predetermined error tolerance E, and then searching for at least one position matched with the reference sequence, and

the modification operation on the fragment is at least one of an insertion, a deletion, and a substitution operation.

7. The method of claim 6, wherein the mapping of the read sequence to the reference sequence includes mapping a remaining sequence, behind the fragment in the read sequence, to a sequence behind the candidate position in the reference sequence.

8. The method of claim 7, further comprising determining whether the remaining sequence matches with the reference sequence when the modification operation is performed on a portion of the remaining sequence within the error tolerance E.

9. The method of claim 8, wherein the error tolerance E is an error tolerance set for the reference sequence.

10. The method of claim 9, wherein, when a portion of the reference sequence behind the candidate position does not match with the remaining sequence behind the fragment in the read sequence, the mapping of the read sequence to the reference sequence is performed so as to include:

moving a starting position of the reference sequence, for matching, within the error tolerance E and

rematching the remaining sequence to the reference position at the moved starting position.

11. The method of claim 9, further comprising:

responding to a match between the fragment and the reference sequence by storing the fragment as a mapping fragment; and

when portions of the remaining sequence behind the fragment match, within the error tolerance E, with the reference sequence behind the candidate position, storing the matched portions as mapping fragments.

12. The method of claim 11, further comprising connecting the mapping fragments to each other when the mapping fragments satisfy the following equation:

|D_r(M₁,M₂)−

D_R(M₁,M₂)|<

E−

E₀

where;

M₁ and M₂ are mapping fragments to be connected,

D_r(M₁, M₂) is a distance between the mapping fragments M₁ and M₂ in a read sequence,

D_R(M₁, M₂) is a distance between the mapping fragments M₁ and M₂ in a reference sequence,

E is an error tolerance for the read sequence,

E₀ is a sum of error values included in the mapping fragments, and

|D_r(M₁, M₂)−

D_R(M₁, M₂)| is an absolute value of a difference between D_r(M₁, M₂) and D_R(M₁, M₂).

13. A computer program product comprising a non-transitory computer-readable medium and computer instructions configured to enable a hardware processor to implement:

a position selector configured to search a reference sequence for a candidate position matched with a fragment, the fragment being a portion of a read sequence;

a mapper configured to map the read sequence to the reference sequence on the candidate position; and

an aligner configured to align the read sequence with the candidate position when the reference sequence and the read sequence match with each other at the candidate position.

14. An apparatus intended for use in aligning a read sequence to a reference sequence, the apparatus comprising:

a position selector configured to search a reference sequence for a candidate position matched with a fragment, the fragment being a portion of a read sequence;

a mapper configured to map the read sequence to the reference sequence on the candidate position; and

an aligner configured to align the read sequence with the candidate position when the reference sequence and the read sequence match with each other at the candidate position

wherein at least one of the position selector, the mapper, and the aligner is implemented using a hardware processor.

15. The apparatus of claim 14, wherein the fragment of the read sequence is set by the position selector to have a predetermined length and to begin at an arbitrary position in the read sequence.

16. The apparatus of claim 14, wherein:

the predetermined length of the fragment is set based on a value of an average frequency with which the fragment appears in the reference sequence, and

the average frequency value is determined according to a length of the reference sequence and a total number of different bases contained in the reference sequence.

17. The apparatus of claim 14, wherein the position selector is further configured to select, in the reference sequence, at least one of:

a position exactly matching with the fragment, and

a position matching with the fragment within a predetermined error tolerance E.

18. The apparatus of claim 14, wherein the mapping unit is further configured to perform at least one of:

mapping a remaining sequence behind the fragment in the read sequence to a sequence behind the candidate position in the reference sequence, and

mapping remaining sequences in front of and behind the fragment in the read sequence to sequences in front of and behind the candidate position in the reference sequence.

19. The apparatus of claim 17, wherein the position selector is further configured to set the error tolerance E as an error tolerance for the reference sequence.

20. The apparatus of claim 19, wherein the mapping unit is configured to:

determine whether the reference sequence behind the candidate position and a remaining sequence behind the fragment in the read sequence match,

detect when a portion of the reference sequence behind the candidate position does not match with the remaining sequence behind the fragment in the read sequence, and

in response to the detection, move a starting position of the reference sequence for matching, within the error tolerance E, and rematch the remaining sequence to the reference position at the moved starting position.

21. The apparatus of claim 14, further comprising a storage, wherein:

when the mapping unit determines that the fragment matches with the reference sequence, the mapping unit stores the fragment in the storage as a mapping fragment, and

when portions of the remaining sequence behind the fragment match with the reference sequence behind the candidate position within the set error tolerance E, the mapping unit stores the matched portions in the storage as mapping fragments.

22. The apparatus of claim 21, wherein the alignment unit connects the mapping fragments to each other when the mapping fragments satisfy the following equation:

|D_r(M₁,M₂)−

D_R(M₁,M₂)|<

E−

E₀

where;

M₁ and M₂ are mapping fragments to be connected,

D_r(M₁, M₂) is a distance between the mapping fragments M₁ and M₂ in a read sequence,

D_R(M₁, M₂) is a distance between the mapping fragments M₁ and M₂ in a reference sequence,

E is an error tolerance permitted for the read sequence,

E₀ is a sum of error values included in the mapping fragments, and

|D_r(M₁, M₂)−

D_R(M₁, M₂)| is an absolute value of a difference between D_r(M₁, M₂) and D_R(M₁, M₂).