Áp dụng phương pháp dóng hàng trình tự cho bài toán dự đoán biến thể gen

Một số khái niệm về sinh học phân tử và di truyền

Các phân tử của một tế bào

Một tế bào bao gồm các phân tử nhỏ như adenosine triphosphate (ATP), epinephrine, chất dẫn truyền thần kinh, nước, đường, acid béo, amino acid và nucleotide, có chức năng mang năng lượng và truyền tín hiệu Những phân tử này có thể tồn tại độc lập hoặc kết hợp tạo thành các đại phân tử, trong đó protein và nucleic acid là hai đại phân tử quan trọng nhất trong sinh học.

Protein là chuỗi dài được hình thành từ hàng trăm đến hàng nghìn amino acid, với sự đa dạng bắt nguồn từ 20 loại amino acid khác nhau Trình tự của các amino acid xác định cấu trúc 3 chiều độc đáo của mỗi protein, từ đó quy định chức năng cụ thể như kháng thể, enzyme, điều khiển, thành phần cấu trúc, vận chuyển và dự trữ.

Deoxyribonucleic acid (DNA) là vật chất di truyền chính ở người và hầu hết các sinh vật, mang thông tin về sản xuất protein thông qua bộ ba mã di truyền Hầu hết các tế bào trong cơ thể người chứa cùng một loại DNA trong nhân tế bào, gọi là DNA nhân, trong khi một lượng nhỏ DNA cũng tồn tại trong ty thể (DNA ty thể hoặc mtDNA) và lục lạp.

Cấu trúc ba chiều của DNA là một chuỗi xoắn kép gồm hai sợi dài cuộn quanh nhau, được tạo thành từ các nucleotide bao gồm đường deoxyribose, nhóm phosphate và bốn bazơ hữu cơ adenine (A), guanine (G), cytosine (C) và thymine (T) Các nucleotide liên kết với nhau qua liên kết cộng hóa trị giữa nhóm phosphate và nhóm -OH của các nucleotide kế tiếp, hình thành nên trục xoắn Mỗi chuỗi xoắn kép được kết nối bởi các liên kết hidro giữa các cặp bazơ: A liên kết với T và G liên kết với C, tạo nên sự bổ sung ngược giữa hai sợi DNA.

Gen là đơn vị chức năng của DNA, bao gồm vùng mã hóa xác định trình tự amino acid của protein và vùng điều hòa kiểm soát thời gian cũng như tế bào sản xuất protein Hiện nay, các nhà khoa học đã phát hiện khoảng 21.000 gen mã hóa protein, chiếm 2% hệ gen con người, trong khi 98% còn lại là vùng điều hòa biểu hiện gen và những chức năng chưa được khám phá.

Ribonucleic acid (RNA) là một phân tử polymer được liên kết bởi các nucleotide RNA tương đối giống DNA về cấu trúc và cấu tạo, chúng chỉ khác

1 https://ghr.nlm.nih.gov/primer/howgenswork/protein

2 https://ghr.nlm.nih.gov/primer/basics/dna

1.1 Một số khái niệm về sinh học phân tử và di truyền nhau ở hai điểm: RNA có dạng sợi đơn gập vào chính nó trong khi DNA có dạng sợi xoắn kép; T trong DNA được thay thế bằng Uracil (U) trong RNA.

Chuỗi xoắn kép DNA bao gồm hai sợi dài xoắn quanh một trục, trong đó mỗi sợi là phiên bản bổ sung ngược của sợi kia Các phân tử đường trong DNA có nhóm phosphate liên kết với carbon 5' của nucleotide, tạo thành liên kết cộng hóa trị với nhóm -OH ở carbon 3' của nucleotide tiếp theo, hình thành trục xoắn của sợi DNA Hai sợi DNA được kết nối với nhau thông qua các liên kết hidro giữa các cặp bazơ: hai liên kết hidro nối giữa T và A, và ba liên kết hidro nối giữa G và C.

3 https://www.nature.com/scitable/topicpage/discovery-of-dna-structure-and-function- watson-397/

1.1 Một số khái niệm về sinh học phân tử và di truyền

Luận thuyết trung tâm

Luận thuyết trung tâm mô tả quy trình chuyển giao thông tin giữa DNA, RNA và protein Tế bào chuyển đổi thông tin mã hóa trong DNA thành protein thông qua hai bước chính: phiên mã và dịch mã Trong phiên mã, vùng mã hóa của gen được sao chép thành RNA, và ở tế bào nhân thực, RNA ban đầu được xử lý thành mRNA nhỏ hơn, di chuyển đến tế bào chất Tại đây, ribosome, một cỗ máy phân tử phức tạp, thực hiện quá trình dịch mã bằng cách lắp ráp và liên kết các amino acid theo thứ tự do mRNA quy định.

Các amino acid được hình thành từ các bộ ba mã hóa được tạo thành từ 4 nucleotide A, C, G, U, với tổng cộng 64 bộ ba khác nhau Nhiều bộ ba có thể tương ứng với cùng một amino acid; ví dụ, UUU và UUC đều đại diện cho Phenylalanine, một α-amino acid không phân cực và trung hòa điện Sợi đơn DNA khuôn mẫu đóng vai trò quan trọng trong quá trình phiên mã tại các trình tự dài từ 100 nucleotide trở lên.

1000 bp được gọi là promoter, nằm trước vùng hóa RNA và không tham gia vào quá trình phiên mã tạo mRNA Vùng phía 3' của promoter được gọi là vùng thượng nguồn (upstream), trong khi vùng phía 5' là vùng hạ nguồn (downstream) Vùng hạ nguồn chứa vùng mã hóa RNA dài từ 20.000 đến 30.000 bp Sản phẩm phiên mã đầu tiên của gen là pre-mRNA, bao gồm cả các đoạn intron (không mã hóa amino acid) và exon (mã hóa amino acid).

Tế bào loại bỏ các intron để tạo ra mRNA trưởng thành trước khi tiến hành dịch mã Mặc dù mRNA chứa các codon, không phải tất cả các trình tự đều tham gia vào quá trình này Vùng 5' UTR, nằm giữa nucleotide đầu tiên và codon bắt đầu AUG, không tham gia dịch mã và chứa các trình tự điều hòa Vùng này dài khoảng 170 nucleotides và gắn với protein ribosome Codon đầu tiên AUG mã hóa cho Methionine, có thể là amino acid của protein hoặc bị loại bỏ Quá trình dịch mã kết thúc tại codon kết thúc, có thể là UAA, UAG, hoặc UGA, không mã hóa cho amino acid nào.

Nhiễm sắc thể

DNA chủ yếu nằm trong nhân của tế bào nhân thực, được gấp nhiều lần thành các nhiễm sắc thể và tái tạo trong quá trình phân chia tế bào Mỗi nhiễm sắc thể bao gồm một phân tử DNA liên kết với các protein nhất định Khi tế bào phân chia, một cỗ máy phân chia gồm nhiều protein sẽ hoạt động để đảm bảo quá trình này diễn ra suôn sẻ.

1.1 Một số khái niệm về sinh học phân tử và di truyền là replisome) tách DNA trong nhiễm sắc thể thành hai sợi, mỗi sợi được dùng làm khuôn để tổng hợp nên sợi bổ sung ngược của nó Kết quả là chúng ta có hai chuỗi DNA mới giống chuỗi ban đầu Ngoại trừ tế bào trứng và tinh trùng, mỗi tế bào người có 23 cặp nhiễm sắc thể, một nửa được di truyền từ bố, nửa còn lại được di truyền từ mẹ, do đó có hai bản sao của một gen được di truyền từ bố và mẹ (lưỡng bội, hay diploid) Riêng đối với các nhiễm sắc thể giới tính, nữ giới sở hữu hai nhiễm sắc thể X trong khi nam giới sở hữu một nhiễm sắc thể

Quá trình phân chia tế bào trứng và tinh trùng gọi là meiosis, diễn ra qua hai giai đoạn phân bào Quá trình này chia một tế bào ban đầu thành 4 tế bào con, mỗi tế bào con chứa một bản sao của mỗi nhiễm sắc thể, tức là ở trạng thái đơn bội (haploid).

Hình 1.2: Sợi đơn DNA khuôn mẫu đánh dấu quá trình phiên mã tại vùng promoter, vùng này không tham gia quá trình phiên mã Vùng từ promoter đến

Vùng thượng nguồn (3' UTR) và hạ nguồn (5' UTR) của gen chứa các thông tin quan trọng cho quá trình phiên mã Vùng hạ nguồn chứa đoạn mã hóa RNA và kết thúc tại đoạn terminator Các pre-mRNA sau khi phiên mã từ gen bao gồm cả exon (mã hóa amino acid) và intron (không mã hóa amino acid) Tế bào sẽ loại bỏ intron để tạo ra mRNA trưởng thành trước khi tiến hành dịch mã Trong mRNA, đoạn 5' UTR gắn với ribosome và bao gồm các trình tự điều hòa không tham gia vào quá trình dịch mã Vùng dịch mã chứa các codon, với codon bắt đầu là AUG và codon kết thúc có thể là UAA, UAG hoặc UGA, không mã hóa cho amino acid nào.

1.1 Một số khái niệm về sinh học phân tử và di truyền

Đột biến

Đột biến là sự thay đổi trình tự nucleotide trong quá trình nhân đôi DNA, dẫn đến sự thay đổi chức năng protein Chúng có thể có lợi, có hại hoặc không ảnh hưởng đến sinh vật Đột biến có thể di truyền nếu xảy ra trong tế bào mầm, như tế bào chứng và tinh trùng, trong khi đột biến không di truyền xảy ra trong tế bào soma, tức là các tế bào không tham gia vào việc hình thành con cái Dù vậy, đột biến trong tế bào soma vẫn có thể tích lũy theo thời gian và gây ra các bệnh như ung thư.

Đột biến liên quan đến một số khái niệm quan trọng như allele, kiểu gen, kiểu hình và biến thể, sẽ được đề cập nhiều trong các phần tiếp theo.

• Allele: là các phiên bản khác nhau của gen mã hóa cho các phiên bản khác nhau của protein.

Kiểu gen (genotype) là tập hợp các allele quyết định các đặc điểm thể chất của sinh vật, như màu mắt và chiều cao, trong khi kiểu hình (phenotype) là sự biểu hiện của những đặc điểm này Ví dụ, một cá thể có kiểu gen với hai allele quy định màu mắt, trong đó allele 1 từ bố biểu hiện màu mắt xanh và allele 2 từ mẹ biểu hiện màu mắt đen, sẽ có kiểu hình là màu mắt xanh Điều này cho thấy kiểu hình là kết quả của kiểu gen kết hợp với ảnh hưởng từ môi trường.

Biến thể (variant) là vùng của gen với sự khác biệt về trình tự, trong khi bộ gen con người có 3 tỷ cặp bazơ tương ứng với 6 tỷ nucleotide, 99,9% trình tự là giống nhau Chỉ có khoảng 6 triệu nucleotide khác nhau giữa các cá thể Các biến thể này phát sinh trong quá trình nhân đôi DNA với tỷ lệ một trên một tỷ cặp bazơ, dẫn đến việc mỗi lần tế bào phân chia và DNA được sao chép sẽ xuất hiện trung bình 3 nucleotide khác biệt.

Một gen đột biến có thể bao gồm nhiều biến thể khác nhau Để đánh giá tác động của đột biến gen, cần xác định các loại biến thể và mức độ ảnh hưởng của chúng đến cơ thể sống.

Bệnh liên quan đến gen

Sự thay đổi trong trình tự DNA ở cấp độ loài có thể giúp loài thích nghi với môi trường sống hoặc dẫn đến sự tuyệt chủng Ở cấp độ cá nhân, một số đột biến có thể cải thiện thể chất, trong khi hầu hết không ảnh hưởng đến chức năng sinh học và một số khác thì không phù hợp Các bệnh có thể phát sinh từ những đột biến này.

Các công nghệ giải trình tự DNA

Giải trình tự Sanger

Công nghệ giải trình tự DNA đầu tiên được phát triển bởi Frederick Sanger và các cộng sự vào năm 1977, sau đó thương mại hóa vào năm 1986 Phương pháp giải trình tự Sanger dựa trên việc sao chép DNA trong ống nghiệm Nhờ công nghệ này, bộ gen người đầu tiên đã được giải trình trong vòng một thập kỷ Quy trình giải trình tự Sanger bao gồm bốn bước chính.

Để tách sợi xoắn kép DNA thành hai sợi đơn, bước đầu tiên là gia nhiệt Quá trình này diễn ra nhờ vào việc liên kết hidro giữa hai sợi DNA, vốn dễ bị phân tách khi nhiệt độ tăng.

1.2 Các công nghệ giải trình tự DNA

Bước 2 trong quá trình tổng hợp DNA là bơm protein DNA polymerase và bổ sung các nucleotide mới DNA polymerase đóng vai trò quan trọng trong việc liên kết các nucleotide, tạo nên sợi bổ sung ngược dựa trên sợi khuôn mẫu ban đầu.

Để ngăn chặn sự kéo dài của các sợi bổ sung ngược, nucleotide chỉnh sửa được đánh dấu bằng chất huỳnh quang với các màu khác nhau được thêm vào Khi mỗi chuỗi bổ sung ngược liên kết với một nucleotide chỉnh sửa, DNA polymerase không thể tiếp tục thêm nucleotide, dẫn đến việc dừng lại của chuỗi bổ sung ngược Sau đó, cả sợi khuôn mẫu và sợi bổ sung ngược được tách ra, mỗi sợi trở thành khuôn mẫu cho việc tổng hợp DNA mới Qua mỗi chu trình, số lượng DNA tăng gấp đôi, nhưng chiều dài các sợi bổ sung ngược ngắn hơn sợi khuôn mẫu và được gọi là các đoạn (fragment) với chiều dài không xác định do vị trí ngẫu nhiên của các nucleotide chỉnh sửa.

Trong bước 4 của quá trình giải trình tự DNA, các đoạn DNA mang điện tích âm được đưa qua ống nghiệm chứa gel trong trường điện, với các fragment ngắn hơn di chuyển nhanh hơn Một nguồn laser chiếu vào các fragment, cho phép máy xác định loại nucleotide dựa trên huỳnh quang Quá trình này tiếp tục cho đến khi máy đọc được chuỗi trình tự Công nghệ giải trình tự Sanger có xác suất tổng hợp các đoạn dài nhỏ, với chiều dài trình tự tối đa chỉ 1000 bp; các trình tự dài hơn sẽ được chia thành các phần nhỏ hơn để giải trình tự riêng biệt Mặc dù Sanger chậm hơn so với giải trình tự thế hệ mới (NGS), nhưng nó vẫn được ưa chuộng nhờ độ chính xác cao, thường được sử dụng để giải trình tự nhắm mục tiêu đến gen và kiểm tra kết quả từ các phương pháp mới.

Giải trình tự thế hệ tiếp theo (NGS)

Công nghệ giải trình tự thế hệ tiếp theo (NGS) đã cách mạng hóa việc giải trình tự DNA với tốc độ nhanh chóng và chi phí ngày càng thấp, dẫn đến nhiều thành tựu khoa học ấn tượng và ứng dụng sinh học mới Tính đến năm 2008, NGS có khả năng tạo ra khối lượng dữ liệu tương đương với hàng trăm máy giải trình Sanger chỉ trong 24 giờ và chỉ cần một người vận hành So với phương pháp Sanger truyền thống, NGS đã có những cải tiến vượt bậc, cho phép thực hiện thao tác song song trên nhiều đoạn DNA trong mỗi chu kỳ, thay vì chỉ một đoạn như trước đây.

1.2 Các công nghệ giải trình tự DNA

Phương pháp giải trình tự Sanger gồm 4 bước chính Đầu tiên, DNA được gia nhiệt để tách thành hai sợi đơn Tiếp theo, protein DNA polymerase và các nucleotide mới được bổ sung để tổng hợp DNA mới Để ngăn chặn sự kéo dài của các sợi tổng hợp, nucleotide chỉnh sửa được thêm vào, với các nucleotide này được đánh dấu bằng chất huỳnh quang với màu sắc khác nhau Cuối cùng, các đoạn DNA mang điện tích âm được đưa qua ống nghiệm chứa gel trong trường điện, nơi đoạn ngắn hơn sẽ di chuyển nhanh hơn và đến đáy ống trước Nguồn laser chiếu vào đáy ống nghiệm giúp xác định loại nucleotide chỉnh sửa, và quá trình này lặp lại cho đến khi máy giải trình tự đọc được chuỗi trình tự hoàn chỉnh.

1.2 Các công nghệ giải trình tự DNA

Công nghệ giải trình tự thế hệ tiếp theo (NGS) đang được nhiều tổ chức phát triển, dẫn đến sự xuất hiện của nhiều phương pháp khác nhau Bài viết này sẽ khám phá các bước chính trong một phương pháp tiêu biểu của công nghệ NGS.

Để chuẩn bị thư viện NGS, trước tiên cần tạo các thư viện DNA tương ứng với mỗi bản sao DNA, sau đó cắt thành các đoạn nhỏ hơn Trong quá trình này, các trình tự chỉ số (index) được thêm vào đầu các đoạn DNA để phân loại thư viện Mỗi thư viện NGS sẽ có một trình tự chỉ số riêng biệt, giúp phân biệt khi chúng được kết hợp trên một flow cell trong quá trình multiplexing Các trình tự chỉ số cũng được giải trình tự để tách các fragment của các thư viện khác nhau trong quá trình demultiplexing Ngoài ra, các adapter, là các đoạn nucleotide bổ sung ngược, được thêm vào cuối mỗi đoạn DNA Trình tự nhận được từ một fragment gọi là read, không bao gồm trình tự chỉ số và adapter Nếu read chứa một phần adapter, nó sẽ bị nhiễm bẩn adapter Để hạn chế nhiễm bẩn này, cần chọn các fragment có chiều dài tương đương, bước này được gọi là chọn cỡ (size selection), với miền giá trị cỡ thay đổi tùy theo yêu cầu của từng máy giải trình tự.

Trong bước 2, các fragment được tổng hợp và gắn vào flow cell, nơi các chu kỳ giải trình tự chưa diễn ra Các fragment này được chuẩn bị từ thư viện NGS và liên kết với các oligo cố định trên flow cell thông qua các adapter Sau đó, protein DNA polymerase và nucleotide mới được thêm vào, bắt đầu quá trình tổng hợp các đoạn bổ sung ngược từ vị trí của các oligo Các đoạn DNA xoắn kép sẽ được gia nhiệt để tách thành hai đoạn xoắn đơn theo chiều thuận và nghịch Bước 3 là loại bỏ các fragment không cần thiết, ảnh hưởng đến loại read từ máy giải trình tự Mục tiêu là tạo ra các fragment chỉ cùng một chiều hoặc cả hai chiều, và các fragment cùng một chiều phải được tổng hợp tách biệt, do đó cần loại bỏ các fragment trong thư viện NGS.

1.2 Các công nghệ giải trình tự DNA

Trong quy trình chuẩn bị thư viện NGS, bước đầu tiên là cắt DNA thành những đoạn nhỏ và thêm adapter vào cuối các đoạn này Sau đó, các đoạn DNA được gia nhiệt để tách thành các fragment chứa adapter và index Tiếp theo, các fragment được đưa vào flow cell, nơi chúng liên kết với oligo thông qua adapter bổ sung DNA polymerase và nucleotide mới được bơm vào flow cell để tổng hợp các fragment nghịch và thuận Bước tiếp theo là loại bỏ các fragment không cần thiết; các đoạn DNA mới được gia nhiệt để tách thành sợi xoắn đơn, và các fragment không gắn oligo sẽ bị loại bỏ Cuối cùng, các fragment có chiều nghịch chứa oligo được giữ lại để sử dụng cho quá trình tổng hợp các fragment thuận Trong bước cuối cùng, các chu kỳ giải trình tự diễn ra, với các nucleotide chỉnh sửa được bơm vào để xác định loại nucleotide qua màu sắc đánh dấu, sau đó nucleotide sẽ trở về trạng thái bình thường và quy trình lại bắt đầu.

1.2 Các công nghệ giải trình tự DNA ban đầu và các fragment có chiều thuận hoặc nghịch gắn với oligo Không mất tính tổng quát, giả sử ta cần tổng hợp các fragment có chiều thuận, do đó cần dữ lại các fragment có chiều nghịch Vì sau khi gia nhiệt, các fragment của thư viện NGS ban đầu không còn liên kết với các oligo, nên chúng dễ dàng bị loại bỏ Các fragment có chiều thuận gắn với oligo thì vẫn liên kết chặt với flow cell, để loại bỏ chúng máy giải trình tự sẽ tiến hành cắt bỏ loại oligo gắn với các fragment này Cuối cùng, ta nhận được các fragment chỉ có một chiều nghịch được gắn chặt với flow cell.

Bước 4 trong quy trình giải trình tự thế hệ tiếp theo liên quan đến việc thực hiện các chu kỳ giải trình tự, trong đó các nucleotide chỉnh sửa sẽ được đảo ngược về các nucleotide thường Trước khi quá trình đảo ngược diễn ra, một máy ảnh ghi lại các nucleotide này, được phân biệt bằng màu huỳnh quang Quá trình này lặp đi lặp lại cho đến khi máy giải trình tự có thể đọc được trình tự của đoạn xoắn đơn DNA Hai cải tiến chính của giải trình tự thế hệ tiếp theo so với giải trình tự Sanger bao gồm khả năng ghi nhận nucleotide qua màu huỳnh quang và quy trình đảo ngược liên tục để thu thập dữ liệu chính xác hơn.

Quá trình chỉnh sửa nucleotide sau khi đọc sẽ chuyển đổi thành nucleotide thông thường, tiếp tục với việc tổng hợp sợi bổ sung ngược lại Quá trình này diễn ra liên tục và mỗi chu kỳ kết thúc bằng một lần đọc nucleotide, với số chu kỳ tương ứng với số nucleotide được đọc Đây được gọi là giải trình tự bằng phương pháp tổng hợp.

Thay vì ống nghiệm, phương pháp mới sử dụng miếng kính gọi là flow cell với nhiều làn, không có trường điện hay DNA tích điện âm Thay vào đó, phương pháp này sử dụng adapter và oligo, cho phép tổng hợp và tách biệt hàng nghìn fragment đồng thời.

Từ cơ chế hoạt động của công nghệ NGS, ta rút ra một số khái niệm sau:

Thư viện DNA là tập hợp DNA được chiết xuất từ một cá thể nhằm phục vụ cho quá trình giải trình tự Sau khi lấy mẫu, DNA sẽ được cắt thành các đoạn nhỏ hơn, mỗi đoạn thuộc về một thư viện cụ thể Các đoạn này sẽ tạo thành các mẫu xếp chồng, cho phép sử dụng thuật toán để ghép nối chúng lại với nhau.

Oligo là đoạn ngắn của DNA đơn nhân tạo được gắn vào flow cell, giúp liên kết với các fragment thông qua các adapter Quá trình này cố định vị trí của các đoạn sợi đơn DNA trong quá trình tổng hợp.

1.3 Các bài toán tin sinh học

Adapter là các đoạn nucleotide nhân tạo được gắn vào cuối mỗi đoạn DNA, có cấu trúc bổ sung ngược với các Oligo, cho phép chúng liên kết với nhau Sau khi trải qua quá trình gia nhiệt, các đoạn DNA sẽ tách ra thành sợi đơn, mỗi sợi đơn sẽ mang các adapter ở cuối.

• PCR (polymerase chain reaction): là kỹ thuật tạo nhiều bản sao DNA nhờ sử dụng enzyme DNA polymerase.

• Thư viện NGS (NGS library): bao gồm các đoạn sợi đơn DNA của một cá thể được gắn adapter (xem hình 1.4, bước 1).

Cụm (cluster) bao gồm một fragment, trong đó oligo là phần trình tự gắn với flow cell và đoạn tổng hợp ngược của nó trong quá trình các chu kỳ tiếp diễn Các fragment chứa oligo được tổng hợp từ thư viện NGS và được liên kết với oligo thông qua các adapter.

Các loại trình tự nhận được từ máy giải trình tự

Trong công nghệ NGS, các đoạn fragment được tổng hợp theo cùng một chiều Dựa vào chiều và khoảng cách giữa các read, có ba loại trình tự có thể được xuất ra từ máy giải trình tự.

• Single-end reads: toàn bộ các read được tổng hợp theo cùng một chiều thuận hoặc nghịch.

Paired-end reads là hai read của cùng một đoạn DNA được tổng hợp theo cả hai chiều thuận và nghịch, có thể có hoặc không có trình tự chung Việc kết hợp hai read này tạo ra một read dài hơn so với single-end read, đồng thời giúp cải thiện quá trình lắp ráp trình tự và phát hiện các biến thể.

Mate pairs refer to two reads derived from the same DNA segment that lack a shared sequence The length of the fragment is the sum of the lengths of the two reads, the inner distance, and the adapter When excluding the adapter, this results in an insert size Mate pairs are a specific type of paired-end reads characterized by longer insert sizes, typically ranging from 2000 bp to 5000 bp.

Các bài toán tin sinh học

Một số bài toán phổ biến

Trong những năm gần đây, liệu pháp gen và chỉnh sửa gen đã trở thành những chủ đề nóng hổi trong lĩnh vực y học Những công nghệ này mở ra nhiều triển vọng mới trong việc điều trị các bệnh di truyền và cải thiện sức khỏe con người.

1.3 Các bài toán tin sinh học nhà khoa học đã không ngừng khám phá những thông điệp còn ẩn dấu trong các trình tự sinh học Ví dụ, tần số xuất hiện của một mẫu trình tự trong một đoạn DNA, cơ chế nhân đôi DNA, và quá trình khử amin cho chúng ta manh mối về vùng bắt đầu sao chép của DNA (gọi là oriC) [Com15] Bài toán định vị oriC không chỉ giúp ta hiểu cách tế bào tái tạo mà còn giúp con người giải quyết các vấn đề y sinh khác nhau Một ứng dụng của nó là phương pháp trị liệu gen, người ta cấy một bộ gen nhỏ được biến đổi gen (được gọi là vector virus) vào thành tế bào Trong nông nghiệp, vectơ virus mang gen nhân tạo đã được sử dụng để tạo ra cà chua chịu sương giá và ngô kháng thuốc trừ sâu Năm 1990, trong bài báo "Sự bắt đầu", bác sỹ William French Anderson đã công bố liệu pháp gen lần đầu tiên được thực hiện thành công trên người khi nó cứu sống của một bé gái bốn tuổi bị rối loạn suy giảm miễn dịch kết hợp nghiêm trọng [And90] Một ví dụ khác, quá trình phiên mã DNA thành các mRNA cho chúng ta tín hiệu về việc xác định các gen quy định chức năng của protein Quá trình này đóng vai trò cốt yếu trong bài toán phân tích biểu hiện gen.

Kể từ khi Watson và Crick phát hiện cấu trúc xoắn kép của DNA, nhiều thách thức đã xuất hiện nhằm giải mã bộ gen người và ứng dụng kiến thức vào thực tiễn Tài liệu "Giới thiệu về tin sinh học" 4 của Hồ Tú Bảo đã phân loại một số bài toán liên quan đến tin sinh học.

So sánh cấu trúc protein

Dự đoán cấu trúc protein

Mô hình hóa cấu trúc RNA

• Phân tích đường chuyển hóa: Đường trao đổi chất (metabolic pathway)

Mạng điều hòa (reguratory networks)

Dóng hàng trình tự (sequence alignment)

Dự đoán chức năng và cấu trúc

Phân tích biểu hiện gen

4 http://www.jaist.ac.jp/ bao/Writings/IntroBioinformaticsV.pdf

1.3 Các bài toán tin sinh học

Công nghệ chỉnh sửa gen CRISPR-Cas9, một trong những công nghệ sinh học hiện đại, cho phép cắt DNA tại các vị trí cụ thể Phương pháp này đã được ứng dụng để chỉnh sửa các đột biến gen gây bệnh ở phôi người và hứa hẹn sẽ mở ra cơ hội chữa trị nhiều bệnh lý liên quan đến gen trong tương lai.

Bài toán dự đoán ảnh hưởng của biến thể gen

1.3.2.1 Một số cách tiếp cận và hạn chế

Phân tích liên kết (Linkage analysis) là một công cụ quan trọng trong di truyền học, giúp tạo bản đồ ánh xạ liên kết để hiển thị thông tin di truyền liên quan đến các nhóm liên kết trong bộ gen Đơn vị ánh xạ được đo bằng centiMorgans (cM), với tần số tái tổ hợp giữa các điểm đánh dấu đa hình như SNPs hoặc vi tế bào, trong đó 1 cM tương đương với một sự kiện tái tổ hợp trong 100 meioses Tại bộ gen người, tỉ lệ tái tổ hợp dao động từ 1 đến 2 cM/Mb Trong các nghiên cứu liên kết, vị trí của gen bệnh được xác định dựa trên mối liên hệ với các vị trí đánh dấu di truyền trên nhiễm sắc thể và phương pháp này đã được áp dụng thành công cho các bệnh đơn gen, chẳng hạn như bệnh Huntington Tuy nhiên, phân tích liên kết cũng tồn tại một số hạn chế.

Các gen bệnh chưa được xác định rõ ràng gây khó khăn trong việc xác định vị trí trên các nhiễm sắc thể Điều này đặc biệt đúng đối với các bệnh phổ biến liên quan đến nhiều gen, khi mà phương pháp phân tích liên kết chưa mang lại hiệu quả rõ rệt.

• Thường có nhiều allele gây bệnh trong một gen, do đó cần một phả hệ đủ lớn để nghiên cứu.

Nghiên cứu liên kết toàn hệ gen (GWAS) sử dụng SNP microarrays với hàng trăm nghìn đến triệu SNP để phân tích sự khác biệt về tần suất biến thể giữa các cá nhân bị ảnh hưởng và không bị ảnh hưởng Cỡ mẫu lớn giúp tăng độ chính xác của các kết quả thống kê Trong thiết kế dựa trên dân số, nghiên cứu thường bao gồm hàng trăm hoặc hàng nghìn trường hợp bệnh và không bệnh để xác định các allele phổ biến có ảnh hưởng nhỏ GWAS đã chứng minh sự tương quan mạnh mẽ, thường xuất hiện ở các vùng xa gen mã hóa protein, có thể là các vùng điều hòa, mặc dù mảng SNP vẫn tạo ra nhiều thách thức trong việc phân tích.

Dóng hàng trình tự

Khái niệm

Dóng hàng trình tự là phương pháp sắp xếp protein, DNA, hoặc RNA để xác định các vùng giống nhau về chức năng, cấu trúc hoặc tiến hóa Các phần tử trong trình tự được dóng hàng, bao gồm nucleotide hoặc amino acid, được biểu diễn trong một ma trận Khoảng trống được chèn vào giữa các phần tử theo tiêu chí tính điểm nhằm tìm ra các chuỗi con chung dài nhất và phù hợp nhất về sinh học Đối với protein, ta có thể xác định các trình tự tương đồng giữa các loài, trong khi đối với DNA và RNA, việc so sánh trình tự cá nhân với trình tự tham chiếu giúp phát hiện các biến thể.

Sự phát triển các thuật toán

Trước năm 2009, đã có nhiều nỗ lực nhằm khớp các trình tự phân kỳ thấp với một bộ gen tham chiếu lớn, sử dụng các công cụ phổ biến như Bowtie, MAQ và SOAP2.

Heng Li và Richard Durbin đã phát triển thuật toán BWA, bao gồm ba thành phần chính: BWA-backtrack, BWA-SW và BWA-MEM, được sử dụng rộng rãi trong phân tích dữ liệu gen BWA-backtrack được tối ưu cho các trình tự Illumina dài tối đa 100bp, trong khi BWA-SW và BWA-MEM hỗ trợ các chuỗi dài từ 70bp đến 1Mbp Trong số này, BWA-MEM là phiên bản mới nhất, được khuyến nghị cho các truy vấn chất lượng cao nhờ vào tốc độ và độ chính xác vượt trội so với BWA-backtrack, đặc biệt là với các trình tự Illumina dài 70-100bp.

Thuật toán dò tìm trình tự tương đồng đã phát triển từ lâu, bắt đầu với bài toán dóng hàng trình tự do Sankoff giới thiệu cùng với thuật toán lập trình động [San75] Tiếp theo, thuật toán Smith-Waterman ra đời, cho phép so sánh các trình tự sinh học bằng cách tìm trình tự chung dài nhất giữa hai chuỗi phân tử [SW81] Để phù hợp với đặc điểm sinh học, mô hình phạt khoảng trống Affine được áp dụng, kết hợp với thuật toán lập trình động [Bel66] trên đồ thị Manhattan ba cấp nhằm tìm trình tự chung dài nhất Năm 1994, Thompson và các cộng sự đã tích hợp những kỹ thuật này vào công cụ CLUSTAL W, giúp tìm các trình tự protein tương đồng với tốc độ nhanh nhờ chiến thuật tham lam [THG94] Sau đó, các công cụ mạnh mẽ hơn như DIALIGN [Mor99] và T-Coffee [NHH00] cũng được phát triển.

5 http://bio-bwa.sourceforge.net/

1.4 Dóng hàng trình tự Đến năm 2004, thuật toán MUSCLE nhanh hơn và hiệu quả hơn hẳn CLUSTAL

Mặc dù đã có nhiều cải tiến trong thuật toán, việc dóng hàng các protein trên toàn bộ chiều dài của chúng vẫn gặp khó khăn Nhiều protein có chức năng tương tự nhưng không chia sẻ trình tự chung đáng kể Để giải quyết vấn đề này, công cụ tìm kiếm dóng hàng địa phương cơ sở (BLAST), được giới thiệu vào năm 1990, đã ra đời BLAST không chỉ giúp tìm kiếm sự tương đồng giữa các protein mà còn cho phép so sánh protein bị đột biến với các protein khác Dựa trên thuật toán tham lam, BLAST hoạt động nhanh chóng và thường được sử dụng để xác định protein dựa trên cơ sở dữ liệu các protein đã biết.

PHÁT TRIỂN CÁC THUẬT TOÁN

Sự phát triển của công nghệ giải trình tự thế hệ tiếp theo đã cho phép thu thập dữ liệu trình tự gen người (SRA) chỉ trong 2 đến 4 giờ, cùng với sự tiến bộ nhanh chóng của các thuật toán, khiến cho việc giải trình tự trở nên nhanh chóng và tiết kiệm chi phí hơn bao giờ hết Chúng tôi áp dụng thuật toán dóng hàng dựa trên chuyển dạng Burrows-Wheeler (BWA) để khớp các trình tự với bộ gen tham chiếu, sau đó sử dụng thuật toán Smith-Waterman (SWA) để dóng hàng lại các Haplotype, nhằm cải thiện độ chính xác trong việc gọi biến thể Quá trình so khớp kết thúc khi xác định được các vị trí nucleotide thay đổi Trong giai đoạn đánh giá ảnh hưởng của các biến thể đến chức năng protein, thuật toán Smith-Waterman lại được áp dụng để tìm kiếm các trình tự tương đồng trong cơ sở dữ liệu protein lớn.

Thuật toán dựa trên chuyển dạng Burrows-Wheeler

Một số cấu trúc dữ liệu

2.1.1.1 Mảng hậu tố (Suffix Arrays)

Mảng hậu tố được giới thiệu lần đầu tiên vào năm 1993 bởi Udi Manber và Gene Myers như một giải pháp hiệu quả về bộ nhớ cho cây hậu tố Để xử lý một chuỗi T chứa các ký tự, cần tạo một mảng lưu trữ các vị trí đầu tiên của các hậu tố trong T dưới dạng số nguyên không âm Để thuận tiện cho việc sắp xếp, ký tự $ được thêm vào cuối chuỗi T, vì khi sắp xếp theo thứ tự bảng chữ cái, ký tự này sẽ đứng ở vị trí đầu tiên.

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler

• Suffix String (SS) là chuỗi con của T bắt đầu từ một vị trí nào đó và kết thúc tại $.

• Suffix Matrix (SM) là một ma trận mà các hàng là các SS được sắp xếp theo thứ tự bảng chữ cái.

Mảng hậu tố (Suffix Arrays - SA) là một cấu trúc dữ liệu quan trọng, chứa thứ tự các ký tự đầu tiên của các chuỗi con SS trong chuỗi T Để xây dựng mảng này, cần phải sắp xếp tất cả các chuỗi con SS theo thứ tự từ điển Hon và các cộng sự đã phát triển một thuật toán hiệu quả cho việc sắp xếp này, với độ phức tạp thời gian O(|T|.log(|T|)) và yêu cầu bộ nhớ tối ưu.

Mảng hậu tố SA có thể được lưu trữ với kích thước O(|T|.log(|Σ|)) bits, trong đó |Σ| là số ký tự duy nhất của chuỗi T không tính ký tự $ Sau khi tạo mảng hậu tố, ta có thể nhanh chóng xác định vị trí của một trình tự mỗi khi nó xuất hiện trong T Các chuỗi con SS sau khi sắp xếp sẽ được nhóm lại ở các vị trí liên tiếp nếu chúng chia sẻ chuỗi con tiền tố giống nhau Ví dụ, trong chuỗi ATCATGATC$, các chuỗi con được nhóm lại trong ma trận SM, với hai chuỗi ATC$ và ATCATGATC$ có chuỗi con chung ATC được đặt gần nhau ở các vị trí 1 và 2 tương ứng với các giá trị 6 và 0 trong mảng hậu tố SA Để tiết kiệm không gian lưu trữ, chúng ta có thể chỉ cần lưu trữ một phần của mảng hậu tố (Partial Suffix Arrays).

Mảng hậu tố của chuỗi ATCATGATC$ được tạo ra bằng cách sắp xếp lại các chuỗi hậu tố theo thứ tự bảng chữ cái, tạo thành mảng SA Mảng này phản ánh thứ tự các ký tự đầu tiên của các chuỗi con SS trong chuỗi gốc Khi thêm các tiền tố tương ứng với các chuỗi con SS vào sau chúng, ta thu được ma trận BWT, trong đó cột cuối cùng của BWTM, được in đậm, thể hiện chuyển dạng Burrows-Wheeler.

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler

2.1.1.2 Ma trận chuyển dạng Burrows-Wheeler

Vào năm 1994, Michael Burrows và David Wheeler đã giới thiệu phương pháp chuyển đổi chuỗi theo khối cho thuật toán nén dữ liệu không mất thông tin, được gọi là chuyển dạng Burrows-Wheeler (BWT) Để thu được BWT của một chuỗi T ban đầu, cần tạo ra một ma trận BWT (BWTM) tương ứng.

Bước đầu tiên là tạo ra tập hợp các chuỗi con SS từ chuỗi T Sau đó, sắp xếp các chuỗi này theo thứ tự bảng chữ cái từ trên xuống dưới để hình thành ma trận SM.

Bước 2 trong quá trình xây dựng ma trận BWTM là thêm các tiền tố tương ứng vào sau các chuỗi SS trên chuỗi T Mỗi cột trong ma trận BWTM đại diện cho một chuyển dạng của chuỗi T, với nhiều ký tự giống nhau được sắp xếp ở các vị trí liền kề.

Ma trận BWT được sinh ra từ chuỗi ATCATGATC$ chứa cột thứ hai là ATTT$AACCG, có ba ký tự T, hai ký tự A, và hai ký tự C liền nhau Chuỗi này có thể được nén lại bằng cách thêm chỉ số trước các ký tự giống nhau, ví dụ: A3T$2A2CG Khi chuyển dạng chuỗi dài như bộ gen người theo cách này, sẽ có nhiều ký tự giống nhau nằm cạnh nhau, tạo điều kiện tốt cho việc nén dữ liệu Tuy nhiên, không phải chuỗi nào cũng có thể giải nén về chuỗi ban đầu Cột cuối cùng của ma trận BWTM được chọn để nén dữ liệu và có thể giải nén thành chuỗi gốc Để giải nén, cần dựa vào cả BWT và cột đầu tiên của BWTM (FC) Mặc dù việc nén dữ liệu có vẻ không hiệu quả vì phải lưu FC, nhưng vấn đề này được giải quyết trong thuật toán dóng hàng khi chỉ cần lưu vị trí của các phần tử đầu tiên thuộc tập hợp {A, T, G, C} trên FC BWTM có hai tính chất quan trọng: tính chất chu trình và tính chất đầu cuối Các dòng của ma trận BWTM được tạo ra từ chuỗi T bằng cách xoay vòng các chuỗi hậu tố và tiền tố theo chu trình.

Khi chọn $ làm hậu tố, nó đứng trước chuỗi tiền tố thuộc T, với ký tự đầu tiên của chuỗi này là ký tự thứ hai của dòng 1 Trong trường hợp chưa quay vòng, $ nằm ở cuối chuỗi T, do đó ký tự cần tìm là A ở đầu dòng 3, mà cũng chính là chuỗi T ban đầu Để tìm ký tự thứ hai của dòng 3, với ký tự A thuộc FC, ta có thể xác định được 3 ký tự A thuộc BWT Việc lựa chọn ký tự tiếp theo là A ở dòng nào cần xem xét tính chất thứ hai, liên quan đến sự xuất hiện lần thứ k của ký tự trong cột đầu và lần xuất hiện thứ k trong cột cuối.

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler ứng với cùng vị trí của ký tự này trong chuỗi T Nói cách khác, các ký tự giống nhau trên FC có thứ tự trước sau giống với thứ tự trước sau của chúng trên

BWT Đặt số thứ tự của các ký tự giống nhau bằng các chỉ số nguyên dương. Đối với chuỗi ATCATGATC$ ta có FC là $1 A 1 A 2 A 3 C 1 C 2 G 1 T 1 T 2 T 3 , BWT là

C 1 G 1 $1 C 2 T 1 T 2 T 3 A 1 A 2 A 3 (Xem hình 2.2) Từ A 2 ở dòng 3, có thể suy ra vị trí tiếp theo là T 2 ở đầu dòng 9 Quá trình này sẽ được lặp lại cho đến khi xác định được chuỗi ban đầu.

Dựa vào tính chất chu trình và mảng hậu tố SA, chúng ta có thể xây dựng chuyển dạng Burrows-Wheeler của chuỗi T với thời gian tuyến tính Ký hiệu cho chuyển dạng này là BW T i.

T i tương ứng là ký tự thứ i của BW T và T, SA i là giá trị tại vị trí thứ i của mạng hậu tố, ta có:

Khi sắp xếp BWT theo thứ tự bảng chữ cái, chúng ta thu được FC Các ký tự giống nhau trong FC được nhóm thành các cụm, và nhờ vào tính chất đầu cuối, chỉ cần lưu vị trí đầu tiên của các ký tự này (FO) để phục vụ cho các thuật toán sau.

2.1.1.3 Ma trận điểm kiểm tra (Checkpoint Arrays)

Sau khi xây dựng chuỗi BWT từ trình tự T, vị trí của một ký tự trong chuỗi BWT có thể được xác định trên chuỗi T Để làm điều này, cần đếm số lần xuất hiện của ký tự trong BWT tại các chỉ số thuộc đoạn [0, n], với n = 0, , |T| − 1 Tuy nhiên, thao tác này tốn nhiều thời gian.

Ma trận điểm kiểm tra (C) được sử dụng để lưu trữ các giá trị đếm, tương tự như mảng hậu tố Để tiết kiệm không gian lưu trữ, chúng ta có thể chỉ lưu một phần của ma trận này Ví dụ, hình 2.3 minh họa ma trận điểm kiểm tra cho chuỗi BWT CG$CTTTAAA Trong trường hợp bộ gen người, nếu cả bốn cột được sử dụng, điều này sẽ tối ưu hóa quá trình lưu trữ dữ liệu.

Thuật toán

2.1.2.1 Thuật toán khớp chính xác

P Ferragina và G Manzini đã đưa ra thuật toán tìm kiếm lùi (backward search) đếm số lần xuất hiện của một mẫu P trên chuỗi T với thời gian O(|P|+occ) [FM05] Trong đó, occ là số lần xuất hiện của mẫu P trong chuỗi T Thuật toán này còn được gọi là FM-index, các ký tự được tìm kiếm ngược từ cuối lên đầu Vị trí của mỗi kí tự này được xác định trên một đoạn thuộc F C Gọi F O(symbol) là thứ tự của vị trí đầu tiên mà kí tự symbol xuất hiện trong F C, CO(symbol, i) là số lần kí tự symbol xuất hiện trong BW T từ vị trí 0 đến vị trí thứ i, với i -1, 0, , |T| - 1 Mỗi lần xét một kí tự trong xâu mẫu P, thứ tự tương ứng với các vị trí trên và dưới của kí tự symbol đang tìm kiếm trên F C được cập nhật như sau: top← F O(symbol) +CO(symbol, top−1) (2.1) bottom← F O(symbol) +CO(symbol, bottom)−1 (2.2)

Các vị trí khớp của mẫu P trên chuỗi T chính bằng giá trị của mảng hậu tố

SA theo thứ tự tương ứng với các vị trí trên F C ở bước cuối cùng Ở đây, hàm

Để tối ưu hóa thuật toán, CO(symbol, i) có thể được thay thế bằng giá trị đếm ký tự symbol trong ma trận điểm kiểm tra Khi sử dụng mảng hậu tố một phần, ta sẽ quay lui các vị trí trong đoạn [top, bottom] cho đến khi tìm thấy các vị trí này trong mảng hậu tố Lúc này, giá trị khớp sẽ là giá trị trong mảng hậu tố cộng thêm số bước quay lui Ví dụ, để khớp mẫu AT C với chuỗi AT CAT GAT C, ta bắt đầu từ cuối chuỗi và xem xét các ký tự C trong đoạn [0, 9], tương ứng với toàn bộ chiều dài của FC.

Để cập nhật đoạn [top, bottom] mới trên FC theo công thức 2.1 và 2.2, cần tính các giá trị F O(C), CO(C,−1) và CO(C,3), lần lượt là 4, 0, và 2 Do đó, đoạn mới của ký tự C trên FC là [4, 5] Tương tự, các đoạn [top, bottom] cho các ký tự T và A được cập nhật thành [7, 8] và [1, 2] Đoạn [1, 2] trên BWT cũng là các vị trí khớp chính xác của mẫu AT C với chuỗi đã cho Cuối cùng, đối chiếu với mảng hậu tố cho thấy các vị trí khớp chính xác của hai chuỗi là 0 và 6.

2.1.2.2 Thuật toán khớp xấp xỉ Đối với thuật toán tìm mẫu khớp chính xác, các kí tự thuộc mẫu P đều phải giống các kí tự trên chuỗi trình tựT theo thứ tự Ngược lại, các kí tự thuộc mẫu khớp xấp xỉ có thể khác các kí tự trên chuỗi đã cho theo trình tự, miễn là số lượng ký tự không giống này nhỏ hơn một ngưỡng khác biệt cho phép (Khác biệt ở đây có thể là một không khớp (mismatch) hoặc một khoảng trống (gap).Khoảng trống với ý nghĩa là các Insert, hoặc các Delete liên tiếp, hay còn gọi

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler

Quá trình tìm kiếm mẫu AT C trong chuỗi AT CAT GAT C cho thấy rằng mẫu khớp chính xác tại vị trí 0 và 6, trong khi đó, mẫu khớp xấp xỉ tại một số vị trí khác.

3 với ngưỡng khác biệt là 1 (III) Mẫu không khớp xấp xỉ vì vượt quá ngưỡng khác biệt cho phép là 1.

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler là Indels) Mặc dù vậy, thuật toán khớp chính xác vẫn được áp dụng cho việc tìm các mẫu khớp xấp xỉ Vẫn với ví dụ hai chuỗi AT C và AT CAT GAT C, ta tiến hành khớp xấp xỉ với ngưỡng khác biệt là 1 Nếu bắt đầu bằng ký tự C trên

Trong bài viết này, chúng ta xem xét hai chuỗi khớp chính xác và nhận thấy rằng chúng thỏa mãn điều kiện đã đề ra Đối với ba ký tự còn lại là G, A và T, ký tự G khác với C, dẫn đến một sự khác biệt Khi cập nhật vị trí của G trên F C, chúng ta tìm được đoạn mới [6, 6] Các ký tự tiếp theo T và A tương ứng với các ký tự thứ hai và thứ nhất của mẫu AT C, do đó số khác biệt vẫn giữ nguyên là 1 Cuối cùng, vị trí khớp xấp xỉ được xác định là 3, trong đó ký tự C của mẫu AT C khác với ký tự G trong chuỗi.

Trong thuật toán CAT GAT, khi xét đến các ký tự T và A, số khác biệt tại bước thứ 3 đã là 2, khiến việc tìm kiếm vị trí khớp xấp xỉ với ngưỡng khác biệt 1 trở nên không khả thi Để tiết kiệm thời gian, ta cần thiết lập một giới hạn dưới cho các khác biệt, mà giới hạn này thường giảm dần từ cuối đến đầu của mẫu P Trong quá trình tìm kiếm lùi, nếu số khác biệt nhỏ hơn giới hạn dưới tại một vị trí nào đó, thuật toán sẽ dừng lại và không tiếp tục tìm kiếm Những giới hạn này được lưu trữ trong một mảng gọi là DA Khả năng mẫu P khớp chính xác với chuỗi T thường thấp hơn khả năng một chuỗi con của P khớp chính xác với T Do đó, việc khớp chính xác các chuỗi con của P sẽ giúp xác định các giới hạn khác biệt dưới Khi bắt đầu khớp từ một ký tự của P giống với ký tự tương ứng trên T, bất kỳ khi nào không kéo dài được chuỗi con khớp chính xác, ta sẽ nhận được một chuỗi con của P khớp với T, trong đó vị trí không kéo dài có thể là một không khớp hoặc một khoảng trống Quá trình xác định DA bắt đầu từ ký tự đầu tiên của P.

P, nếu vị trí tiếp theo không có khác biệt thì số khác biệt tại vị trí này bằng số khác biệt tại vị trí liền trước nó Ngược lại, tại mỗi vị trí xuất hiện khác biệt thì số khác biệt tại đó bằng số khác biệt tại vị trí trước nó cộng thêm một đơn vị. Thuật toán tìm DAđược thiết kế gần giống thuật toán khớp chính xác, điểm khác nhau ở đây là ta tìm kiếm thuận trên mẫu P, và khớp chính xác với chuỗi đảo ngược của T (ký hiệu T 0 ) (Algorithm 1) Lý do chọn chuỗi T 0 là vì DA được thiết kế cho thuật toán tìm kiếm lùi Xét ví dụ chuỗi T và P lần lượt là

T GCGT AGT A và GCAGT, các chuỗi đảo ngược của chúng T 0 và P 0 lần lượt là

Khi áp dụng thuật toán tìm kiếm lùi với chuỗi T 0, mẫu P khớp với chuỗi này tương đương với việc khớp mẫu đảo ngược P 0 với chuỗi T 0 theo chiều nghịch của P 0.

DA được tính toán dựa trên nguyên tắc rằng khi giá trị top lớn hơn bottom, sẽ xuất hiện một khác biệt, có thể là không khớp hoặc khoảng trống Ví dụ, chuỗi con dài nhất của P 0 từ ký tự cuối cùng khớp với T 0 là CG, dẫn đến DA[0] = DA[1] = 0 Chuỗi con này không thể kéo dài thêm.

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler dài đồng nghĩa với việc xuất hiện một không khớp hoặc một khoảng trống, do đó giá trị tiếp theo trong mảng DAđược cộng thêm một đơn vị Hơn nữa, chuỗi con tiếp theo là T GA khớp chính xác với T 0 nên ta có DA[2] = DA[3] = DA[4] = 1. Việc sử dụng mảng DAgiúp tăng tốc độ tính toán cũng như giảm yêu cầu về bộ nhớ Nhìn sang cột cuối cùng, rõ ràng với D[4] = 1 ta không thể khớp chính xác mẫu GCAGT với chuỗi T GCGT AGT A, nói cách khác thuật toán không tính toán các trường hợp với khác biệt bằng 0 ngay tại ký tự cuối cùng T Tương tự, vì D[2] = 1 nên có thể loại bỏ các trường hợp của A để khớp chính xác GCA.

Hình 2.5: Mảng giới hạn khác biệt dưới sử dụng để khớp mẫu GCAGT với chuỗi

Để xác định mảng, chúng ta sử dụng thuật toán tìm kiếm lùi cho mẫu đảo ngược T GACG với chuỗi đảo ngược AT GAT GCGT Kết quả thu được là mảng giới hạn khác biệt dưới {0, 0, 1, 1, 1}.

Input: BW T 0 : Burrows - Wheeler Transform of Reverse String,

CO 0 : Checkpoint Arrays of BWT’.

4: bt ←F O(symbol) +CO 0 (symbol, bt)−1

Giải thuật cho bài toán dóng hàng trình tự dựa trên chuyển dạng Burrows-Wheeler đã được trình bày dưới dạng đệ quy ([LD09]) Trong luận văn này, thuật

2.1 Thuật toán dựa trên chuyển dạng Burrows-Wheeler toán được khử đệ quy và trình bày lại dưới dạng tuần tự để tạo thuận lợi nếu ta cần lập trình song song hoặc đồng thời (Algorithm 2).

Dữ liệu đầu vào bao gồm BW T, mảng giới hạn khác biệt dưới DA, mảng hậu tố một phần PSA, ngưỡng khác biệt W, mẫu P AT, vị trí xuất hiện đầu tiên của các ký tự F O, và ma trận điểm kiểm tra CO.

• Khởi tạo mảng cập nhật thông tin với đoạn đầu tiên [1, |BW T|] chứa toàn bộ chiều dài T.

• Dòng 1: Khi mảng cập nhật thông tin khác rỗng thuật toán được chạy lặp lại.

• Dòng 2, 3: Lấy thông tin của đoạn [top, bottom] đầu tiên từ mảng cập nhật thông tin, đồng thời xóa đoạn này khỏi mảng cập nhật thông tin.

• Dòng 4: Tập hợp được đem khớp gồm bốn ký tự {A, T, G, C}.

• Dòng 5, 6: Nếu chiều dài chuỗi con của mẫu khác 0 ta tiến hành khớp chuỗi con này với chuỗi trình tự từ ký tự cuối cùng của chuỗi con.

• Dòng 7, 8: Duyệt qua các ký tự trong tập hợp được đem khớp, thuật toán sẽ tìm các đoạn [top, bottom] mới tương ứng với mỗi ký tự này.

Thuật toán Smith-Waterman

Thực nghiệm thuật toán

Tiền xử lý dữ liệu