Tìm xâu con chung lớn nhất

1
1, Ý tưởng
2, Thực hiện
BT Tin
3, Thuận lợi, khó khăn
4, Tổng kết
1, Ý tưởng
2
?ng d?ng sinh h?c:
So sánh chuỗi DNA của hai hay nhiều sinh vật với nhau

Một chuỗi DNA bao gồm một chuỗi các phân tử (bases)
Base: adenine(A), guanine(G), cytosine(C), và thymine(T)
VD: Chuỗi DNA của:
Sinh vật 1: S1 =ACCGGTCGAGTGCGCGAAGCCGGCCGAA
Sinh vật 2: S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA


So sánh 2 chuỗi để chỉ ra được chúng “giống nhau” như thế nào???
3
1, Ý tưởng
?ng d?ng sinh h?c:
So sánh chuỗi DNA của hai hay nhiều sinh vật với nhau
Phương pháp:
Tìm ra một chuỗi S3 mà các bases của nó xuất hiện cả trong S1 và S2
(những bases này xuất hiện theo cùng thứ tự, không cần thiết liên tiếp nhau).
S3 càng dài -> chuỗi S1 và S2 càng “giống nhau”
S1 = ACCGGTCGAGTGCGCGAAGCCGGCCGAA
S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA

S3 = GTCGTCGGAAGCCGGCCGAA
2, Thực hiện
4
Bài toán dãy con chung dài nhất
- Longest Common Subsequence (LCS)
Cho hai dãy X = và Y = .
Tìm dãy con chung dài nhất của 2 dãy X và Y
2.1. Thuật giải:
Dùng Quy hoạch động để xây dựng thuật toán:
 
2 dãy: X =
Y =

Z = là bất kì LCS của X và Y

Nếu xm = yn thì zk = xm = yn và Zk-1 sẽ là một LCS của Xm-1 và Yn-1
Nếu xm ≠ yn thì zk ≠ xm suy ra rằng Z là một LCS của Xm-1 và Y
Nếu xm ≠ yn thì zk ≠ yn suy ra rằng Z là một LCS của X và Yn-1
5
2, Thực hiện
2.1. Thuật giải:
6
2, Thực hiện
2.1. Thuật giải:
VD: X và Y

Áp dụng giải thuật trên kẻ bảng ta được kết quả như hình:
7
Trong thủ tục trên ta sử dụng biến b[i, j] để ghi nhận tình huống tối ưu khi tính giá trị c[i, j]. Sử dụng biến này ta có thể đưa ra dãy con chung dài nhất của hai dãy X và Y nhơ thủ tục sau đây.
8
2.2. Sơ đồ khối:
2, Thực hiện
2.1. Thuật giải:
3, Thuận lợi, khó khăn
9
3.1. Thuận lợi
Bài toán xây dựng có tính ứng dụng trong thực tế cao
Code bao gồm những câu lệnh không quá phức tạp
- Nguồn tài liệu phong phú
- Mỗi thành viên đều có thể phụ trách từng mảng của bài tập
3.2. Khó khăn
- Code bài toán dài 200 dòng, trong quá trình làm khônng tránh khỏi những sai sót, khó tìm lỗi sai
- SV chưa thành thạo turbo C, PowerPoint
10
4, Tổng kết:
Mặc dù gặp không ít những khó khăn nhưng nhóm đã cố gắng hoàn thành bài tập lớn

Bài toán trên không tránh khỏi những sai sót, nhóm rất mong nhận được sự góp ý của thầy và các bạn!
Mọi ý kiến xin liên hệ:
...