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
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ử?
Giải Tin học 12 Bài 27: Máy tính và Khoa học dữ liệu - Kết nối tri thức
Luyện tập 2 trang 148 Tin học 12: 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ử?
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).
Lời giải bài tập Tin học 12 Bài 27: Máy tính và Khoa học dữ liệu hay khác: