- ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ. - BÀI TOÁN CẤU TRÚC CHUỖI NGUỒN (Founder Sequences Reconstruction Problem). - LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN. - Ngành: Công nghệ thông tin. - Chuyên ngành: Hệ thống thông tin Mã số: 60480104. - Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể và cá nhân tôi nói riêng. - Cuối cùng tôi cũng bày tỏ lòng biết ơn về sự giúp đỡ của các anh, chị đồng nghiệp trong Bộ môn Tin học trường Đại học Công Đoàn, cơ quan nơi tôi công tác đã tạo điệu kiện tốt nhất cho tôi về thời gian cũng như động viên tôi hoàn thành bài luận văn.. - BÀI TOÁN CẤU TRÚC CHUỖI NGUỒN. - Một số khái niệm trong sinh học. - Phát biểu bài toán cấu trúc chuỗi nguồn. - Mô hình bài toán. - Bài toán 1: tìm số điểm ngắt nhỏ nhất. - Bài toán 2: tìm chuỗi nguồn. - Các phƣơng pháp tiếp cận để giải bài toán cấu trúc chuỗi nguồn. - Phương pháp giải bài toán tìm ra số điểm ngắt nhỏ nhất. - Phương pháp giải bài toán tìm số chuỗi nguồn. - GIỚI THIỆU VỀ THUẬT TOÁN ANT COLONY OPTIMIZATION (ACO. - Giới thiệu về thuật toán ACO. - Mô hình mô phỏng của thuật toán. - Đồ thị cấu trúc. - Trình bày về thuật toán ACO cơ bản. - Thông tin Heuristic. - Thuật toán AS. - Thuật toán ACS. - Thuật toán Max-Min. - Thuật toán Max- Min trơn. - Ứng dụng thuật toán ACO trong việc giải quyết bài toán Ngƣời chào hàng Sale Man. - Bài toán người chào hàng trong thực tế. - Phát biểu bài toán người đưa hàng trên mô hình hóa đồ thị. - Áp dụng thuật toán ACO giải quyết bài toán người chào hàng. - THUẬT TOÁN MỚI. - Thuật toán tối ƣu đàn kiến ACO. - Xây dựng đồ thị cấu trúc. - Thông tin heuristic. - Thuật toán Max – Min. - Thuật toán Max – Min trơn. - So sánh giữa hai cách cập nhật mùi. - Mô tả thuật toán tối ƣu đàn kiến ACO tổng quát giải bài toán cấu trúc chuỗi nguồn. - KẾT QUẢ THỰC NGHIỆM. - Mô tả thực nghiệm. - Kết quả thực nghiệm. - So sánh các kết quả thực nghiệm. - So sánh kết quả với RecBlock. - So sánh kết quả với hai thuật toán cập nhật mùi khác nhau. - Bảng 2.1 Một số thuật toán ACO. - Bảng 4.1 So sánh thực nghiệm với RecBlock trên bộ dữ liệu Random. - Bảng 4.2 So sánh thực nghiệm với RecBlock trên bộ dữ liệu evo. - Bảng 4.3 So sánh thực nghiệm với RecBlock trên bộ dữ liệu ms. - Kết quả thực nghiệm so sánh hai phương pháp MMAS và SMMAS với bộ dữ liệu rnd_30_60. - Kết quả thực nghiệm so sánh ba phương pháp ACS, MMAS và SMMAS với bộ dữ liệu evo_50_250. - Kết quả thực nghiệm so sánh ba phương pháp ACS, MMAS và SMMAS với bộ dữ liệu ms_50_250. - Hình 1.1 Cấu trúc nhiễm sắc thể. - Hình 1.2 Minh họa gen trên nhiễn sắc thể. - Hình 1.3 Một đột biến điểm xảy ra trong phân tử DNA thay thế cặp nucleotide A-T bằng cặp nucleotide G-C. - Ví dụ về bộ gen tái tổ hợp được tạo từ chuỗi nguồn. - Minh họa đầu vào của bài toán. - Minh họa đầu ra của bài toán. - Đặc tả thuật toán Recblock. - Hình 2.3 Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm. - Hình 2.4 Đặc tả thuật toán ACO. - Hình 2.5 Minh họa hình ảnh bài toán người đưa hàng. - Hình 2.6 Đặc tả thuật toán ACO cho bài toán TSP. - Đồ thị xây dựng thuật toán ACO đối với bài toán cấu trúc chuỗi nguồn. - Hình 3.2 Lựa chọn đỉnh tiếp theo. - Hình 3.3 Đặc tả thuật toán ACO. - Đồ thị cấu trúc cho bộ dữ liệu với n= 5, m= 7. - Hình 4.1 Mô tả INPFILE với bộ dữ liệu rnd_30_90. - Hình 4.2 Mô tả OUTFILE tìm ra k =5 trên bộ dữ liệu rnd_30_90. - Hình 4.3 Mô tả OUTFILE tìm ra điểm ngắt trong bộ dữ liệu rnd_30_90. - Tin sinh học là một lĩnh vực khoa học liên ngành, trong đó sinh học phân tử và tin học đóng vai trò chủ đạo. - Sinh học làm môi trường dữ liệu cơ sở, trên đó xây dựng và hoàn thiện các chương trình xử lý dữ liệu ứng dụng làm công cụ hỗ trợ hiệu quả cho việc nghiên cứu, thu nhận và sản xuất ra các sản phẩm sinh học mong muốn khác nhau phục vụ đời sống con người…Về cơ bản, tin sinh học tập trung vào nghiên cứu và áp dụng các phương pháp cũng như các kĩ thuật trong tin học để giải quyết các bài toán trong sinh học phân tử. - Tin sinh học có tính ứng dụng cao trong cuộc sống, đặc biệt trong lĩnh vực y-dược và trong lĩnh lực di truyền.. - Trong sinh học, di truyền chuyển những đặc trưng sinh học từ một sinh vật cha mẹ đến con cái và nó đồng nghĩa với di chuyển, gen thừa nhận mang thông tin sinh học.. - Bài toán cấu trúc chuỗi nguồn là một bài toán cho các thông tin ở dạng một chuỗi của các nhiễm sắc thể hiện tại, và tìm ra được các thông tin về nhiễm sắc thể của tổ tiên. - Đó là một bài toán lớn trong sinh học, hiện nay đang được rất nhiều người quan tâm và nghiên cứu.. - Đã có nhiều thuật toán nghiên cứu và công bố giải quyết bài toán cấu trúc chuỗi nguồn để tìm ra được các thông tin di truyền.. - Trong luận văn này, tôi trình bày khảo cứu lại các phương pháp giải quyết bài toán cấu trúc chuỗi nguồn. - Tôi khảo cứu và cài đặt lại thuật toán RecBlock được Andrea Roli and Christian Blum đề xuất năm 2009 là một thuật toán được coi là hoàn chỉnh nhất đến thời điểm hiện tại để giải bài toán cấu trúc chuỗi nguồn. - Sử dụng ý tưởng xây dựng lời giải của RecBlock, trong luận văn chúng tôi đã đề xuất một thuật toán mới đó là thuật toán tối ưu đàn kiến Ant colony optimization (ACO) để giải quyết bài toán cấu trúc chuỗi nguồn mục đích để tìm ra được chuỗi nhiễm sắc thể của tổ tiên dựa trên số lần lai ghép là ít nhất. - Đây là thuật toán mới và lần đầu tiên được đưa vào để giải bài toán cấu trúc chuỗi nguồn. - Và trong thực nghiệm đã chỉ ra được thuật toán ACO tối ưu hơn rất nhiều so với thuật toán RecBlock. - Luận văn còn cài đặt với các thuật toán cập nhật mùi khác nhau trong thuật toán ACO và kết quả trả về vẫn là tối ưu hơn thuật toán trước.. - Ngoài phần kết luận, cấu trúc nội dung của luận văn bao gồm:. - [1] Đỗ Đức Đông và Hoàng Xuân Huấn (2011), “Về biến thiên của vết mùi trong phương pháp ACO và các thuật toán mới”, Tạp chí Tin học và điều khiển học, T.27, tr. - [2] Đỗ Đức Đông (2012), Phương pháp tối ưu đàn kiến và ứng dụng, Đại học Công nghệ - Đại học Quốc gia Hà Nội, luận án Tiến sĩ.. - [3] Hoàng Trọng Phán, Trương Thị Bích Phượng, Trần Quốc Dung (2005), Giáo trình di truyền học, Dự án Giáo dục Đại học- Đại học Huế.. - [4] Lê Sỹ Vinh (2013), Giáo trinh Nhập môn Tin sinh tr.12-tr.23 – trường Đại học Công nghệ - Đại học Quốc gia Hà Nội.