Download miễn phí Khóa luận Các phương pháp sắp hàng đa chuỗi nhanh
Mục Lục:
Chương 1. Giới thiệu 1
1.1 Multiple alignment 1
1.2 Các chương trình sắp hàng đa chuỗi (multiple sequences alignment ) thông dụng hiện nay 3
Chương 2. Các phương pháp bắt cặp đa chuỗi 5
2.1 CLUSTALW 5
2.1.1 Tính toán ma trận khoảng cách giữa mọi cặp chuỗi 5
2.1.2 Tạo cây hướng dẫn (guide tree) 5
2.1.3 Progressive alignment 6
2.2. MUSCLE 7
2.2.1 Các loại khoảng cách và các cách xây dựng cây hướng dẫn 7
2.2.2 Profile alignment 8
2.2.3 Thuật toán 8
2.3 MAFFT 10
2.3.1 Bắt cặp nhóm sử dụng FFT 10
2.3.2 Hệ thống tính điểm 13
2.4 PROBCONS 15
Chương 3. Cây quyết định 17
3.1 Cách giải quyết của Chuong B. Do và Kazutaka Katoh 17
3.2 Vấn đề tốc độ 18
3.2.1 Dữ liệu với số lượng chuỗi lớn ( > 200 chuỗi) 18
3.2.2 Dữ liệu với số lượng sequence nhỏ, tổng số amino axit nhỏ 19
3.2.3 Dữ liệu với độ dài của chuỗi quá lớn ( > 2000 amino acids) 20
3.3 Vấn đề điểm chuẩn (benchmark) 21
3.3.1 Với các chuỗi có độ tương đồng cao 21
3.3.2 Với các chuỗi có độ tương đồng thấp 21
3.4 Cây quyết định 22
3.4.1 Cây quyết định cho yêu cầu tốc độ xử lý cao 23
3.4.2 Cây quyết định cho yêu cầu tốc điểm chuẩn cao 24
Chương 4: Kết quả thực nghiệm và bình luận 26
4.1 Giới thiệu về BAliBASE 26
4.1.1 BAliBASE 2 26
4.1.2 BAliBASE 3 26
4.1.3 Cách đánh giá của BAliBASE 27
4.2 Kết quả thực nghiệm 28
Chương 5: Kết Luận 34
Tài Liệu Tham Khảo 35
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-07-khoa_luan_cac_phuong_phap_sap_hang_da_chuoi_nhanh.72xDAImnDh.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53914/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ng công thức sau để tính khoảng cách giữa từng “hàng xóm” với nút mới. Ở đây: f, g là 2 hàng xóm và u là nút mới được tạo thành:
Khi một nút mới được tạo thành ta dùng công thức sau để tính khoảng cách của nó với các nút cũ:
Ở đây, u là nút mới, k là nút cũ, f và g là 2 phần tử tạo nên nút mới u.
2.1.3 Progressive alignment
Dựa vào cây hướng dẫn (guide tree) được tạo ra từ bước 2, chúng ta sử dụng sắp hàng các chuỗi từ nút lá cho đến gốc của cây. Mỗi bước sẽ là quá trình sắp hàng 2 nhóm chuỗi đã được sắp hàng trước đó sử dụng thuật toán quy hoạch động [9] [10]. Gap ở những nhóm chuỗi này được giữ nguyên trong kết quả tạo thành. Việc này lặp đi lặp lại cho đến khi gặp gốc của cây hướng dẫn. Đó là kết quả cuối cùng.
2.2. MUSCLE
2.2.1 Các loại khoảng cách và các cách xây dựng cây hướng dẫn
MUSCLE[6] sử dụng hai cách để xác định khoảng cách giữa các chuỗi đó là khoảng cách K-mer[11] cho những cặp chuỗi chưa được sắp hàng và khoảng cách Kimura[12] cho những cặp đã được sắp hàng (có độ dài bằng nhau).
K-mer[11] được định nghĩa là một chuỗi có độ dài bằng K của các amino acid đứng liền kề nhau. Thuật toán sử dụng K-mer không đòi hỏi cặp chuỗi cần sắp hàng mà ưu điểm lớn của nó là kết quả thu được với tốc độ khá cao (độ phức tạp thuật toán là O(L) với L là độ dài của chuỗi) [11].
Hình 1: Ví dụ về k-mer [6]
Hình 1 thể hiện một ví dụ của K-mer, với K = 3, ở các chuỗi trên dễ dàng nhận thấy K-mer là 6 và tại các chuỗi ở phần dưới K-mer là 13. Tương tự như vậy với K = 4 các chuỗi bên trên K-mer là 4 và các chuỗi dưới K-mer là 9.
Khoảng cách Kimura[12] giữa 2 chuỗi đã được sắp hàng (có độ dài bằng nhau) được tính theo công thức sau:
DK2p= -1/2 ln(1-2P-Q) – ¼ ln(1/2Q)
Ở đây, P là số lượng transition và Q là số lượng transversion trong hai chuỗi. Transition là một phép thay thế khi thay A bởi G, C bởi T hay ngược lại. Trong khi đó Transversion là phép thay thế A bởi C hay T hay các trường hợp tương tự.
Sau khi xây dựng xong ma trận khoảng cách, MUSCLE[6] sử dụng thuật toán UPGMA[13] để nhóm các chuỗi lại với nhau. UPGMA[13] là một thuật toán xây dựng cây hướng dẫn cho việc sắp hàng từng profile. Đầu vào của UPGMA[13] là một ma trận khoảng cách. Ở mỗi bước 2 nút gần nhất được nhóm lại với nhau tạo thành một nút mới và ma trận khoảng cách được tính lại theo công thức sau:
Ở đây, chúng ta tính khoảng cách giữa 2 nút A và B; x và y lần lượt là các nút ban đầu trong A và B; d(x, y) là khoảng cách giữa 2 nút x và y.
2.2.2 Profile alignment
Để áp dụng bắt cặp sóng đôi vào các profiles, điều cần thiết là xác định một hàm tính điểm cho một cách sắp hàng.
Ta coi i, j là 2 amino acid, pi là xác xuất i xuất hiện, pij là xác xuất i và j được align với nhau, fxi là xác suất của i xuất hiện tại cột x của profile thứ nhất, fxG là xác suất xuất hiện một gap tại cột x trong các profile. Khi đó MUSCLE[6] đưa ra hàm tính Log-Expectation theo công thức sau:
LExy = (1 - fxG)(1- fyG) log ∑i∑j fxi fyi pij/pipj
MUSCLE[6] sử dụng các tham số pi và pij là các tham số của ma trận 240 PAM VTML [14].
2.2.3 Thuật toán
Thuật toán MUSCLE[6] là một loạt các bước sử dụng các khái niệm đã trình bày ở trên. Tuy nhiên tổng quát lại nó bao gồm 3 phần chính là:
Phần 1: draft progessive.
Phần 2: improved progessive.
Phần 3: Refinement.
Mỗi phần làm một nhiệm vụ riêng biệt, nhưng kết nối chặt chẽ với nhau bởi đầu ra của phần này là đầu vào của phần tiếp theo.
Hình 2: Các bước thực hiện của MUSCLE [6]
Phần 1: draft progessive. Mục tiêu chính của phần này là tạo ra một đa chuỗi thẳng hàng mà vấn đề chính là tốc độ chứ không phải là sự chính xác.
Sử dụng khoảng cách K-mer[8] để xác định khoảng cách giữa mỗi cặp của chuỗi dầu vào. Tạo ra ma trận khoảng cách D1.
Sử dụng thuật toán UPGMA[13] để xây dựng cây hướng dẫn TREE1.
Ở mỗi lá của cây Tree1, một profile được tạo ra từ một chuỗi đầu vào. Các nút trong cây được thăm theo thứ tự tiền tố (nghĩa là các nút con được thăm trước cha mẹ). Ở mỗi nút trong (internal node) phương pháp một bắt cặp sóng đôi (pairwise alignment - một đa chuỗi thẳng hàng nhưng chỉ có được xây dựng từ 2 profile) được xây dựng từ 2 nút con. Việc này lặp đi lặp lại cho đến khi gặp gốc của cây. Đó chính là đa chuỗi thẳng hàng – mục tiêu của bước này.
Phần 2: improved progessive. Hầu hết các lỗi trong phần một đều do việc sử dụng khoảng cách K-mer[11], phần 2 sẽ tạo lại cây bằng cách sử dụng khoảng cách Kimura[12]. Phương pháp này cho kết quả tốt hơn nhưng đòi hỏi các chuỗi phải được sắp hàng (có độ dài bằng nhau).
Với mỗi cặp chuỗi trong MSA1, chúng ta tính khoảng cách cho chúng sử dụng khoảng cách Kimura[12]. Kết quả ta có ma trận khoảng cách D2.
Từ ma trận khoảng cách D2, sử dụng phương pháp UPGMA[13] ta tạo nên cây Tree2.
Làm tương tự bước 1.3 với cây Tree2 ta được đa chuỗi thẳng hàng MSA2.
Phần 3: Refinement. Tìm phương án tốt nhất.
- Bước 3.1 Một cạnh được chọn từ Tree2 (cạnh được chọn bằng cách giảm dần khoảng cách tới gốc)
- Bước 3.2 Chia cây Tree2 thành 2 phần bằng cách bỏ cạnh vừa chọn, sau đó tính lại các profile trên mỗi phần đó.
- Bước 3.3 Tạo ra một đa chuỗi thẳng hàng (sequences alignment) mới bằng cách sắp hàng một lần nữa 2 profile vừa được tạo ra.
- Bước 3.4 Nếu điểm SP (sum of pair)[23] được cải thiện thì cách sắp hàng mới được giữ lại, ngược lại ta bỏ đi.
- Lặp lại các bước 3.1-3.4 cho tới khi hội tụ hay đi tới giới hạn do người sử dụng định nghĩa[15].
2.3 MAFFT
2.3.1 Bắt cặp nhóm sử dụng FFT
Biểu diễn một amino acid dưới dạng một vector
Tần suất của sự thay thế các amino acid phụ thuộc mạnh mẽ vào các thuộc tính lí hóa của chúng, đặc biệt là các thuộc tính khối lượng (volume) và độ phân cực (polarity)[16]. Do đó để biểu diễn một amino acid a dưới dạng vector thì ta cần một vector trong đó các thành phần của vector này là v(a) – thể hiện thuộc tính khối lượng và p(a) – thể hiện thuộc tính độ phân cực[17]. Ở đây, MAFFT[4] đã sử dụng các giá trị v(a) và p(a) đã được chuẩn hóa để thuận lợi cho việc tính toán sau này. Công thức xác định các giá trị chuẩn hóa đó là:
Trong dó các giá trị và là các giá trị trung bình, các giá trị là độ lệch tiêu chuẩn.
Khi đó một chuỗi amino acid sẽ được chuyển thành một chuỗi các vector.
Tính toán mối quan hệ giữa hai chuỗi amino acid
Mối tương quan về mặt khối lượng giữa 2 chuỗi amino acid được tính theo công thức sau
Trong đó N và M là độ dài của 2 amino acid. là giá trị của thuộc tính khối lượng của 2 amino acid tại vị trí thứ n. k là độ trễ trong phép tính. Việc định nghĩa k sẽ được nêu ở phần sau.
Bằng một cách hoàn toàn tương tự ta sẽ tính được giá trị . Khi đó hàm quan hệ giữa 2 chuỗi amino acid này được định nghĩa theo công thức
c(k) = cv(k) + cp(k).
Nếu ta coi N = M trong trường hợp trên, khi đó độ phức tạp của thuật toán để tính mối quan hệ này là O(N2). Tuy nhiên, dựa vào biến đổi Fourier ta có thể tối ưu bước này và giảm độ phức tạp thuật toán xuống còn O(N logN) [18]. Xét với trường hợp tính toán cv(k), ta c...
