Bỏ qua tới nội dung chính

Trước khi có thuật toán cho sinh học

Thuật toán cho sinh học tính toán: khi sinh học thành một ngành dữ liệu

Những thuật toán biến sinh học thành ngành dữ liệu: so khớp trình tự, mẹo tìm nhanh của BLAST, ghép bộ gen bằng đồ thị, cây phát sinh loài — và học từ đâu.

Ban biên tập OpenER

Cập nhật 18/11/2026 · 19 phút đọc · CC BY 4.0

Hãy hình dung bạn làm ở một phòng xét nghiệm thủy sản. Tôm ở một ao nuôi miền Tây chết hàng loạt; từ mẫu bệnh, người ta đọc được một đoạn DNA dài vài trăm chữ cái của một con vi khuẩn lạ. Nó là vi khuẩn gì? Bạn dán đoạn ấy vào ô tìm kiếm của BLAST trên trang của Trung tâm Thông tin Công nghệ sinh học Quốc gia Mỹ (NCBI) rồi bấm nút. Vài giây sau, màn hình liệt kê những trình tự giống nó nhất trong một kho gen của hàng trăm nghìn loài, mỗi dòng kèm một con số cho biết sự giống nhau ấy có thể chỉ là tình cờ hay không.

Vài giây đó đứng trên ba ý tưởng: cách so khớp bằng quy hoạch động (dynamic programming) có từ năm 1970, một mẹo tìm nhanh bằng "hạt giống" và một công thức thống kê, cùng từ năm 1990. Thuật toán cho sinh học tính toán (algorithms for computational biology) — phần thuật toán của tin sinh học (bioinformatics) — học những ý tưởng như thế: biến câu hỏi sinh học thành bài toán trên chuỗi ký tự, đồ thị và cây, rồi giải cho đủ nhanh với lượng dữ liệu không ai đọc hết bằng mắt.

Bài Sinh học đã kể DNA là chuỗi bốn chữ cái A, C, G, T, gen được dịch thành protein ra sao, và chuyện Dự án Bộ gen người. Bài này đi tiếp từ đó: có chuỗi rồi, làm gì với nó?

Trước khi có thuật toán cho sinh học

Năm 1955, Frederick Sanger đọc xong trình tự axit amin của insulin, protein đầu tiên được đọc trọn. Mười năm sau đó, trình tự mới xuất hiện rải rác trong các tạp chí; muốn so hai protein, người ta thường đặt hai bản in cạnh nhau và dò bằng mắt. Rồi từng bước:

  1. Kho dữ liệu đầu tiên — năm 1965, Margaret Dayhoff, một nhà hóa học sớm dùng máy tính, xuất bản Atlas of Protein Sequence and Structure: 65 trình tự protein đã biết lúc đó, lưu trên bìa đục lỗ, mỗi axit amin một chữ cái. Atlas dày lên qua từng năm và mở đường cho các kho như GenBank (1982). Năm 1978, nhóm của bà làm ra bảng điểm PAM cho biết axit amin nào hay thay cho axit amin nào.
  2. Cây họ hàng từ trình tự — năm 1967, Walter Fitch và Emanuel Margoliash dựng cây tiến hóa của 20 loài, từ nấm men tới người, chỉ dựa trên trình tự một protein là cytochrome c.
  3. So khớp bằng quy hoạch động — năm 1970, Saul Needleman và Christian Wunsch công bố cách xếp thẳng hàng hai protein cho tổng điểm cao nhất bằng một bảng quy hoạch động. Năm 1981, Temple Smith và Michael Waterman sửa nó để tìm đoạn giống nhau nhất nằm ở bất kỳ đâu.
  4. Tìm nhanh trong kho lớn — khi kho phình ra, quy hoạch động với từng trình tự trở nên quá chậm. FASTA (David Lipman và William Pearson, từ 1985) rồi BLAST (Stephen Altschul và cộng sự, 1990) chấp nhận bỏ sót đôi chút để nhanh hơn nhiều lần. Bài báo BLAST năm 1990 đứng thứ 12 trong danh sách 100 bài báo khoa học được trích dẫn nhiều nhất mà tạp chí Nature lập năm 2014.
  5. Ghép bộ gen từ mảnh vụn — máy chỉ đọc được những đoạn ngắn, nên người ta băm DNA thành rất nhiều mảnh ngẫu nhiên, đọc từng mảnh rồi để máy tính ghép lại: giải trình tự kiểu shotgun (shotgun sequencing). Năm 1995, bộ gen vi khuẩn Haemophilus influenzae được ghép theo cách này — bộ gen đầu tiên của một sinh vật sống tự do. Cuộc đua giữa công ty Celera và dự án công khai Bộ gen người quanh năm 2000 cũng là cuộc đua giữa hai cách băm và ghép.
  6. Dữ liệu thế hệ mới — từ khoảng 2005, máy giải trình tự thế hệ mới (next-generation sequencing) ra đời; vài năm sau, một lần chạy đã cho hàng trăm triệu đoạn đọc (read), mỗi đoạn chỉ vài chục tới vài trăm chữ cái. Các chương trình ghép chuyển sang đồ thị de Bruijn (de Bruijn graph), theo ý tưởng của Ramana Idury và Michael Waterman (1995), Pavel Pevzner và cộng sự (2001).
  7. Hình dạng protein — năm 2020, AlphaFold 2 giải gần trọn bài toán đoán hình dạng protein từ trình tự, câu hỏi treo suốt nửa thế kỷ (bài Sinh học đã kể).

Đặt cạnh nhau:

Chưa có thuật toán
Có thuật toán
Hai protein có họ hàng không?
Đặt hai bản in cạnh nhau, dò bằng mắt
Cách xếp tốt nhất, kèm khả năng giống nhau do tình cờ
Đoạn gen lạ là của loài gì?
Hỏi chuyên gia, tra sách
BLAST qua kho của hàng trăm nghìn loài trong vài giây
Đọc một bộ gen
Đọc nối từng đoạn theo thứ tự, mất nhiều năm
Đọc hàng triệu mảnh cùng lúc, ghép bằng đồ thị
Cây họ hàng giữa các loài
Dựa vào hình thái, hóa thạch
Dựng từ trình tự, đo được độ tin cậy
Một ổ dịch
Đếm ca bệnh
Đọc gen virus, biết ca nào gần ca nào

Nhưng thuật toán chỉ so được với thứ đã có trong kho. Khi Dự án Bộ gen Trái Đất (Earth BioGenome Project) ra đời năm 2018 với mục tiêu đọc bộ gen của khoảng 1,5 triệu loài sinh vật nhân thực đã được đặt tên, mới chưa tới 0,2% số loài ấy có bộ gen được giải. Với phần lớn cây cỏ, côn trùng, ếch nhái trong rừng Việt Nam, BLAST chỉ tìm ra họ hàng gần nhất đã có trong kho — nhiều khi là họ hàng rất xa.

Môn này trả lời câu hỏi gì

Môn này trả lời: làm sao rút ra câu trả lời sinh học từ những chuỗi ký tự rất dài, rất nhiều và đầy lỗi đọc — cho đúng, cho nhanh, và biết mình chắc tới đâu? Cụ thể là năm câu hỏi:

  • Hai trình tự giống nhau tới đâu, chỗ nào ứng với chỗ nào? (so khớp)
  • Một đoạn ngắn nằm ở đâu trong một kho hàng tỷ chữ cái? (chỉ mục và tìm kiếm)
  • Từ hàng triệu mảnh vụn, bộ gen nguyên vẹn trông thế nào? (ghép bộ gen)
  • Các loài, các mẫu virus có họ hàng với nhau ra sao? (phát sinh loài)
  • Kết quả nào là thật, kết quả nào chỉ là trùng hợp? (thống kê)

Với người học khoa học máy tính, đây là nơi quy hoạch động, bảng băm, đồ thị và thống kê gặp dữ liệu thật, đủ lớn và đủ bẩn để mọi lựa chọn đều có giá — và y học, nông nghiệp, dịch tễ đang cần những người như thế.

Năm ý tưởng cốt lõi

1. So khớp trình tự: quy hoạch động với bảng điểm của sinh học

So khớp trình tự (sequence alignment) là việc nền nhất của môn. Hai gen cùng một gốc tổ tiên trôi dạt khác nhau qua hàng triệu năm: chỗ này một chữ bị thay, chỗ kia một chữ mất đi hay chèn thêm. Muốn so chúng, ta xếp thẳng hàng (align) hai chuỗi, chèn dấu "-" vào chỗ một bên thiếu chữ, sao cho tổng điểm cao nhất. Số cách chèn tăng theo hàm mũ, nhưng quy hoạch động — khuôn đã gặp ở bài Thiết kế và phân tích thuật toán — giải gọn: điểm tốt nhất khi xếp hai đoạn đầu chỉ có thể đến từ ba ô liền trước trong bảng.

Phần riêng của sinh học nằm ở bảng điểm. Đột biến không xảy ra đều nhau: A và G cùng nhóm purin, C và T cùng nhóm pyrimidin, và đổi trong cùng nhóm (transition) hay gặp hơn đổi sang nhóm khác (transversion). Nên phạt nhẹ hơn:

python
CUNG_NHOM = {("A", "G"), ("G", "A"), ("C", "T"), ("T", "C")}   # đổi cùng nhóm: hay gặp hơn

def diem(x, y):
    if x == y:
        return 2                                  # giống nhau
    return -1 if (x, y) in CUNG_NHOM else -2      # khác nhau: phạt nhẹ hay phạt nặng

TRONG = -3                                        # phạt mỗi chữ đứng đối diện khoảng trống

def can_chinh(a, b):
    n, m = len(a), len(b)
    F = [[0] * (m + 1) for _ in range(n + 1)]     # F[i][j]: điểm tốt nhất khi xếp a[:i] với b[:j]
    for i in range(n + 1):
        F[i][0] = i * TRONG
    for j in range(m + 1):
        F[0][j] = j * TRONG
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            F[i][j] = max(F[i - 1][j - 1] + diem(a[i - 1], b[j - 1]),  # hai chữ đối diện nhau
                          F[i - 1][j] + TRONG,                          # chữ của a gặp "-"
                          F[i][j - 1] + TRONG)                          # chữ của b gặp "-"
    tren, duoi, i, j = "", "", n, m               # lần ngược từ góc dưới phải về góc trên trái
    while i > 0 or j > 0:
        if i and j and F[i][j] == F[i - 1][j - 1] + diem(a[i - 1], b[j - 1]):
            tren, duoi, i, j = a[i - 1] + tren, b[j - 1] + duoi, i - 1, j - 1
        elif i and F[i][j] == F[i - 1][j] + TRONG:
            tren, duoi, i = a[i - 1] + tren, "-" + duoi, i - 1
        else:
            tren, duoi, j = "-" + tren, b[j - 1] + duoi, j - 1
    return F[n][m], tren, duoi

diem_so, tren, duoi = can_chinh("GCTAGCTTACGA", "GCAGCTTGCGA")
print("điểm", diem_so)
print(tren)
print("".join("|" if x == y else ":" if (x, y) in CUNG_NHOM else " " for x, y in zip(tren, duoi)))
print(duoi)

Kết quả:

text
điểm 16
GCTAGCTTACGA
|| |||||:|||
GC-AGCTTGCGA

Dấu | là giống nhau, : là một lần đổi cùng nhóm (A với G), - là chỗ một chữ bị mất. Nếu mọi sai khác đều phạt như nhau, ta có khoảng cách sửa (edit distance) quen thuộc của trình sửa lỗi chính tả; sinh học chỉ thay bảng giá. Với protein, bảng giá là ma trận 20 × 20 rút ra từ những cặp protein họ hàng thật — PAM của Dayhoff, rồi BLOSUM62 (1992), bảng mặc định khi so protein bằng BLAST đến nay.

Đổi vài chỗ — điểm không bao giờ xuống dưới 0, lần ngược từ ô cao nhất thay vì ô góc — ta có thuật toán Smith–Waterman tìm đoạn giống nhau nhất. Thời gian chạy tỷ lệ với tích hai độ dài: hai gen một nghìn chữ là một triệu ô, tức thì. Nhưng so một đoạn với cả bộ gen người 3 tỷ chữ, cho hàng trăm triệu đoạn đọc, thì không.

2. Tìm nhanh bằng hạt giống: mẹo của BLAST

Ý của BLAST: hai đoạn có họ hàng đủ gần thì gần như chắc chắn chung ít nhất một từ ngắn giống hệt — gọi là hạt giống (seed), hay k-mer khi dài k chữ. Vậy đừng so với mọi vị trí, chỉ so kỹ ở những chỗ hai bên chung hạt. Cách dễ thấy nhất: lập sẵn một chỉ mục (index) ghi mỗi từ dài k chữ xuất hiện ở đâu trong kho, tra các từ của đoạn cần tìm, rồi so kỹ ở vài chỗ trúng nhiều nhất. Chỉ mục ấy là một bảng băm — dict của Python — như bài Cấu trúc dữ liệu và giải thuật giải thích:

python
import random
from collections import Counter, defaultdict

random.seed(2026)
bo_gen = "".join(random.choices("ACGT", k=1_000_000))   # "bộ gen" giả: 1 triệu chữ ngẫu nhiên

K = 11
chi_muc = defaultdict(list)                    # mỗi từ dài K chữ -> các vị trí nó xuất hiện
for i in range(len(bo_gen) - K + 1):
    chi_muc[bo_gen[i:i + K]].append(i)

doan_doc = list(bo_gen[654_321:654_321 + 60])  # một đoạn đọc 60 chữ lấy từ vị trí 654321...
for p in (10, 30, 45):                         # ...có 3 chữ bị máy đọc sai
    doan_doc[p] = "C" if doan_doc[p] != "C" else "G"
doan_doc = "".join(doan_doc)

phieu = Counter()
for j in range(len(doan_doc) - K + 1):         # mỗi hạt K chữ của đoạn đọc
    for i in chi_muc.get(doan_doc[j:j + K], []):
        phieu[i - j] += 1                      # bầu cho vị trí bắt đầu i - j
print(len(phieu), "vị trí ứng viên")
print(phieu.most_common(3))

Kết quả:

text
10 vị trí ứng viên
[(654321, 17), (73467, 3), (125300, 2)]

Đoạn đọc có 50 hạt dài 11 chữ. Hạt nào chứa chữ đọc sai thì trượt, nhưng vẫn còn 17 hạt cùng chỉ về vị trí 654321. Vài hạt trúng ngẫu nhiên ở chỗ khác — trong một triệu chữ cái, từ 11 chữ lặp lại là chuyện thường — nhưng mỗi chỗ chỉ được 1–3 phiếu. Thay vì so với cả triệu vị trí, giờ chỉ cần so kỹ ở 10 chỗ. Chế độ blastn của BLAST cũng dùng hạt dài 11 chữ cái, chỉ tra theo chiều ngược lại: lập bảng cho các từ của đoạn cần tìm rồi quét qua kho.

Cái giá: hai đoạn họ hàng xa, không còn chung từ 11 chữ nào, sẽ bị bỏ sót. BLAST là một heuristic, đổi một ít độ nhạy lấy rất nhiều tốc độ; hạt càng ngắn càng nhạy nhưng càng nhiều trúng giả. Khi phải dóng hàng trăm triệu đoạn đọc vào bộ gen tham chiếu (reference genome) của người, các chương trình như BWA và Bowtie (2009) còn nén chỉ mục bằng biến đổi Burrows–Wheeler (Burrows–Wheeler transform), để chỉ mục của cả bộ gen vừa bộ nhớ một máy tính để bàn.

3. Ghép bộ gen: một bài toán đồ thị

Máy đọc trả về những đoạn ngắn lộn xộn, không kèm vị trí. Cách tự nhiên là nối những đoạn gối lên nhau; nhưng tìm cách đi qua mỗi đoạn đúng một lần là bài toán đường đi Hamilton (Hamiltonian path), thuộc nhóm NP-đầy đủ mà bài Thiết kế và phân tích thuật toán nói là chưa ai biết cách giải nhanh.

Đồ thị de Bruijn lật ngược góc nhìn. Cắt mọi đoạn đọc thành các từ dài k; mỗi từ là một cạnh nối k − 1 chữ đầu với k − 1 chữ cuối của nó. Ghép bộ gen giờ là đi qua mỗi cạnh đúng một lần: đường đi Euler (Eulerian path), bài toán Euler giải ở Königsberg năm 1736 (bài Toán rời rạc, logic và chứng minh có kể), giải được trong thời gian tuyến tính:

python
from collections import defaultdict

def ghep(cac_doan, k):
    """Ghép bộ gen từ các đoạn đọc bằng đồ thị de Bruijn và đường đi Euler."""
    tu = {d[i:i + k] for d in cac_doan for i in range(len(d) - k + 1)}  # mọi từ dài k, bỏ trùng
    di_toi, chenh = defaultdict(list), defaultdict(int)
    for t in sorted(tu):              # mỗi từ là một cạnh: từ k-1 chữ đầu sang k-1 chữ cuối
        di_toi[t[:-1]].append(t[1:])
        chenh[t[:-1]] += 1            # số cạnh ra trừ số cạnh vào
        chenh[t[1:]] -= 1
    dau = next(u for u in di_toi if chenh[u] == 1)   # đỉnh xuất phát: ra nhiều hơn vào
    chong, duong = [dau], []
    while chong:                      # thuật toán Hierholzer: đi qua mỗi cạnh đúng một lần
        u = chong[-1]
        if di_toi[u]:
            chong.append(di_toi[u].pop())
        else:
            duong.append(chong.pop())
    duong.reverse()
    return duong[0] + "".join(dinh[-1] for dinh in duong[1:])

doan_doc = ["ATTTGACATC", "GTGTCATAAA", "TGACATCTAT",   # sáu đoạn đọc dài 10 chữ,
            "TAAACCATTT", "TCATAAACCA", "ACCATTTGAC"]   # thứ tự lộn xộn như máy trả về
print(ghep(doan_doc, 4))
print(ghep(doan_doc, 6))
# bộ gen thật: GTGTCATAAACCATTTGACATCTAT

Kết quả:

text
GTGTCATTTGACATAAACCATCTAT
GTGTCATAAACCATTTGACATCTAT

Với k = 6, đồ thị cho đúng bộ gen. Với k = 4, kết quả cũng dài 25 chữ, đi qua đủ mọi từ 4 chữ của các đoạn đọc — nhưng sai: hai khúc AAAC và TTGA đổi chỗ cho nhau. Thủ phạm là đoạn CAT lặp ba lần: đỉnh chỉ dài 3 chữ nên đồ thị không phân biệt được ba lần ấy, và có hai cách đi qua mọi cạnh đều hợp lệ. Muốn gỡ, từ và đoạn đọc phải dài hơn đoạn lặp. Đó là lý do bản bộ gen người năm 2003 còn trống ở những vùng lặp dài, và bản đầy đủ năm 2022 cần máy đọc được những đoạn dài hàng chục nghìn chữ cái trở lên. Chương trình ghép thật còn phải xử lý lỗi đọc, hai mạch DNA và độ phủ không đều, nhưng xương sống vẫn là đồ thị này.

4. Cây phát sinh loài: dựng cây họ hàng từ khoảng cách

Có trình tự của nhiều loài, hay nhiều mẫu virus, ta muốn biết ai gần ai: cây phát sinh loài (phylogenetic tree). Cách đơn giản nhất là UPGMA (Robert Sokal và Charles Michener, 1958): ghép hai cụm gần nhau nhất, coi cụm mới như một mẫu, tính lại khoảng cách bằng trung bình, lặp lại. Thử với bốn mẫu virus giả định lấy từ bốn ca bệnh:

python
# số vị trí khác nhau giữa bộ gen virus của bốn ca bệnh (số tự đặt để minh họa)
kc = {("A", "B"): 2, ("A", "C"): 7, ("A", "D"): 12,
      ("B", "C"): 7, ("B", "D"): 12, ("C", "D"): 9}
kc = {frozenset(cap): d for cap, d in kc.items()}
co = {"A": 1, "B": 1, "C": 1, "D": 1}           # mỗi cụm gồm bao nhiêu mẫu

while len(co) > 1:
    cap = min(kc, key=kc.get)                    # hai cụm gần nhau nhất
    x, y = sorted(cap)
    print(f"ghép {x} với {y}, khoảng cách {kc[cap]:.1f}")
    moi = f"({x},{y})"
    for z in co:
        if z not in cap:                         # khoảng cách tới cụm mới: trung bình theo số mẫu
            kc[frozenset((moi, z))] = (co[x] * kc[frozenset((x, z))]
                                       + co[y] * kc[frozenset((y, z))]) / (co[x] + co[y])
    co[moi] = co.pop(x) + co.pop(y)
    kc = {c: d for c, d in kc.items() if not c & cap}

print(next(iter(co)))

Kết quả:

text
ghép A với B, khoảng cách 2.0
ghép (A,B) với C, khoảng cách 7.0
ghép ((A,B),C) với D, khoảng cách 11.0
(((A,B),C),D)

Dòng cuối là cây viết bằng ngoặc lồng nhau: A và B gần như giống hệt, nhiều khả năng cùng một chuỗi lây; C chung nhánh nhưng xa hơn; D tách ra từ sớm, có thể do virus vào từ nơi khác. Cây chỉ nói ai gần ai, không nói ai lây cho ai. UPGMA còn giả định mọi nhánh tích lũy đột biến cùng một tốc độ — đồng hồ phân tử (molecular clock); khi giả định ấy sai, các phương pháp như nối láng giềng (neighbor joining, 1987) hay hợp lý cực đại (maximum likelihood) cho cây đáng tin hơn.

5. Thống kê: giống vì họ hàng, hay vì tình cờ?

Thuật toán so khớp luôn trả về một cách xếp tốt nhất, kể cả cho hai chuỗi chẳng liên quan. Câu hỏi thật là: điểm này có cao hơn mức tình cờ cũng đạt được không? Cách thử trực tiếp: xáo trộn (shuffle) một chuỗi (giữ nguyên số chữ A, C, G, T nhưng phá mọi họ hàng), so lại nhiều lần, xem điểm thật đứng đâu giữa đám điểm "tình cờ":

python
import random

def diem_cuc_bo(a, b):
    """Điểm Smith–Waterman: giống +1, khác -1, khoảng trống -2; không bao giờ dưới 0."""
    truoc, tot_nhat = [0] * (len(b) + 1), 0
    for x in a:
        nay = [0]
        for j, y in enumerate(b):
            s = max(0, truoc[j] + (1 if x == y else -1), truoc[j + 1] - 2, nay[j] - 2)
            nay.append(s)
            tot_nhat = max(tot_nhat, s)
        truoc = nay
    return tot_nhat

def dot_bien(s, ty_le):                      # đổi ngẫu nhiên một tỷ lệ chữ cái sang chữ khác
    return "".join(random.choice("ACGT".replace(c, "")) if random.random() < ty_le else c
                   for c in s)

random.seed(7)
goc = "".join(random.choices("ACGT", k=100))
for ten, ty_le in [("họ hàng gần", 0.2), ("họ hàng xa", 0.5)]:
    b = dot_bien(goc, ty_le)
    that = diem_cuc_bo(goc, b)
    tron = [diem_cuc_bo(goc, "".join(random.sample(b, len(b)))) for _ in range(200)]
    vuot = sum(s >= that for s in tron)
    print(f"{ten}: điểm {that}; 200 lần xáo trộn: cao nhất {max(tron)}, "
          f"{vuot} lần đạt từ {that} trở lên")

Kết quả:

text
họ hàng gần: điểm 63; 200 lần xáo trộn: cao nhất 13, 0 lần đạt từ 63 trở lên
họ hàng xa: điểm 10; 200 lần xáo trộn: cao nhất 14, 30 lần đạt từ 10 trở lên

Cặp họ hàng gần (đổi 20% chữ cái) vượt xa mọi lần xáo trộn: khả năng chỉ do tình cờ dưới 1/200. Cặp họ hàng xa (đổi một nửa) thì cứ chừng bảy lần xáo trộn lại có một lần điểm cao bằng — không phân biệt được với tình cờ, dù chúng thật sự cùng gốc. Đổi random.seed thì có lần cặp này nổi lên, có lần chìm hẳn: ở vùng mờ ấy, kết luận "có họ hàng" hay "không" đều dễ sai.

BLAST không xáo trộn hàng trăm lần cho mỗi kết quả. Năm 1990, Samuel Karlin và Stephen Altschul chỉ ra điểm so khớp cục bộ tốt nhất giữa các chuỗi ngẫu nhiên theo một phân phối biết trước — phân phối giá trị cực trị (extreme value distribution), không phải hình chuông — nên tính thẳng được giá trị E (E-value): số kết quả điểm cao như thế mà ta chờ gặp do tình cờ khi tìm trong một kho cỡ ấy. Kho càng lớn, trùng hợp càng dễ gặp — chính cái bẫy "thử nhiều lần cho tới khi có kết quả" trong bài Xác suất và thống kê. Tư duy xác suất còn đi xa hơn: mô hình Markov ẩn (hidden Markov model) đoán đâu là gen, đâu là vùng xen giữa trong một bộ gen mới đọc — chuyện của bài Mô hình đồ thị xác suất.

Thuật toán cho sinh học tính toán nằm ở đâu trong chồng tầng

Trong chồng tầng của bài Từ electron đến ứng dụng, môn này nằm ở tầng ứng dụng nhưng dùng tới gần như mọi tầng bên dưới: thuật toán chuỗi và đồ thị, hệ cơ sở dữ liệu cho những kho như GenBank, tính toán song song khi một lần giải trình tự sinh ra hàng trăm gigabyte dữ liệu thô. Phía bên kia là chồng tầng của sự sống trong bài Sinh học; môn này là cây cầu giữa hai bên.

Đưa lên

Câu trả lời cho câu hỏi sinh học — hai gen có họ hàng không, đoạn đọc nằm ở đâu, bộ gen trông thế nào, các mẫu virus gần nhau ra sao — kèm con số cho biết chắc tới đâu.

Giấu đi

Hàng trăm triệu đoạn đọc vụn và từng lỗi đọc riêng lẻ — cùng những giả định của mô hình: bảng điểm, độ dài hạt, đồng hồ phân tử, kích thước kho. Ai dùng công cụ như hộp đen sẽ không biết mình đang tin vào giả định nào.

Học trước và học sau

· 6 môn

Thiết kế và phân tích thuật toán

Design and Analysis of Algorithms

Quy hoạch động, đồ thị, NP-đầy đủ — bộ đồ nghề của cả môn này. Trên OpenER, đây là một trong ba chủ đề nên học trước.

Xem chủ đề trên OpenER: Design and Analysis of Algorithms

Sinh học

Biology

DNA, gen, protein, đột biến, tiến hóa — đủ để hiểu đề bài. Nên học trước.

Xem chủ đề trên OpenER: Biology

Xác suất và thống kê

Probability and Statistics

Giá trị p, kiểm định bằng xáo trộn, mô hình xác suất — nền của giá trị E và mô hình Markov ẩn. Nên học trước hoặc song song.

Xem chủ đề trên OpenER: Probability and Statistics

Cấu trúc dữ liệu và giải thuật

Data Structures and Algorithms

Bảng băm, cây, sắp xếp — nền để hiểu các cấu trúc chỉ mục chuỗi như mảng hậu tố (suffix array) mà môn này dùng để tìm trong hàng tỷ chữ cái.

Xem chủ đề trên OpenER: Data Structures and Algorithms

Mô hình đồ thị xác suất

Probabilistic Graphical Models

Mô hình Markov ẩn và thuật toán Viterbi — công cụ tìm gen và phân loại họ protein.

Xem chủ đề trên OpenER: Probabilistic Graphical Models

Học sâu

Deep Learning

Hướng mới của ngành: dự đoán cấu trúc protein, mô hình học từ hàng trăm triệu trình tự.

Xem chủ đề trên OpenER: Deep Learning

Ứng dụng thật và nghề nghiệp

  • Theo dõi dịch bệnh: Viện Vệ sinh Dịch tễ Trung ương giải trình tự toàn bộ gen virus SARS-CoV-2 từ đầu năm 2020. Báo cáo của viện về đầu năm 2022 cho thấy trong 213 mẫu ở miền Bắc có 172 mẫu là Omicron — Omicron đã thay Delta chỉ trong một thời gian rất ngắn. Các trình tự được gửi lên kho dữ liệu quốc tế GISAID và xếp dòng virus bằng các công cụ như Nextclade, Pangolin, dựa trên so khớp và cây phát sinh loài.
  • Y học bộ gen: đoạn đọc từ mẫu máu được dóng vào bộ gen tham chiếu để tìm biến thể (variant), rồi đối chiếu với kho biến thể gây bệnh — một dây chuyền gồm đúng các ý ở trên.
  • Nông nghiệp: tìm gen chịu mặn, kháng bệnh của lúa, chọn giống bằng chỉ thị phân tử.
  • Vi sinh vật và môi trường: đọc lẫn DNA của hàng nghìn loài vi khuẩn trong mẫu đất, nước, ruột người, rồi phân loại chúng — ngành hệ gen học môi trường (metagenomics).
  • Dược và protein: cơ sở dữ liệu AlphaFold đã có hơn 200 triệu cấu trúc dự đoán; thiết kế protein, tìm đích thuốc.
  • Kỹ sư phần mềm cho sinh học: xây dây chuyền xử lý dữ liệu, chạy tính toán trên cụm máy và đám mây cho các phòng thí nghiệm, bệnh viện, công ty xét nghiệm.

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • cài đặt so khớp toàn cục và cục bộ, chọn bảng điểm, đọc kết quả BLAST và giá trị E mà không coi chúng là hộp đen;
  • viết chỉ mục k-mer, ghép một bộ gen nhỏ bằng đồ thị de Bruijn, và hiểu khi nào công cụ thật bỏ sót hay ghép sai;
  • dựng cây phát sinh loài từ ma trận khoảng cách và nói được giả định đằng sau;
  • làm việc cùng nhà sinh học: hiểu câu hỏi của họ, và nói rõ thuật toán trả lời được tới đâu.

Nên biết trước: quy hoạch động và đồ thị ở mức môn Thiết kế và phân tích thuật toán, xác suất cơ bản, Python. Sinh học chỉ cần vừa đủ: bài Sinh học đủ để bắt đầu, và mỗi chương của khóa chính đều kể lại bối cảnh sinh học từ đầu.

Bắt đầu trên OpenER: trang chủ đề Algorithms for Computational Biology có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Khóa chính là chuỗi Bioinformatics Specialization của UC San Diego trên Coursera, do Phillip Compeau và Pavel Pevzner — hai tác giả giáo trình Bioinformatics Algorithms — giảng, mỗi thuật toán có bài lập trình chấm tự động. Muốn vào nhanh bằng Python, có khóa ngắn Algorithms for DNA Sequencing của Johns Hopkins, do Ben Langmead (một tác giả của Bowtie) và Jacob Pritt giảng. Khóa video của IIT Madras trên NPTEL nghiêng về công cụ; slide môn Bioinformatics của Đại học Cambridge cô đọng cả môn trong 12 buổi; MIT 7.91J là bước tiếp theo.

Lời khuyên cho môn này: giải bài trên Rosalind (rosalind.info), trang bài tập tin sinh học chấm tự động đi cùng giáo trình của Compeau và Pevzner. Mọi thuật toán trong bài này đều có ở đó, với dữ liệu đủ lớn để code của bạn phải thật sự nhanh.

Tài liệu tham khảo

  • Phillip Compeau, Pavel Pevzner — Bioinformatics Algorithms: An Active Learning Approach, Active Learning Publishers; đọc tại bioinformaticsalgorithms.org.
  • Richard Durbin, Sean Eddy, Anders Krogh, Graeme Mitchison — Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
  • Neil C. Jones, Pavel A. Pevzner — An Introduction to Bioinformatics Algorithms, MIT Press, 2004.
  • Dan Gusfield — Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
  • MIT 7.91J Foundations of Computational and Systems Biology (Spring 2014) — MIT OpenCourseWare; Bioinformatics (2025–26) — Khoa Khoa học và Công nghệ máy tính, Đại học Cambridge.
  • Các bài báo gốc: S. B. Needleman, C. D. Wunsch, Journal of Molecular Biology 48, 1970; T. F. Smith, M. S. Waterman, Journal of Molecular Biology 147, 1981; S. F. Altschul và cộng sự, "Basic local alignment search tool", Journal of Molecular Biology 215, 1990; S. Karlin, S. F. Altschul, PNAS 87, 1990; P. A. Pevzner, H. Tang, M. S. Waterman, "An Eulerian path approach to DNA fragment assembly", PNAS 98, 2001.
  • NCBI — tài liệu BLAST (BLAST Help và BLAST+ Command Line Applications User Manual).
  • T. T. H. Ung và cộng sự — "Occurrence of the Omicron variant of SARS-CoV-2 in northern Viet Nam in early 2022", Western Pacific Surveillance and Response Journal 13(3), 2022.

Ban biên tập OpenER, “Thuật toán cho sinh học tính toán: khi sinh học thành một ngành dữ liệu”, OpenER, 2026. Phát hành theo CC BY 4.0: được chia sẻ, chỉnh sửa, kể cả thương mại, miễn ghi công tác giả và dẫn link bài gốc.