Câu 2 trang 148 Luyện tập Tin học 12- Kết nối tri thức: Trong trường hợp xấu nhất, để sắp xếp các đoạn nucleotide ngắn thành hệ gene người hoàn chỉnh, ước tính cần bao nhiêu phép thử?

Câu hỏi/Đề bài:

Trong trường hợp xấu nhất, để sắp xếp các đoạn nucleotide ngắn thành hệ gene người hoàn chỉnh, ước tính cần bao nhiêu phép thử?

Hướng dẫn:

Thảo luận cùng bạn và thầy cô, kết hợp tìm kiếm thông tin trên Internet để trả lời.

Lời giải:

Giả sử chúng ta có một chuỗi gốc với tổng cộng N nucleotide và muốn sắp xếp các đoạn nucleotide ngắn thành chuỗi đó.

Nếu các đoạn nucleotide ngắn có độ dài lần lượt là n1, n2, n3, …, nk (với k là số lượng đoạn), thì số lượng phép thử cần thiết để sắp xếp chúng thành chuỗi đầy đủ là tích của số lượng tổ hợp khác nhau có thể có cho mỗi đoạn.

Với ví dụ đơn giản, giả sử chúng ta chỉ có một đoạn nucleotide ngắn với độ dài n. Trong trường hợp này, số lượng phép thử cần thiết là 4^n, vì mỗi vị trí trong đoạn có thể là một trong 4 loại nucleotide (A, C, G, T).

Tuy nhiên, trong trường hợp tổng quát với nhiều đoạn nucleotide ngắn khác nhau, chúng ta cần nhân các số lượng tổ hợp lại với nhau. Vì vậy, số lượng phép thử cần thiết sẽ là tích của (4^n1) x (4^n2) x (4^n3) x … x (4^nk).