Bạn sẽ học được gì
- Định vị điểm khởi đầu sao chép DNA bằng thuật toán tìm motif và biểu đồ độ lệch (skew diagram)
- Áp dụng quy hoạch động để giải bài toán so khớp trình tự (sequence alignment) và tính khoảng cách chỉnh sửa
- Cài đặt thuật toán lắp ráp bộ gene (genome assembly) dựa trên đồ thị De Bruijn
- Dùng mô hình Markov ẩn (HMM) để giải bài toán tìm gene hoặc phân đoạn trình tự
- Xây cây phát sinh loài (phylogenetic tree) từ dữ liệu trình tự bằng thuật toán khoảng cách
Nên học trước
Giới thiệu
Thuật toán cho tin sinh học áp dụng các kỹ thuật thiết kế thuật toán — chủ yếu là quy hoạch động và cấu trúc dữ liệu chuỗi — để trả lời câu hỏi sinh học cụ thể: gene bắt đầu sao chép ở đâu, hai trình tự giống nhau đến mức nào, hệ gene lắp ráp lại ra sao từ hàng triệu đoạn đọc ngắn. Mỗi thuật toán trong môn này đều gắn với một câu hỏi sinh học thật, không trừu tượng.
Một trục xuyên suốt: quy hoạch động trên chuỗi
Phần lớn bài toán quy về so sánh hoặc ghép các chuỗi ký tự (A, C, G, T hoặc amino acid): căn chỉnh trình tự, tìm motif chung, đo khoảng cách tiến hóa. Quy hoạch động là công cụ trung tâm — nắm vững bảng quy hoạch động cho bài toán edit distance là nền tảng cho gần như mọi chương còn lại.
Từ chuỗi đơn lẻ đến toàn bộ hệ gene
Khi dữ liệu là hàng triệu đoạn đọc ngắn từ máy giải trình tự, quy hoạch động từng cặp không còn khả thi — đây là lúc đồ thị (đồ thị De Bruijn cho lắp ráp gene, cây cho phát sinh loài) và các cấu trúc dữ liệu chuỗi chuyên biệt phát huy tác dụng. Luôn tự hỏi: dữ liệu đầu vào lớn cỡ nào, và cấu trúc dữ liệu nào giúp tránh so sánh mọi cặp.
Sinh học chỉ cần vừa đủ
Không cần học sinh học chuyên sâu — mỗi bài toán trong lộ trình đều tóm tắt đủ bối cảnh sinh học cần thiết. Quan trọng hơn là thói quen tin sinh học: luôn hỏi "giả định thống kê nào đứng sau thuật toán này" trước khi tin kết quả nó trả về.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Bioinformatics Algorithms: An Active Learning Approach
Phillip Compeau, Pavel Pevzner · 2014
Vì sao chọn: Giáo trình tin sinh học dùng rộng rãi nhất hiện nay (200+ đại học), mỗi chương mở đầu bằng một câu hỏi sinh học cụ thể rồi phát triển dần thuật toán để trả lời, đúng tinh thần và thứ tự của lộ trình này. Sách trả phí (một số chương mẫu đọc miễn phí trên trang chính thức), có bài tập tự chấm miễn phí trên Rosalind.
Nên đọc: Chương 1–3 (khởi đầu sao chép, tìm motif, lắp ráp gene), Chương 5 (so khớp trình tự), Chương 7 và 10 (phát sinh loài, mô hình Markov ẩn)
Algorithms
Jeff Erickson · 2019
Sách đã có trong catalog (CC BY, miễn phí). Ôn lại kỹ thuật quy hoạch động tổng quát trước khi học các biến thể chuyên biệt cho sinh học (so khớp trình tự, HMM) — chương Dynamic Programming là nền tảng trực tiếp cho các bước đầu của lộ trình này.
Nên đọc: Chương 3 Dynamic Programming
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Từ câu hỏi sinh học đến bài toán thuật toán: khởi đầu sao chép DNA
khoảng 5 giờTìm hiểu vì sao vị trí khởi đầu sao chép (ori) quan trọng, học biểu đồ độ lệch (skew diagram) và bài toán tìm k-mer thường xuất hiện nhất. Viết chương trình tính biểu đồ độ lệch cho một bộ gene vi khuẩn thật và định vị ori bằng điểm cực tiểu của biểu đồ.
- Đọc: Chương 1: Where in the Genome Does DNA Replication Begin? — Bioinformatics Algorithms: An Active Learning Approach
Bước 2: Tìm motif và nền tảng quy hoạch động cho chuỗi
khoảng 7 giờÔn quy hoạch động tổng quát rồi áp dụng vào bài toán tìm motif (đồng hồ phân tử) bằng tìm kiếm nhánh-cận và thuật toán Gibbs sampling ngẫu nhiên. Cài đặt thuật toán tìm motif ngẫu nhiên hóa và so sánh độ chính xác với tìm kiếm vét cạn trên dữ liệu mô phỏng.
- Đọc: Chương 3 Dynamic Programming — Algorithms
- Đọc: Chương 2: Which DNA Patterns Play the Role of Molecular Clocks? — Bioinformatics Algorithms: An Active Learning Approach
Bước 3: Lắp ráp bộ gene bằng đồ thị De Bruijn
khoảng 8 giờHọc cách xây đồ thị De Bruijn từ các k-mer chồng lấp và quy bài toán lắp ráp gene về tìm đường đi/chu trình Euler. Tự lắp ráp một bộ gene nhỏ mô phỏng từ tập đoạn đọc ngắn cho trước bằng thuật toán đường đi Euler.
- Đọc: Chương 3: How Do We Assemble Genomes? — Bioinformatics Algorithms: An Active Learning Approach
Bước 4: So khớp trình tự và khoảng cách chỉnh sửa
khoảng 7 giờHọc bài toán so khớp trình tự toàn cục/cục bộ (Needleman-Wunsch, Smith-Waterman) bằng quy hoạch động với ma trận điểm số. Cài đặt so khớp cục bộ cho hai trình tự protein thật và giải thích ý nghĩa sinh học của vùng khớp điểm cao nhất.
- Đọc: Chương 5: How Do We Compare Genes? — Bioinformatics Algorithms: An Active Learning Approach
Bước 5: Cây phát sinh loài và mô hình Markov ẩn
khoảng 8 giờHọc dựng cây phát sinh loài từ ma trận khoảng cách (như UPGMA/Neighbor Joining) và mô hình Markov ẩn giải bằng thuật toán Viterbi. Dựng cây phát sinh loài từ 5 trình tự virus mô phỏng bằng Neighbor Joining, sau đó cài đặt Viterbi cho một HMM 2 trạng thái đơn giản.
- Đọc: Chương 7: Which Animal Gave Us SARS? — Bioinformatics Algorithms: An Active Learning Approach
- Đọc: Chương 10: Why Have Biologists Still Not Developed an HIV Vaccine? — Bioinformatics Algorithms: An Active Learning Approach
Khái niệm chính
- So khớp trình tự & Khoảng cách chỉnh sửa
- Đo độ tương đồng giữa hai chuỗi bằng số phép chèn/xóa/thay thế tối thiểu; giải bằng quy hoạch động trong thời gian O(nm).
- Đồ thị De Bruijn
- Cấu trúc dữ liệu biểu diễn các đoạn đọc ngắn chồng lấp nhau bằng cách nối các k-mer; lắp ráp bộ gene quy về tìm đường đi Euler trên đồ thị này.
- Mô hình Markov ẩn (HMM)
- Mô hình xác suất cho dữ liệu tuần tự với trạng thái ẩn, như vùng mã hóa/không mã hóa; giải bằng thuật toán Viterbi — một dạng quy hoạch động trên xác suất.
- Biểu đồ độ lệch (Skew diagram)
- Đồ thị đếm chênh lệch số lượng G và C dọc theo bộ gene, dùng để định vị điểm khởi đầu sao chép DNA.
- Tìm motif (Motif finding)
- Tìm mẫu trình tự ngắn xuất hiện lặp lại, có thể lệch vài ký tự, trong nhiều chuỗi; ứng dụng tìm vị trí gắn của protein điều hòa.
- Cây phát sinh loài (Phylogenetic tree)
- Cây biểu diễn quan hệ tiến hóa giữa các loài hoặc trình tự, dựng từ ma trận khoảng cách hoặc nguyên lý tiết kiệm tối đa (parsimony).
- Suffix tree / Suffix array
- Cấu trúc dữ liệu chỉ mục cho một chuỗi dài, cho phép tìm kiếm mẫu con trong thời gian gần như hằng số sau khi xây dựng.
Học xong để làm gì
- Giải trình tự bộ gene người và các sinh vật khác: lắp ráp từ hàng triệu đoạn đọc ngắn bằng đồ thị De Bruijn
- Truy vết nguồn gốc dịch bệnh (như SARS-CoV-2): dựng cây phát sinh loài từ trình tự virus thu thập theo thời gian
- Chẩn đoán bệnh di truyền: định vị đột biến gây bệnh bằng so khớp trình tự bệnh nhân với bộ gene tham chiếu
- Phát triển thuốc và vaccine: phân tích trình tự protein, dự đoán vùng mã hóa gene bằng HMM
- Phân loại vi sinh vật trong hệ vi sinh vật (microbiome) bằng so khớp và phân cụm trình tự
Câu hỏi thường gặp
Không có nền sinh học thì học nổi không?
Nổi, vì mỗi bài toán đều bắt đầu từ một câu hỏi sinh học được giải thích lại từ đầu; quan trọng hơn là vững quy hoạch động và cấu trúc dữ liệu chuỗi.
Môn này có cần biết thống kê sâu không?
Cần hiểu xác suất cơ bản (biến ngẫu nhiên, kỳ vọng, chuỗi Markov) để dùng được mô hình Markov ẩn — nếu chưa vững nên ôn lại song song.
Khác gì với việc dùng công cụ tin sinh học có sẵn như BLAST?
Môn học dạy nguyên lý đằng sau các công cụ đó; hiểu thuật toán giúp biết khi nào công cụ có thể cho kết quả sai hoặc chọn tham số phù hợp thay vì dùng như hộp đen.
Học xong có thể làm việc trong ngành công nghệ sinh học không?
Đây là nền tảng trực tiếp cho các vị trí bioinformatics/computational biology tại viện nghiên cứu, công ty giải trình tự hoặc dược phẩm.

