SẮP HÀNG HOÀN CHỈNH HAI HỆ GENOME

Mục lục
Hà Tuấn Cường 1
HÀ NỘI - 20< hai số cuối của năm bảo vệ KLTN> 1
Hà Tuấn Cường 2
HÀ NỘI - 20< hai số cuối của năm bảo vệ KLTN> 2
Lời cảm ơn 1
Tóm tắt 2
Mục lục 3
Danh sách hình vẽ 4
Danh sách các bảng 6
Lời mở đầu 7
Chương 1. Giới thiệu 8
1.1.1. Hệ thống ký tự 9
1.1.2. Các phép biến đổi 9
1.1.3. Khoảng cách 10
Chương 2. Bài toán sắp hàng hoàn chỉnh hai hệ gen 15
2.1. Tổng quan 15
2.2 Pairwise Alignment with Rearrangement 16
2.2.1. Cơ sở lý thuyết 16
2.2.3. Độ phức tạp của thuật toán 20
2.3. Bắt cặp với những trình tự lớn 20
Chương 3. Full Genome Alignment 22
3.1. Xây dựng hệ thống 22
22
3.2. Giới thiệu về BLASTZ 24
Page | 3
3.2.1. Tính năng của BLASTZ 24
3.2.2. Chương trình BLASTZ 25
3.3. Optimal Alignment with Linear space 26
Chương 4. Kết quả 29
4.1. Chương trình 29
4.2. Kiểm thử 31
4.2.1. Dữ liệu mô phỏng 31
4.2.2. Dữ liệu thật 34
Chương 5. Kết luận 36
Tài liệu tham khảo 37
Danh sách hình vẽ
Page | 4
Hình 1. Ví dụ về một trình tự. Hình trên cùng: 1 đoạn 18S rDNA của sâu bọ khác
cánh. Hình giữa trên: Tổng quát cơ thể động vật chân dốt. Hình giữa dưới:
Orthopteran stridulation. Hình dưới cùng: Đoạn gen mtDNA [13] 8
Hình 2: Các biến đổi ở mức độ gen giữa Người và Khỉ 13
Hình 3:Hình trái: ví dụ 2 phép biến đổi S1(k1, t1) và S2(k2, t2) là độc lập với
nhau. Hình phải:Đổi chỗ đồng thời 2 phép biến đổi độc lập 19
Hình 4: Single Swap (trái) và Couple Swap (phải) 21
Hình 5:Sắp hàng trình tự với Ukkonen Barrier [13] 28
Hình 6: Giao diên chương trình 30
Hình 7: Kết quả chương trình 31
Page | 5
Danh sách các bảng
Bảng 1: Ma trận trọng số của BLASTZ 25
Bảng 2: Kết quả Test với số Inversion – Move là 0 32
Bảng 3: Kết quả Test với số Inversion – Move là 1 33
Bảng 4: Kết quả Test với số Inversion – Move là 2 33
Bảng 5: Kết quả Test với số Inversion – Move là 3 33
Bảng 6: Kết quả chạy dữ liệu thật 35
Page | 6
Lời mở đầu
Năm 1854, Charles Darwin cho xuất bản quyển sách “Nguồn gốc của các
loài sinh vật”, một công trình nghiên cứu sinh học nổi tiếng và đặt nền tảng cho
thuyết tiến hóa của ông. Trong đó có viết “tất cả các động vật tương tự nhau phải
tiến hóa từ một tổ tiên chung và tất cả các sinh vật phải tiến hóa từ một vài hoặc
một tổ tiên chung đã sống cách đây nhiều triệu năm.” [7]
Bộ gen của sinh vật là một trình tự ADN, theo thuyết tiến hóa thì chúng
cùng được biến đổi và phát triển từ một tổ tiên chung. Trải qua hàng triệu năm tiến
hóa và phát triển, một số đoạn gen được mất đi cũng như bị di chuyển vị trí so với
ban đầu, hình thành lên những hệ gen khác nhau đại diện cho hàng tỷ sinh vật trên
trái đất. Một trong những nhiệm vụ cần thiết là phải tìm ra mối quan hệ về mặt cấu
trúc giữa các hệ gen sinh vật, qua đó xây dựng lên một bức tranh toàn cảnh về sự
tương tự và tiến hóa giữa các sinh vật trên hành tinh.
Với sự phát triển của công nghệ giải mã trình tự, ngày càng nhiều các hệ
gen đã được giải mã hoàn chỉnh và được lưu trữ trong các ngân hàng cơ sở dữ liệu
gen. Việc so sánh và tìm ra sự tương đồng giữa các hệ gen một cách thủ công là
không thể thực hiện được. Do đó dẫn đến một nhu cầu cấp thiết phải nghiên cứu
phương pháp và xây dựng chương trình để so sánh và bắt cặp trình tự cho hai hệ
gen.
Mặc dù một số phương pháp đã được nghiên cứu và phát triển, chúng mới
chỉ tập trung vào xác định và bắt cặp cho những vùng ADN có độ tương đồng cao
giữa hai hệ gen. Tức là, một phần lớn trong hệ gen có thể không được bắt cặp và
so sánh khi ta tiến hành với các loài sinh vật có hệ gen khác nhau nhiều. Vì vậy
cần phải xây dưng một hệ thống có khả năng bắt cặp được toàn bộ các ADN trên
hai hệ gen.
Page | 7
Chương 1. Giới thiệu
Chương này giới thiệu về những kiến thức cơ bản về tin sinh học, bài toán
bắt cặp trình tự và bắt cặp trình tự theo hệ gen. Nội dung giới thiệu được dựa một
phần trên bài giảng của Viện Đại học Ohio State, Hoa Kỳ [13]
1.1. Trình tự
Một hệ gen của một sinh vật được thể hiện là một trình tự của các ADN.
Trình tự là một dãy tuyến tính các phần tử được sặp xếp theo thứ tự. Như
vậy một trình tự chứa hai loại thông tin: thông tin về phần tử và thông tin định vị -
thông tin về vị trí tương đối của từng phần tử so với các phần tử khác.
Các thông tin định vị có thể được xác định theo nhiều cách như theo trục,
theo thời gian, vị trí của nhiễm sắc thể hoặc trong 1 vòng protein.
Hình 1. Ví dụ về một trình tự. Hình trên cùng: 1 đoạn 18S rDNA của sâu bọ khác
cánh. Hình giữa trên: Tổng quát cơ thể động vật chân dốt. Hình giữa dưới:
Orthopteran stridulation. Hình dưới cùng: Đoạn gen mtDNA [13]
Page | 8
Các loài sinh vật được tiến hóa từ một tổ tiên chung, biến đổi qua các dạng
hình thái trong quá trình tiến hóa và phát triển. Khi đề cập đến trình tự, có ba vấn
đề chúng ta cần phải nói đến là hệ thống các ký tự trong trình tự, các phép biến đổi
trình tự và hàm khoảng cách đánh giá sự thay đổi của trình tự.
1.1.1. Hệ thống ký tự
Tập hợp các phần tử có thể xuất hiện trong trình tự được gọi là một hệ
thống các ký tự ( ∑ ) , trong ADN, người ta sử dụng một thệ thống kí tự ∑ = {A,
C, G, T, λ ) trong đó A, C, G, T đại diện cho 4 nucleotides : adenine (A),
cytosine (C), guanine (G) và thymine (T). λ là ký tự đặc biệt đại diện cho 1
khoảng trống là 1 vị trí mà không có nucleotide thực tế. Trong hầu hết các trường
hợp, ký tự gap (‘-‘) có thể được sử dụng để thay thế cho λ. Bất kỳ một trình tự nào
cũng là một sự thể hiện bởi các phần tử có thể xuất hiện trong trình tự và được
định nghĩa trong ∑.
1.1.2. Các phép biến đổi
Trong quá trình tiến hóa, có 4 phương thức chính để biến đổi một trình tự là
phép thay thế, phép chèn – xóa, đảo ngược và dịch chuyển. Biến đổi phức tạp xảy
ra là sự kết hợp của 2 phép đảo ngược và dịch chuyển, sự kết hợp này gây ra sự
khó khăn trong việc dựng lại mối quan hệ giữa các trình tự trong những hệ thống
phân tích phức tạp.
Phép thay thế:
Phép chèn – xóa:
Phép đảo ngược:
Phép dịch chuyển:
Page | 9
1.1.3. Khoảng cách
Một điều quan trọng và cần thiết là xây dựng một hàm mục tiêu đánh giá
khoảng cách giữa hai trình tự, qua đó đánh giá sự tương đồng, mối quan hệ giữa
hai hệ gen. Khoảng cách này có thể được tính toán theo một số hàm như thay thế,
chèn, xóa làm biến đổi một trình tự này thành một trình tự khác. Khoảng cách giữa
hai trình tự có thể chỉ được tính đơn giản chỉ là chi phí thay thế (Hamming
Hamming [10]) trong những trình tự có độ dài bằng nhau hay phức tạp hơn bao
gồm cả chi phí chèn – xóa và dịch chuyển.
1.2. Sắp hàng trình tự
Sắp hàng trình tự là một thủ tục cực kỳ quan trọng trong Tin sinh học, nó
được xem là nền tảng cho tất cả các thủ tục khác. Vấn đề đặt ra là tạo ra những sự
sắp hàng giữa các nucleotide thông qua việc chèn các ký tự gap, làm cho khoảng
cách giữa hai trình tự tức chi phí sửa chữa (là tổng chi phí cho các sự kiện chèn –
xóa, thay thế các nucleotide) giữa hai trình tự là nhỏ nhất (hoặc lớn nhất).
Đầu vào là 2 trình tự X = (x
1
, x
2
, …x
p
) và Y = (y
1
, y
2
, …y
q
), sắp hàng trình
tự X và Y là cách chèn các kí tự trống vào hai trình tự X và Y sao cho chúng có độ
dài bằng nhau và khoảng cách (chi phí sửa chữa) giữa hai trình tự là nhỏ nhất
(hoặc lớn nhất).
Các thuật toán quy hoạch động đầu tiên cho việc sắp hàng giữa các chuỗi
ký tự được trình bày bởi Levenshtein [14], với độ phức tạp về thời gian và bộ nhớ
là O(n
2
). Needleman và Wunsch [16] lần đầu tiên áp dụng thuật toán này vào
lĩnh vực Tin sinh học năm 1970. Yêu cầu bộ nhớ giảm xuống còn O(n) bởi
Hirschberg[12] trong khi thời gian chạy vẫn là O(n
2
). Những cải tiến của Ukkonen
[21,22] với những cặp trình tự có khoảng cách độ dài là d, thuật toán yêu cầu thời
gian O(nd) cho trường hợp xấu nhất và độ phức tạp thời gian trung bình là
O(d
2
+n). Thuật toán Quy hoạch động tính toán chi phí bắt cặp theo công thức sau:
Page | 10

(1)
Cost[i][j] là chi phí bắt tới vị trí i của trình tự 1 và vị trí j của trình tự 2, σ
i,j
là chi phí thay thế nucleotide ở vị trí thứ i của trình tự 1 và ở vị trí j của trình tự 2,
σ
index
là chi phí chèn- xóa một nucleotide.
Pairwise Alignment by Needleman and Wunsch
1 Cost[0][0] ← 0
2 {Khởi tạo cột đầu tiên}
3 for i = 0 to |X| do
4 Cost[i][0] ← Cost[i-1][0] + σ
index
5 {Khởi tạo hàng đầu tiên}
6 for j = 0 to |Y| do
7 Cost[0][i] ← Cost[0][j-21] + σ
index
8 {Quy hoạch động}
9 for i = 1 to |X| do
10 for j = 1 to |Y| do
11 ins ← Cost[i-1][j] + σ
index
12 del ← Cost[i][j-1] + σ
index
13 sub ← Cost[i-1][j-1] + σ
i,j
14 Cost[i-1][j-1] ← min(ins, del, sub)
15 end for
16 end for
17 return Cost[|X|][|Y|]
Thuật toán Needleman – Wunsch hoạt động khi mà chi phí cho việc
chèn – xóa các nucleotide là một trọng số cố định. Tức chi phí cho việc chèn
một đoạn gap có độ dài k là w
k
= kw
1
. Trên thực tế, việc tính toán chi phí chèn
– xóa thường phức tạp hơn, bao gồm chi phí cho việc bắt đầu và mở rộng các
đoạn gap.
Waterman [25], tiến hành thực nghiệm trên một khối lượng lớn các trình
tự với trọng số cho việc chèn gap w
k
≤ kw
1
với độ phức tạp thời gian là O(n
3
).
Page | 11
Lý do của việc tăng độ phức tạp về thời gian là do việc bổ sung thêm việc tính
toán chi phí chèn – xóa gap trong các trường hợp. Công thức được đưa ra:
(2)
Trong đó P[i][j] và Q[i][j] là chi phí chèn và xóa ở vị trí ( i , j)
Trong các trường hợp đặc biệt, chi phí chèn gap là một hàm tuyến tính w
k
=
uk +v trong đó v được gọi là chi phí bắt đầu một đoạn gap và v là chi phí mở rộng
đoạn gap. Gotoh (1982) [9] đã đưa ra một công thức tính toán tối ưu hóa việc tính
toán ma trận P và Q giảm độ phức tạp thời gian xuống còn O(n
2
). Công thức mà
Gotoh đưa ra là :
(3)
1.3. Sắp hàng trình tự hệ gen
Trong quá trình tiến hóa của các sinh vật, bên cạnh những biến đổi ở mức
độ điểm (sự thay thế chèn – xóa của các nucleotide) còn có những sự biến đổi ở
mức độ gen. Có 3 phép biến đổi chính ở mức độ gen là phép chèn gen, xóa gen và
dịch chuyển gen. Hình 2 mô tả một ví dụ về sự biến đổi ở mức độ gen giữa Người
và Khỉ. Ta thấy gen số 1 đã bị dịch chuyển, nó nằm ở đầu của hệ gen Người nhưng
lại nằm ở cuối ở hệ gen của Khỉ. Ngoài ra, gen số 2 tồn tại ở Khỉ nhưng không tồn
tại ở Người. Tức là hoặc nó bị xóa khỏi hệ gen của Người hoặc nó được chèn thêm
vào hệ gen của Khỉ. Do ta không phân biệt được phép chèn gen, và xóa gen, ta gọi
chung là phép chèn/xóa gen. Trải qua hàng triệu năm tiến hóa, với sự biến đổi ở
Page | 12

Xem chi tiết: SẮP HÀNG HOÀN CHỈNH HAI HỆ GENOME