Đường dẫn truy cập

Lý thuyết đồ thị và vaccine Covid (kỳ kết)


Những thứ này có liên quan tới nhau. (Hình: Vũ Quí Hạo Nhiên, Wikimedia/Roland1952/CC BY-SA 3.0, CDC, Jakob Emanuel Handmann/Kunstmuseum Basel)

Qua 2 kỳ trước, tôi giới thiệu vaccine Covidlý 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.

Gene sequencing giống như cắt vụn một sấp nhiều bản của cùng cuốn sách rồi ghép lại cho đủ một cuốn. (Hình: Vũ Quí Hạo Nhiên)
Gene sequencing giống như cắt vụn một sấp nhiều bản của cùng cuốn sách rồi ghép lại cho đủ một cuốn. (Hình: Vũ Quí Hạo Nhiên)

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.

Đọc thật nhiều mảnh vụn để, tính cả trùng lấp, đủ để bao nguyên con virus. (Hình: Vũ Quí Hạo Nhiên trên nền Wikimedia/Roland1952/CC BY-SA 3.0)
Đọc thật nhiều mảnh vụn để, tính cả trùng lấp, đủ để bao nguyên con virus. (Hình: Vũ Quí Hạo Nhiên trên nền Wikimedia/Roland1952/CC BY-SA 3.0)

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.

Liệt kê hết các đoạn đầu và đoạn cuối của tất cả các read. (Hình: Vũ Quí Hạo Nhiên)
Liệt kê hết các đoạn đầu và đoạn cuối của tất cả các read. (Hình: Vũ Quí Hạo Nhiên)

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.

Mỗi mũi tên biểu hiện một read. Mũi tên từ AG tới GU biểu hiện AGU. (Hình: Vũ Quí Hạo Nhiên)
Mỗi mũi tên biểu hiện một read. Mũi tên từ AG tới GU biểu hiện AGU. (Hình: Vũ Quí Hạo Nhiên)

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ờ.

Giải chu trình Euler. (Hình: Vũ Quí Hạo Nhiên)
Giải chu trình Euler. (Hình: Vũ Quí Hạo Nhiên)

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:

  • 16x9 Image

    Vũ Quí Hạo Nhiên

    Vũ Quí Hạo Nhiên là giáo sư Toán đại học cộng đồng Coastline College ở Quận Cam, California, với hơn 10 năm dạy các đại học cộng đồng trong vùng như Santa Ana, Cypress, Santiago Canyon, và Orange Coast College. Ngoài ra, ông cũng từng làm báo Việt ngữ trong hơn 10 năm, với chức vụ Tổng thư ký Toà soạn và Phụ tá chủ bút cũng như cộng tác viên cho nhiều báo, đài phát thanh tại Mỹ và các nước khác.

    Ông là giám đốc chương trình luyện thi SAT cho một trung tâm tại Garden Grove, là giám khảo chấm thi AP Statistics cho College Board / ETS, và là cộng tác viên viết sách giáo khoa Toán cho nhà xuất bản Hawkes Learning.

    Trong blog này Vũ Quí Hạo Nhiên viết về những chuyện ông biết: Toán, giáo dục, lịch sử California. Ông hy vọng độc giả sẽ thảo luận, phê bình, kể cả chê trách, cũng như cho ý kiến đề nghị đề tài.

    Các bài viết của tác giả là blog cá nhân và được đăng tải với sự đồng ý của đài VOA nhưng không phản ánh quan điểm chính thức của chính phủ Hoa Kỳ.

Diễn đàn Facebook

VOA có ứng dụng mới

Xem tin tức VOA trực tiếp trên điện thoại và máy tính bảng! Ứng dụng tin tức miễn phí của VOA Tiếng Việt liên tục cập nhật thông tin trung thực, đa chiều về tình hình Việt Nam và thế giới; đặc biệt có thêm chức năng vượt tường lửa, phá chặn website.

Hãy tải ngay ứng dụng VOA Tiếng Việt trên iTunes StoreGoogle Play!

Lưu ý: Ứng dụng cũ của VOA đã bị xóa vào ngày 15/1/2020.

XS
SM
MD
LG