Luận văn Tiến sĩ Công nghệ thông tin: Một số thuật toán dóng hàng các mạng protein

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> MỘT SỐ THUẬT TOÁN<br /> DÓNG HÀNG CÁC MẠNG PROTEIN<br /> <br /> LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> Hà Nội - 2019<br /> <br /> ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> TRẦN NGỌC HÀ<br /> <br /> MỘT SỐ THUẬT TOÁN<br /> DÓNG HÀNG CÁC MẠNG PROTEIN<br /> <br /> Chuyên ngành: Khoa học máy tính<br /> Mã số: 9480101.01<br /> <br /> LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> NGƯỜI HƯỚNG DẪN KHOA HỌC:<br /> 1. PGS.TS Hoàng Xuân Huấn<br /> 2. GS. TS. Thái Trà My<br /> <br /> Hà Nội - 2019<br /> <br /> LỜI CAM ĐOAN<br /> Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết<br /> quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả<br /> trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa<br /> từng được ai công bố trong các công trình nào khác.<br /> Tác giả<br /> <br /> 1<br /> <br /> LỜI CẢM ƠN<br /> Luận án được thực hiện tại trường ĐH Công nghệ - ĐHQG Hà Nội, dưới<br /> sự hướng dẫn của PGS.TS Hoàng Xuân Huấn và GS.TS Thái Trà My.<br /> Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Hoàng Xuân Huấn, cô Thái<br /> Trà My, những người đã có những định hướng giúp tôi thành công trong việc<br /> nghiên cứu của mình. Thầy cũng đã động viên và chỉ bảo giúp tôi vượt qua<br /> những khó khăn để tôi hoàn thành được luận án này.<br /> Tôi xin chân thành cảm ơn tới TS. Đỗ Đức Đông, TS. Đặng Cao Cường<br /> và các thầy cô ở Bộ môn Khoa học máy tính trường Đại học Công nghệ đã<br /> đóng góp cho tôi nhiều kiến thức quý báu về kiến thức khoa học để tôi có thể<br /> hoàn thành luận án.<br /> Tôi cũng xin cảm ơn tới các thầy, cô thuộc khoa Công nghệ thông tin –<br /> Trường ĐH Công Nghệ, đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình<br /> làm nghiên cứu sinh.<br /> Tôi cũng xin cảm ơn tới các thầy cô ở khoa Toán, và lãnh đạo trường<br /> Đại học Sư Phạm – Đại học Thái Nguyên, đã tạo mọi điều kiện thuận lợi về<br /> mặt thời gian và công tác chuyên môn giúp tôi trong quá trình làm nghiên cứu<br /> sinh.<br /> Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè nơi đã cho<br /> tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay.<br /> <br /> 2<br /> <br /> MỤC LỤC<br /> DANH MỤC BẢNG BIỂU .............................................................................. 7<br /> DANH MỤC CÁC HÌNH ................................................................................. 9<br /> DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ........................................... 10<br /> MỞ ĐẦU ......................................................................................................... 12<br /> Chương 1. DÓNG HÀNG CÁC MẠNG PROTEIN VÀ TỐI ƯU MỀM ...... 16<br /> 1.1.<br /> <br /> Tin sinh học và dóng hàng các mạng protein ...................................... 16<br /> <br /> 1.1.2. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein. ................. 22<br /> 1.1.3. Bài toán dóng hàng mạng tương tác protein - protein ......................... 26<br /> 1.2.<br /> <br /> Tối ưu mềm .......................................................................................... 31<br /> <br /> 1.2.1. Bài toán tối ưu tổ hợp và tiếp cận mềm ............................................... 31<br /> 1.2.2. Phương pháp tối ưu đàn kiến ............................................................... 35<br /> 1.2.3. Tính toán tiến hóa và các thuật toán memetic ..................................... 44<br /> 1.2.4. Thuật toán tìm kiếm Tabu .................................................................... 45<br /> 1.3.<br /> <br /> Động cơ nghiên cứu ............................................................................. 47<br /> <br /> 1.4.<br /> <br /> Kết luận chương ................................................................................... 48<br /> <br /> Chương 2. DÓNG HÀNG CÁC MẠNG CÁC VỊ TRÍ LIÊN KẾT PROTEIN<br /> ......................................................................................................................... 49<br /> 2.1.<br /> <br /> Bài toán dóng hàng nhiều đồ thị .......................................................... 49<br /> <br /> 2.1.1. Tập nhiều đồ thị ................................................................................... 50<br /> 2.1.2. Dóng hàng nhiều đồ thị ........................................................................ 50<br /> 2.1.3. Hàm đánh giá chất lượng dóng hàng ................................................... 51<br /> 3<br /> <br />