Qua 2 kỳ trước, tôi giới thiệu vaccine Covid và lý thuyết đồ thị. Vậy hai chuyện này liên quan gì tới nhau? Liên quan ở chỗ làm gene sequencing, chép ra chuỗi nucleotides trong RNA của con virus.
RNA là một chuỗi dài, vài chục ngàn nucleotides (gồm A, C, G, hay U). Có RNA đi từ điểm đầu tới điểm cuối. Có RNA là vòng tròn nối lại, không có điểm đầu hay điểm cuối. Các con coronavirus chẳng hạn có RNA là vòng tròn, dài từ 25 tới 30 ngàn nucleotides.
Phương pháp hiện nay để làm gene sequencing, tức là viết ra mấy chục ngàn nucleotides đó theo đúng thứ tự, là lấy một mẫu virus, lấy hoá chất phá bể chúng ra, sau đó dùng chất màu (fluorescent stain) để đọc các nucleotides trên từng miếng bể đó, rồi ghép lại với nhau.
Trên mạng, TS Phillip Compeau đại học Carnegie Mellon University so sánh việc làm gene sequencing giống như có một sấp nhiều bản của cùng cuốn sách (tương đương mẫu virus có nhiều con trong đó), bỏ vô máy cắt vụn ra, rồi ghép những mảnh vụn đó lại thành đủ một cuốn. Các bạn có thể tưởng tượng chuyện này khó cỡ nào. Không thể làm được nếu không có một phương pháp toán học rõ ràng.
Mỗi lần đọc một đoạn RNA, tiếng Anh gọi là một “read.” Như những mảnh vụn khi cắt xén một sấp cùng quyển sách, những read này có thể đến từ các con virus khác nhau, chúng có thể trùng lấp, và không có cách nào biết mảnh này đến từ chỗ nào trên con virus.
Nhưng ngược lại, nếu gom đủ số đông các mảnh vụn, các read, mình có thể tin tưởng là đâu đó trong đống vụn đó, nếu ghép đúng cách, kể cả trùng lấp, sẽ có đủ một con virus. Để làm gene sequencing cho con SARS-CoV-2 chẳng hạn, các nhà khoa học Trung Quốc đã sử dụng đến hơn 80,000,000 reads.
Về toán học, chính sự trùng lấp giữa các mảnh vụn giúp giải bài toán này. Mấu chốt là đoạn cuối của một mảnh read phải trùng với đoạn đầu của mảnh read khác. Thí dụ có một read kết thúc bằng GU. Vậy tiếp theo nó không thể là một read bắt đầu bằng UG and CA được, mà phải bắt đầu bằng GU.
Nhưng có biết bao nhiêu mảnh bắt đầu bằng GU, lựa cái nào bây giờ?
Để tạm vô hết, rồi tính tiếp cho đủ 80,000,000 reads. Một số chuỗi sẽ không đi tới đâu hết, nhưng sẽ có chuỗi bao đủ 80,000,000 reads. Đó là đáp số đúng. (Trên thực tế thì có thể có nhiều đáp số bao đủ 80,000,000 reads, nhưng các nhà sinh vật học có thể dùng kiến thức có sẵn về loài coronavirus để loại bỏ các đáp số vô lý.)
Phương pháp sử dụng là lý thuyết đồ thị. Giả sử mình biết RNA của con virus là vòng tròn, với các mảnh vụn như sau:
AGU
GUG
CAG
GUC
UGU
UCA
Phương pháp làm gene sequencing là lập một mô hình đồ thị, trong đó mỗi read là một cạnh. (Cái này quan trọng: Mỗi read là một cạnh.) Rồi đi mình một đường vòng bao hết tất cả các read.
Mà bao hết tất cả các read, tức là bao hết tất cả các cạnh. Đường vòng trong đồ thị bao hết tất cả các cạnh là một chu trình Euler, mà chu trình Euler thì đã có cách tìm nhanh từ lâu rồi, gọi là thuật toán Hierholzer, theo tên nhà toán học Đức Carl Hierholzer.
Vậy phương pháp ghép các mảnh vụn trên như sau.
Bước 1, liệt kê hết các đoạn đầu và đoạn cuối của tất cả các read. AGU có đoạn đầu AG và đoạn cuối GU. CAG có đoạn đầu CA và đoạn cuối AG (đã viết ra rồi nên không viết nữa.
Bước 2. Mỗi read, vẽ một mũi tên đi từ đoạn đầu tới đoạn cuối của read đó. Để biếu hiện AGU, vẽ mũi tên từ AG tới GU.
Kết quả là một đồ thị trong đó mỗi cạnh có hướng, tiếng Anh gọi là directed graph hay digraph. Trong digraph, muốn đi đâu phải đi đúng chiều mũi tên, không được đi ngược lại. Kiểu như đồ thị đường một chiều vậy.
Bước 3, đi tìm một chu trình Euler. Tức là tìm cách vẽ đồ thị này, theo đúng hướng mũi tên, mà không nhấc cây viết khỏi tờ giấy và không đồ lên cùng một cạnh hai lần.
Cái hay của lý thuyết đồ thị, là từ năm 1893 đã có thuật toán của Carl Hierholzer để tìm chu trình Euler nhanh chóng. Vì vậy, 80,000,000 mảnh read có thể là một con số rất lớn, nhưng với thuật toán Hierholzer và mấy điện toán hiện đại, bài này có thể giải trong vài giờ.
Từ chu trình Euler, đọc ra các read theo thứ tự và tính cả trùng lấp. Cạnh đầu tiên là AGU, rồi tới GUG, gộp lại thành AGUG (GU trùng lấp). Tiếp tục tới cuối cùng thì ra đáp số là: AGUGUCA. Rồi lập lại vì RNA vòng tròn: AGUGUCAGUGUCAGUGUC....
Và đó là phương pháp dùng lý thuyết đồ thị của Euler để giải bài toán gene sequencing, từ đó có được ngành y tế hiện đại và vaccine cho Covid. Mai này chích ngừa xong, có miễn nhiễm cộng đồng, hãy nhớ cám ơn Euler!
Mời quý vị tham khảo thêm trong video này:
