Chuyên Đ Nghiên C u 7 - Tin Sinh H c.ề ứ ọ
Gi ng Viên: ảNgô Công Th ng.ắ
Sinh viên th c hi n: ự ệ Nguy n H ng Kiênễ ồ .
L p: ớTin h c A-K52.ọ
Khoa: Công Ngh Thông Tin.ệ
Mã Sinh Viên: 521996.
Chuyên Đ Nghiên C u 7 - Tin Sinh H c.ề ứ ọ
N i Dung:ộ
Nhóm 2:
Nhóm 2: Tìm hi u bài toán so sánh c p trình t :ể ặ ự
a. N i dung và ý nghĩa sinh h c c a bài toán so sánh c p ộ ọ ủ ặ
trình t .ự
b. Thu t toán ma tr n đi m. ậ ậ ể
d. Thu t toán quy ho ch đ ng Needlemanậ ạ ộ -Wunsch.
N i dungộ
Tìm hi u bài toán so sánh c p trình t :ể ặ ự
1. N i dung và ý nghĩa sinh h c c a bài toán so sánh ộ ọ ủ
c p trình t .ặ ự
2. Thu t toán ma tr n đi m. ậ ậ ể
3. Thu t toán quy ho ch đ ng Needlemanậ ạ ộ -Wunsch.
1. N i dung và ý nghĩa sinh h c c a bài toán ộ ọ ủ
so sánh c p trình t .ặ ự
-Đ nh nghĩa: so sánh trình t là quá trình nghiên c u ị ự ứ
s gi ng nhau gi a các chu i trình t (sequence),ự ố ữ ỗ ự
-là cách th c so sánh gi a 2 hay nhi u trình t d a ứ ữ ề ự ự
trên vi c so sánh m t chu i các thành ph n(ký t ) ệ ộ ỗ ầ ự
c a trình t đ tìm ra nh ng đi m t ng đ ng, ủ ự ể ữ ể ươ ồ
gi ng nhau gi a các trình t . ố ữ ự
1. N i dung và ý nghĩa sinh h c c a bài toán ộ ọ ủ
so sánh c p trình t .ặ ự
- Cho 2 chu i sinh h c S1,S2. Gióng c p chu i này đ c th c ỗ ọ ặ ỗ ượ ự
hi n b ng cách chèn thêm vào hai chu i S1 và S2 các d u ệ ằ ỗ ấ
cách (kí hi u là ”-”) t i các v trí b t kỳ v i s l ng không ệ ạ ị ấ ớ ố ượ
h n ch đ t o ra 2 chu i S1’ và S2’ t ng ng, sau đó đ t ạ ế ể ạ ỗ ươ ứ ặ
m t chu i trên chu i kia sao cho môi kí t c a chu i này ộ ỗ ỗ ự ủ ỗ
gióng th ng v i m t kí t c a chu i kia và c p trình t gióng ẳ ớ ộ ự ủ ỗ ặ ự
không đ ng th i là d u cách.ồ ờ ấ
- Chu i sinh h c ban đ u không có d u cách và n u lo i b d u ỗ ọ ầ ấ ế ạ ỏ ấ
kh i S1’ và S2’ ta s có S1 và S2 ban đ u.ỏ ẽ ầ
- Yêu c u đ t ra là th c hi n bài toán sao cho tìm ra c p chu i ầ ặ ự ệ ặ ỗ
S1’, S2’ có s t ng đ ng cao nh t.ự ươ ồ ấ