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

Hướng dẫn học chủ đề

Thuật toán cho sinh học tính toán

Algorithms for Computational Biology

Nâng caokhoảng 35 giờ5 bước

Thuật toán cho tin sinh học: xử lý và phân tích dữ liệu sinh học lớn như trình tự gene.

Bắt đầu học

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ách

Giáo trình chính

Bioinformatics Algorithms: An Active Learning Approach

Phillip Compeau, Pavel Pevzner · 2014

Có phíNâng caoTiếng Anh362 trang

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

CC BYTrung bìnhTiếng Anh472 trang

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.

  1. 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 đồ.

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

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

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

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

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.

Chọn nguồn tự học

Cần một nền tảng sinh học cơ bản song song với thuật toán để hiểu bài toán thực tế.