Luận văn thạc sĩ bài toán cấu trúc chuỗi nguồn founder sequences reconstruction problem 04

Luận văn thạc sĩ: Nghiên cứu bài toán cấu trúc chuỗi nguồn. Tối ưu hóa việc tái cấu trúc founder sequences. Tìm hiểu sâu về vấn đề này.

• Tác giả: Lê Thị Hào
• Người hướng dẫn: TS. Đỗ Đức Đông
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Bài Toán Cấu Trúc Chuỗi Nguồn (Founder Sequences Reconstruction Problem)
• Loại tài liệu: Luận văn Thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• MỤC LỤC
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC HÌNH VẼ
• I. CHƯƠNG I: BÀI TOÁN CẤU TRÚC CHUỖI NGUỒN
• 1. Một số khái niệm trong sinh học
• 1. Một số khái niệm về di truyền
• 1. Quá trình đột biến DNA
• 1. Khái quát về các Haplotype được tạo từ các tái tổ hợp
• 1. Phát biểu bài toán cấu trúc chuỗi nguồn
• 1. Mô hình bài toán
• 1. Bài toán 1: tìm số điểm ngắt nhỏ nhất
• 1. Bài toán 2: tìm chuỗi nguồn
• 1. Các phƣơng pháp tiếp cận để giải bài toán cấu trúc chuỗi nguồn
• 1. Phương pháp giải bài toán tìm ra số điểm ngắt nhỏ nhất
• 1. Phương pháp giải bài toán tìm số chuỗi nguồn
• II. CHƢƠNG II: GIỚI THIỆU VỀ THUẬT TOÁN ANT COLONY OPTIMIZATION (ACO)
• 2. Giới thiệu về thuật toán ACO
• 2. Mô hình mô phỏng của thuật toán
• 2. Kiến tự nhiên
• 2. Kiến nhân tạo
• 2. Trình bày giải thuật
• 2. Đồ thị cấu trúc
• 2. Trình bày về thuật toán ACO cơ bản
• 2. Thông tin Heuristic
• 2. Quy tắc cập nhật vết mùi
• 2. Thuật toán AS
• 2. Thuật toán ACS
• 2. Thuật toán Max-Min
• 2. Thuật toán Max- Min trơn
• 2. Ứ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
• 2. Bài toán người chào hàng trong thực tế
• 2. Phát biểu bài toán người đưa hàng trên mô hình hóa đồ thị
• 2. Áp dụng thuật toán ACO giải quyết bài toán người chào hàng
• III. CHƢƠNG III: THUẬT TOÁN MỚI
• 3. Thuật toán tối ƣu đàn kiến ACO
• 3. Xây dựng đồ thị cấu trúc
• 3. Xây dựng lời giải tuần tự
• 3. Thông tin heuristic
• 3. Cập nhật mùi
• 3. Thuật toán Max – Min
• 3. Thuật toán Max – Min trơn
• 3. So sánh giữa hai cách cập nhật mùi
• 3. 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
• 3. Số lƣợng kiến
• 3. Tham số bay hơi
• IV. CHƢƠNG IV: KẾT QUẢ THỰC NGHIỆM
• 4. Mô tả thực nghiệm
• 4. Các thông số cài đặt
• 4. Kết quả thực nghiệm
• 4. So sánh các kết quả thực nghiệm
• 4. So sánh kết quả với RecBlock
• 4. So sánh kết quả với hai thuật toán cập nhật mùi khác nhau
• KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO
• DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT
• MỞ ĐẦU
• I. CHƢƠNG I: BÀI TOÁN CẤU TRÚC CHUỖI NGUỒN
• 1. Một số khái niệm trong sinh học
• 1. Một số khái niệm về di truyền
• 1. Quá trình đột biến DNA
• 1. Khái quát về các Haplotype đƣợc tạo từ các tái tổ hợp
• 1. Phát biểu bài toán cấu trúc chuỗi nguồn
• 1. Mô hình bài toán
• 1. Bài toán 1: tìm số điểm ngắt nhỏ nhất

Tóm tắt

I. Giải mã Cấu trúc chuỗi nguồn Tổng quan luận văn thạc sĩ

Luận văn thạc sĩ về bài toán cấu trúc chuỗi nguồn (Founder Sequences Reconstruction Problem) là một công trình nghiên cứu chuyên sâu trong lĩnh vực tin sinh học, một ngành khoa học liên ngành kết hợp giữa sinh học phân tử và công nghệ thông tin. Nghiên cứu này tập trung vào việc áp dụng các kỹ thuật tin học để giải quyết những vấn đề phức tạp trong sinh học phân tử, đặc biệt là lĩnh vực di truyền. Di truyền học nghiên cứu sự chuyển giao các đặc tính sinh học từ thế hệ cha mẹ sang con cái thông qua gen, nơi chứa đựng thông tin di truyền được mã hóa trong chuỗi DNA. Hiểu rõ nguồn gốc tổ tiên và quá trình tiến hóa là một trong những mục tiêu cốt lõi của khoa học hiện đại. Bài toán cấu trúc chuỗi nguồn đóng vai trò quan trọng trong mục tiêu này, cho phép các nhà khoa học truy ngược thông tin di truyền từ các nhiễm sắc thể hiện tại để tái tạo lại nhiễm sắc thể (NST) của tổ tiên. Việc này có ý nghĩa to lớn trong y học, giúp xác định các gen liên quan đến bệnh tật hoặc các đặc điểm y khoa quan trọng. Luận văn này không chỉ khảo cứu các phương pháp đã có mà còn đề xuất một thuật toán mới dựa trên tối ưu hóa đàn kiến (Ant Colony Optimization - ACO). Đây là một hướng tiếp cận lần đầu được áp dụng cho bài toán cấu trúc chuỗi nguồn, hứa hẹn mang lại hiệu quả vượt trội so với các thuật toán trước đây như RecBlock. Mục tiêu chính của luận văn là tìm ra một tập hợp chuỗi nguồn sao cho tổng số lần lai ghép, hay còn gọi là điểm ngắt, là ít nhất, từ đó xây dựng lại bức tranh di truyền một cách chính xác nhất. Công trình nghiên cứu này cung cấp một cái nhìn toàn diện từ các khái niệm sinh học cơ bản đến việc triển khai và thực nghiệm một thuật toán metaheuristic tiên tiến, mở ra những hướng phát triển mới cho ngành tin sinh học.

1.1. Nền tảng Tin sinh học và các khái niệm di truyền cốt lõi

Tin sinh học là lĩnh vực sử dụng sức mạnh tính toán để phân tích dữ liệu sinh học khổng lồ. Nền tảng của nó là các khái niệm di truyền cơ bản. Nhiễm sắc thể (NST) là cấu trúc chứa chuỗi DNA và protein, mang toàn bộ thông tin di truyền của sinh vật. DNA là một chuỗi xoắn kép được tạo thành từ bốn loại nucleotide (A, T, G, C). Một đoạn DNA mang thông tin mã hóa cho một protein cụ thể được gọi là gen. Các biến thể của một gen được gọi là alen. Một khái niệm quan trọng là Đa hình đơn nucleotide (SNP), tức sự thay đổi của một nucleotide duy nhất trong bộ gen, tạo ra sự khác biệt giữa các cá thể. Haplotype là một chuỗi các alen trên cùng một nhiễm sắc thể được di truyền cùng nhau. Việc nghiên cứu các haplotype giúp xác định mối liên quan giữa gen và bệnh tật.

1.2. Phát biểu chính thức bài toán Cấu trúc chuỗi nguồn

Bài toán cấu trúc chuỗi nguồn (Founder Sequences Reconstruction Problem - FSRP) được phát biểu như sau: Cho một tập hợp C gồm n tái tổ hợp (recombinants), mỗi tái tổ hợp là một chuỗi nhị phân {0, 1} có độ dài m, và một số nguyên k cho trước. Yêu cầu của bài toán là tìm ra một tập hợp F gồm k chuỗi nguồn (founder sequences), mỗi chuỗi cũng có độ dài m, sao cho mỗi tái tổ hợp trong C có thể được tạo thành từ các đoạn của các chuỗi nguồn trong F với tổng số điểm ngắt (breakpoints) là nhỏ nhất. Một điểm ngắt xảy ra khi hai đoạn gen liên tiếp trong một tái tổ hợp đến từ hai chuỗi nguồn khác nhau. Mục tiêu là tối ưu hóa việc phân rã các tái tổ hợp để giảm thiểu số lần lai ghép trong quá trình tiến hóa.

II. Thách thức chính trong việc tái Cấu trúc chuỗi nguồn gen

Việc giải quyết bài toán cấu trúc chuỗi nguồn đối mặt với nhiều thách thức lớn, chủ yếu xuất phát từ tính phức tạp tổ hợp của không gian tìm kiếm. Khi số lượng chuỗi nguồn (k) và độ dài của chuỗi gen (m) tăng lên, số lượng lời giải tiềm năng tăng theo cấp số nhân, khiến các phương pháp duyệt cạn trở nên bất khả thi. Đây là một bài toán thuộc lớp NP-khó, đòi hỏi các thuật toán heuristic và metaheuristic hiệu quả để tìm ra lời giải gần tối ưu trong thời gian hợp lý. Một trong những khó khăn chính là việc phải giải quyết đồng thời hai bài toán con lồng vào nhau. Bài toán thứ nhất là tìm số điểm ngắt nhỏ nhất cho một tập tái tổ hợp khi đã biết trước các chuỗi nguồn. Bài toán thứ hai, cũng là bài toán chính, là tìm ra k chuỗi nguồn tối ưu sao cho tổng số điểm ngắt là nhỏ nhất. Các phương pháp truyền thống như quy hoạch động, do Ukkonen đề xuất, tỏ ra không hiệu quả với dữ liệu lớn. Thuật toán cận và nhánh (branch-and-bound) dù hứa hẹn nhưng cũng chỉ được đánh giá trên các tập dữ liệu nhỏ. Thuật toán RecBlock, được xem là một trong những phương pháp hoàn chỉnh nhất trước đây, hoạt động theo cơ chế tham lam, xây dựng lời giải theo từng cột. Mặc dù cải thiện được tốc độ, RecBlock có nguy cơ bị mắc kẹt ở các điểm tối ưu cục bộ và không đảm bảo tìm ra lời giải tối ưu toàn cục. Do đó, việc tìm kiếm một phương pháp mới có khả năng khám phá không gian lời giải rộng hơn và tránh được các cạm bẫy cục bộ là một yêu cầu cấp thiết, dẫn đến sự ra đời của các thuật toán dựa trên tối ưu hóa đàn kiến (ACO).

2.1. Vấn đề xác định số điểm ngắt breakpoint tối thiểu

Bài toán tìm số điểm ngắt nhỏ nhất là một hàm mục tiêu quan trọng cho bài toán chính. Với một tập tái tổ hợp và một tập chuỗi nguồn đã cho, mục tiêu là phân rã mỗi tái tổ hợp thành các đoạn con, mỗi đoạn thuộc về một chuỗi nguồn duy nhất. Thách thức nằm ở việc lựa chọn chuỗi nguồn cho mỗi đoạn sao cho số lần chuyển đổi giữa các chuỗi nguồn (tức là số điểm ngắt) là tối thiểu. Luận văn sử dụng một thuật toán tham lam để giải quyết vấn đề này: tại mỗi vị trí, thuật toán sẽ chọn đoạn dài nhất có thể khớp với một trong các chuỗi nguồn, sau đó lặp lại quy trình cho phần còn lại. Mặc dù nhanh chóng, cách tiếp cận này không đảm bảo tìm được kết quả tối ưu tuyệt đối.

2.2. Hạn chế của các phương pháp truyền thống như RecBlock

Thuật toán RecBlock xây dựng ma trận chuỗi nguồn F theo từng cột một. Tại mỗi bước, nó đưa ra quyết định cục bộ để điền vào cột tiếp theo sao cho số điểm ngắt phát sinh là ít nhất tại thời điểm đó. Ưu điểm của RecBlock là tốc độ, vì nó chỉ cần chạy một lần để đưa ra kết quả. Tuy nhiên, bản chất tham lam (greedy) này chính là nhược điểm lớn nhất. Quyết định được đưa ra ở một cột có thể không phải là lựa chọn tốt nhất cho toàn bộ lời giải. Điều này dẫn đến nguy cơ thuật toán bị sa vào các điểm tối ưu cục bộ, tạo ra một cấu trúc chuỗi nguồn không thực sự tối ưu về tổng thể. Do đó, cần một thuật toán có khả năng học hỏi và khám phá tốt hơn, như thuật toán ACO.

III. Hướng dẫn áp dụng Tối ưu hóa đàn kiến cho chuỗi nguồn

Tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) là một phương pháp metaheuristic mô phỏng hành vi tìm kiếm thức ăn của loài kiến trong tự nhiên. Thuật toán này đã được chứng minh là rất hiệu quả trong việc giải quyết các bài toán tối ưu hóa tổ hợp, bao gồm cả bài toán cấu trúc chuỗi nguồn. Ý tưởng cốt lõi của ACO là sử dụng một tập hợp các "kiến nhân tạo" để cùng nhau xây dựng các lời giải tiềm năng. Mỗi con kiến di chuyển trên một đồ thị cấu trúc, nơi các đỉnh và cạnh đại diện cho các thành phần của lời giải. Trong quá trình di chuyển, kiến để lại một chất hóa học gọi là "vết mùi" (pheromone). Những đường đi dẫn đến lời giải tốt hơn sẽ được tăng cường nhiều vết mùi hơn, qua đó thu hút các con kiến khác đi theo trong các vòng lặp sau. Sự kết hợp giữa thông tin heuristic (kinh nghiệm cục bộ) và thông tin từ vết mùi (kinh nghiệm toàn cục) giúp đàn kiến hội tụ về những lời giải chất lượng cao. Việc áp dụng thuật toán ACO vào bài toán cấu trúc chuỗi nguồn đòi hỏi phải thiết kế một đồ thị cấu trúc phù hợp, xác định cách kiến xây dựng lời giải tuần tự, và lựa chọn một quy tắc cập nhật mùi hiệu quả. Luận văn đã đề xuất một mô hình đồ thị với m cột, tương ứng với độ dài chuỗi gen, và 2^k hàng, đại diện cho tất cả các tổ hợp có thể có của một cột trong ma trận chuỗi nguồn. Cách tiếp cận này cho phép thuật toán ACO khám phá một không gian lời giải rộng lớn và tránh được các điểm tối ưu cục bộ mà thuật toán RecBlock thường gặp phải, từ đó tìm ra cấu trúc chuỗi nguồn tối ưu hơn.

3.1. Nguyên lý hoạt động cơ bản của thuật toán ACO

Thuật toán ACO hoạt động dựa trên cơ chế học tăng cường (reinforcement learning). Ban đầu, các con kiến xây dựng lời giải một cách ngẫu nhiên. Sau mỗi vòng lặp, chất lượng của các lời giải được đánh giá (trong trường hợp này là tổng số điểm ngắt). Các cạnh hoặc đỉnh thuộc về lời giải tốt nhất sẽ được "thưởng" bằng cách tăng cường vết mùi. Đồng thời, một phần vết mùi trên tất cả các đường đi sẽ bị "bay hơi". Quá trình này tạo ra một vòng lặp phản hồi tích cực: các đường đi tốt sẽ ngày càng trở nên hấp dẫn hơn, hướng việc tìm kiếm của đàn kiến về những vùng hứa hẹn trong không gian lời giải. Điều này giúp cân bằng giữa việc khai thác (exploitation) các lời giải tốt đã biết và khám phá (exploration) các vùng mới.

3.2. Xây dựng đồ thị cấu trúc và lời giải tuần tự cho bài toán

Để giải bài toán cấu trúc chuỗi nguồn, một đồ thị cấu trúc được xây dựng. Đồ thị này bao gồm m tầng, mỗi tầng tương ứng với một cột của ma trận chuỗi nguồn. Mỗi tầng có 2^k đỉnh, mỗi đỉnh đại diện cho một vector cột nhị phân có độ dài k. Một con kiến sẽ xây dựng một lời giải bằng cách đi qua đồ thị từ tầng 1 đến tầng m, tại mỗi tầng chọn một đỉnh. Hành trình hoàn chỉnh của một con kiến sẽ tạo thành một ma trận F[k x m], chính là một bộ chuỗi nguồn tiềm năng. Việc lựa chọn đỉnh tiếp theo của kiến dựa trên xác suất, được tính toán từ nồng độ vết mùi và thông tin heuristic tại đỉnh đó. Cách xây dựng này đảm bảo mọi lời giải được tạo ra đều hợp lệ.

IV. Phương pháp cải tiến ACO trong Cấu trúc chuỗi nguồn gen

Để tối ưu hóa hiệu suất của thuật toán ACO cho bài toán cấu trúc chuỗi nguồn, việc lựa chọn quy tắc cập nhật mùi là vô cùng quan trọng. Quy tắc này quyết định chiến lược học của thuật toán và ảnh hưởng trực tiếp đến khả năng hội tụ và chất lượng lời giải cuối cùng. Luận văn không chỉ áp dụng ACO một cách cơ bản mà còn đi sâu vào việc so sánh và triển khai các biến thể cập nhật mùi tiên tiến. Hai thuật toán được tập trung nghiên cứu là Max-Min Ant System (MMAS) và một phiên bản cải tiến của nó, Smoothed Max-Min Ant System (SMMAS). MMAS là một biến thể mạnh mẽ của ACO, trong đó chỉ có con kiến tìm được lời giải tốt nhất trong vòng lặp (hoặc tốt nhất từ đầu đến giờ) được phép cập nhật vết mùi. Ngoài ra, MMAS còn giới hạn nồng độ vết mùi trong một khoảng [τ_min, τ_max] để tránh tình trạng hội tụ quá sớm, hay còn gọi là tắc nghẽn. Tuy nhiên, MMAS vẫn có thể khiến việc tìm kiếm trở nên quá tập trung vào một lời giải tốt duy nhất. Để khắc phục nhược điểm này, luận văn đã triển khai thuật toán SMMAS do Đỗ Đức Đông và Hoàng Xuân Huấn đề xuất. SMMAS là một quy tắc cập nhật mùi "trơn", cho phép giảm vết mùi ở các cạnh không thuộc lời giải tốt một cách từ từ hơn. Điều này giúp duy trì sự đa dạng trong quần thể lời giải và tăng cường khả năng khám phá của thuật toán, đặc biệt là trong các bài toán có không gian tìm kiếm phức tạp như cấu trúc chuỗi nguồn. Việc áp dụng các quy tắc cải tiến này đã chứng minh được sự vượt trội so với các phương pháp trước đó.

4.1. So sánh chi tiết quy tắc cập nhật mùi MMAS và SMMAS

Trong MMAS, vết mùi được cập nhật dựa trên lời giải tốt nhất (G-best). Các cạnh không thuộc lời giải này sẽ có vết mùi giảm nhanh chóng về giá trị tối thiểu τ_min. Điều này có thể làm cho thuật toán trở nên quá tham lam, bỏ qua những vùng tiềm năng khác. Ngược lại, SMMAS sử dụng một quy tắc cập nhật mượt mà hơn. Thay vì chỉ tập trung vào G-best, nó còn quan tâm đến các lời giải gần đúng. Vết mùi trên các cạnh không tối ưu không bị giảm đột ngột, giúp thuật toán duy trì khả năng khám phá lâu hơn. SMMAS cũng đơn giản hóa việc thiết lập tham số, không yêu cầu xác định chính xác giá trị hàm mục tiêu ban đầu như MMAS.

4.2. Ưu điểm vượt trội của thuật toán Max Min trơn SMMAS

Thuật toán SMMAS thể hiện nhiều ưu điểm so với MMAS. Thứ nhất, nó giảm nguy cơ tắc nghẽn bằng cách duy trì sự đa dạng trong việc tìm kiếm. Thứ hai, việc lựa chọn tham số trở nên đơn giản và hợp lý hơn. Thứ ba, về mặt tính toán, SMMAS có độ phức tạp tương đương nhưng thực hiện ít phép toán hơn vì không cần tính hàm mục tiêu trong lượng mùi cập nhật và không cần so sánh để giới hạn vết mùi. Nhờ những cải tiến này, SMMAS trở thành một lựa chọn hiệu quả và mạnh mẽ để giải quyết bài toán cấu trúc chuỗi nguồn, giúp tìm ra lời giải có số điểm ngắt thấp hơn một cách ổn định.

V. Kết quả thực nghiệm So sánh hiệu quả ACO và RecBlock

Để đánh giá hiệu quả của phương pháp đề xuất, luận văn đã tiến hành một loạt thực nghiệm chi tiết, so sánh thuật toán ACO (sử dụng quy tắc cập nhật mùi SMMAS) với thuật toán RecBlock. Các thực nghiệm được thực hiện trên ba bộ dữ liệu chuẩn: random (dữ liệu ngẫu nhiên), evo và ms (dữ liệu được tạo ra dựa trên mô hình tiến hóa). Các bộ dữ liệu này có kích thước đa dạng, với số lượng tái tổ hợp n từ 30 đến 50 và độ dài chuỗi gen m từ 2n đến 5n. Kết quả thực nghiệm đã cho thấy một cách rõ ràng sự vượt trội của thuật toán ACO. Trong hầu hết các trường hợp, ACO đều tìm ra lời giải có tổng số điểm ngắt thấp hơn đáng kể so với RecBlock. Trung bình, thuật toán ACO cho kết quả tốt hơn khoảng 5% so với RecBlock trên tất cả các bộ dữ liệu. Sự khác biệt này có thể được giải thích bởi cơ chế hoạt động. RecBlock là một thuật toán tham lam, chỉ chạy một lần và đưa ra quyết định dựa trên thông tin cục bộ. Trong khi đó, thuật toán ACO kết hợp cả thông tin heuristic và cơ chế học tăng cường thông qua vết mùi, cho phép nó khám phá không gian lời giải một cách toàn diện hơn và thoát khỏi các điểm tối ưu cục bộ. Bên cạnh đó, luận văn cũng so sánh hiệu quả giữa các quy tắc cập nhật mùi khác nhau trong ACO, như ACS, MMAS và SMMAS. Kết quả một lần nữa khẳng định rằng SMMAS thường mang lại kết quả ổn định và tốt nhất. Những kết quả thực nghiệm này cung cấp bằng chứng vững chắc cho thấy tối ưu hóa đàn kiến là một hướng tiếp cận đầy hứa hẹn và hiệu quả cho bài toán cấu trúc chuỗi nguồn.

5.1. Phân tích chi tiết hiệu quả trên các bộ dữ liệu chuẩn

Trên bộ dữ liệu random, evo, và ms, thuật toán ACO liên tục cho ra số điểm ngắt trung bình thấp hơn RecBlock. Ví dụ, với bộ dữ liệu rnd_30_60 và k=5, ACO đạt 435.4 điểm ngắt so với 456.2 của RecBlock. Tương tự, trên bộ dữ liệu tiến hóa evo_30_60, ACO chỉ có 202.1 điểm ngắt trong khi RecBlock là 211. Sự chênh lệch này càng rõ rệt khi kích thước bài toán tăng lên. Điều này cho thấy khả năng mở rộng và tính mạnh mẽ của thuật toán ACO khi xử lý các vấn đề phức tạp trong tin sinh học.

5.2. Đánh giá tính tối ưu của ACO so với thuật toán cũ

Sự vượt trội của ACO so với RecBlock nằm ở khả năng học hỏi và thích nghi. RecBlock đưa ra quyết định "một lần và mãi mãi" cho mỗi cột, trong khi ACO liên tục tinh chỉnh lời giải qua nhiều vòng lặp. Cơ chế vết mùi cho phép các "kinh nghiệm" tốt được chia sẻ trong cả đàn kiến, hướng việc tìm kiếm đến những vùng có khả năng chứa lời giải tối ưu toàn cục. Mặc dù ACO đòi hỏi thời gian tính toán nhiều hơn do phải chạy lặp lại, nhưng sự cải thiện về chất lượng lời giải đã hoàn toàn chứng minh giá trị của phương pháp này trong việc giải quyết bài toán cấu trúc chuỗi nguồn.

Trích đoạn nội dung tài liệu

Chương 1: Trình bày sơ lược các khái niệm sinh học, phát biểu bài toán cấu trúc chuỗi nguồn. Giới thiệu một vài thuật toán giải quyết bài toán, trình bày lại thuật toán RecBlock. Chương 2: Giới thiệu thuật toán Ant colony optimization (ACO) và một vài thuật toán cập nhật mùi khác nhau trong ACO. Ví dụ về bài toán người chào hàng giải quyết bằng thuật toán ACO.

Chương 3: Đề xuất thuật toán mới, đó là thuật toán Ant colony optimization (ACO) để giải quyết bài toán cấu trúc chuỗi nguồn. Đưa ba quy tắc cập nhật mùi khác nhau đó là ACS, MMAS, SMMAS để giải quyết bài toán. Chương 4: Đưa ra kết quả thực nghiệm của luận văn, so sánh kết quả của thuật toán ACO với các quy tắc cập nhật mùi khác nhau, so sánh kết quả của thuật toán ACO với thuật toán RecBlock. TIEU LUAN MOI download : [e-mail] 10 CHƢƠNG I.

BÀI TOÁN CẤU TRÚC CHUỖI NGUỒN 1. Một số khái niệm trong sinh học 1. Một số khái niệm về di truyền Nhiễm sắc thể: Là một cấu trúc trong tế bào chứa hai loại thông tin gồm chuỗi DNA và Protein. Trong đó chuỗi DNA mang thông tin di truyền xác định chức năng và đặc điểm của sinh vật, Protein quyết định đến chức năng và quá trình phát triển của sinh vật.

Tập hợp tất các nhiễm sắc thể của một sinh vật được gọi là hệ gen của sinh vật đó.1 Cấu trúc nhiễm sắc thể Chuỗi DNA (Deoxyribonucleic Acid): Là một chuỗi cấu trúc xoắn kép gồm hai sợi liên kết, bắt cặp với nhau (A-T, G-C). Trên mỗi một sợi được biểu diễn bởi một xâu kí tự chứa 4 loại kí tự: A,T,G,C (tên viết tắt của 4 loại nucleotide). Ví dụ, xâu kí tự “CAGTTGACGGCGAACCGTGCGAGCAGACGGTCGTT“ là một chuỗi DNA. Gen: Là một đoạn DNA mang thông tin hướng dẫn tổng hợp protein và có một vị trí nhất định trên nhiễm sắc thể.

Gen chịu trách nhiệm về những đặc điểm di truyền.2 Minh họa gen trên nhiễn sắc thể Alen: Các dạng khác nhau của một gen (không cùng xảy ra) nằm tại cùng một vị trí xác định trên một nhiễm sắc thể cụ thể. Locus: Vị trí riêng biệt của một đoạn DNA mang thông tin (hay còn gọi là gen) trên nhiễm sắc thể. Nhiều locus được gọi là loci. TIEU LUAN MOI download : [e-mail] 11 SNP: Được viết tắt của “single nucleotide polymorphism” được gọi là đa hình đơn nucleotide (đọc là sờ-níp ), là những biến thể trình tự DNA xảy ra khi một đơn nucleotide (A, T, C, hoặc G) trong trình tự bộ gen bị thay đổi.

Được minh họa bằng hình ả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 Di truyền: là hiện tượng chuyển những tính trạng của cha mẹ cho con cái thông qua gen của bố mẹ. 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, gen thừa nhận mang thông tin sinh học (hay thông tin di truyền). Thông tin di truyền: là các thông tin được mã hóa trong các bộ nucleotide, được di truyền từ thế hệ này sang thế hệ khác ở cấp độ phân tử thông qua các hoạt động nhân đôi DNA. Phép lai tạo: là quá trình hình thành nhiễm sắc thể (NST) mới trên cơ sở NST cha mẹ bằng cách ghép một hay nhiều đoạn gen của hai hay nhiều NST cha mẹ với nhau.

Quá trình đột biến DNA Theo thuyết tiến hóa của Darwin thì các loài sinh vật đều tiến hóa từ một tổ tiên chung [4]. Hệ gien của các sinh vật bị biến đổi theo thời gian trong quá trình tiến hóa dưới tác động của nhiều yếu tố khác nhau và có thể dẫn đến việc tạo ra các loài sinh vật mới. TIEU LUAN MOI download : skknchat@gmail. Minh họa quá trình tiến hóa của các loài từ một tổ tiên chung Hai trình tự tương đồng: Hai trình tự DNA của hai sinh vật khác nhau gọi là tương đồng nếu như chúng cùng tiến hóa từ một trình tự DNA tổ tiên chung.

Quá trình đột biến của các trình tự DNA: Trong quá trình tiến hóa, các nucleotit trên trình tự DNA có thể bị đột biến. Ba phép đột biến là: đột biến thay thế, đột biến mất, đột biến thêm Hình 1. Quá trình đột biến giữa hai trình tự DNA Hình 1.5 minh họa quá trình đột biến của hai trình tự X = “AGGTGGT” và Y = “ACGGTGG” từ một trình tự DNA tổ tiên chung XY = “ACGGTGGT”. Các phép đột biến trên trình tự DNA trong quá trình tiến hóa sẽ làm cho hệ gien của các loài sinh vật khác nhau cả về nội dung cũng như độ dài.

Các cá thể của cùng TIEU LUAN MOI download : [e-mail] 13 một loài (ví dụ hai người) cũng có hệ gien khác nhau. Tuy nhiên, sự khác biệt giữa hệ gien của hai người vào khoảng 0. Chính sự khác biệt 0.1% này tạo ra sự khác biệt giữa hai người khác nhau. Đột biến giữa hai trình tự prôtêin: Các đột biến nuclêotít trên các trình tự DNA trong quá trình tiến hóa sẽ dẫn đến các đột biến trên các trình tự axít amin mà chúng mã hóa.

Các đột biến giữa hai trình tự prôtêin cũng có thể xuất hiện trong quá trình tổng hợp prôtêin từ các trình tự DNA. Ví dụ hai trình tự DNA X = “CCTGAGCCAATATTGATGAA” và Y = “CCGGAGCCAACTATTGTT" sẽ mã hóa hai prôtêin tương ứng X = “PEPTIDE” và Y = “PEPTV”. Khái quát về các Haplotype đƣợc tạo từ các tái tổ hợp Một haplotype của n vị trí là một chuỗi các nucleotide kích thước m. Nó mô hình một đoạn nhiễm sắc thể với sự đa hình do sự thay thế nucleotide, được gọi là đa hình đơn nucleotide (SNP).

SNPs trong một quần thể chỉ có hai nucleotide được quan sát thấy ở mỗi vị trí: các alen của tổ tiên và alen mới. Sự đa dạng của một Haplotype đại diện giống như một chuỗi các vị trí đa hình đơn trong trình tự DNA [12]. Trong quá trình tái tổ hợp các vị trí tăng lên theo cấp số nhân. Để tìm ra nguyên nhân của việc tái tổ hợp được so sánh với các vị trí đa hình và là vô cùng khó.

Tuy nhiên trong bộ gen của người mỗi Haplotype đều đa dạng và có những Haplotype chiếm ưu thế dùng để đại diện cho việc tìm ra những Haplotype tổ tiên. Khoảng cách giữa các thế hệ có thể giảm vì có thể tiến hành thực hiện xây dựng. Một sự tái tổ hợp giữa hai haplotype X và Y có thể được mô hình hóa như một hoạt động phá vỡ và trao đổi các phần đối diện của X và Y. Tức là nó là hoạt động của dạng: X5X3, Y5Y3  X5Y3, Y5X3 với X = X5X3, Y = Y5Y3 (biểu thị 5 và 3 là các phân đoạn của X và Y và X5, Y5 cũng như Y3, X3 có độ dài là giống nhau.

Trong mô hình của con người, chỉ có một trong các haplotype kết quả được truyền đi. Vì vậy, một sự tái tổ hợp có thể được biểu diễn như X, Y  Z, Z là 1 tái tổ hợp. Cho C = {C1, C2, …, Ch} là một tập các Haplotype chung và R là một tái tổ hợp mới. Vấn đề là phải tìm một lộ trình tái tổ hợp tối thiểu (tối thiểu của chuỗi recombinations) tạo ra từ một tập hợp con CR của C.

Một tái tổ hợp X, Y  Z trong 1 lộ trình như sau: X and/or Y trong CR hoặc được tạo từ tái tổ hợp trước đó của các phần tử CR. R là alen với C nếu và chỉ nếu, cho vị trí bất kỳ i trong R, có tồn tại một haplotype Ck của C như vậy mà R[i] = Ck[i]. Ở đây, cho bất kỳ haplotype X, X[i] biểu thị phần tử i của X. Ví dụ, các haplotype: R = C A C T T G A A C G Alen với C = {C1, C2, C3, C4, C5}: TIEU LUAN MOI download : [e-mail] 14 C1 = A C G T C T G A T T C2 = C A G A T G G A C G C3 = C C G A T G G C C G C4 = A A C T T T G A C T C5 = A C C T C G A A T G Nếu R không alen với C, R có thể không được tạo từ tái tổ hợp của C.

các vị trí không alen yêu cầu một đột biến mới. Ngược lại, được hiểu là R alen với C và R được tạo bằng các vị trí của tái tổ hợp C. Như vậy chúng ta thu được một tập các Hapotype như bảng (1. Mỗi haplotype là một xâu độ dài m của các ký tự {0, 1}.

Ký tự 0 biểu thị mã hóa alen dạng tự nhiên và ký tự 1 biểu thị alen dạng biến dị. Tập HAP tƣơng đƣơng với haplotype C Hk pos 1 2 3 4 5 6 7 8 9 10 HAP1 0 0 0 1 0 0 0 1 0 0 HAP2 1 1 0 0 1 1 0 1 1 1 HAP2 1 0 0 0 1 1 0 0 1 1 HAP4 0 1 1 1 1 0 0 1 1 0 HAP5 0 0 1 1 0 1 1 1 0 1 Khái niệm về điểm ngắt: Ngoài tế bào, các nhiễm sắc thể kết hợp trong các tế bào của con người. Có một NST từ bố, và một trong những NST khác từ phía của người mẹ. Nhưng thế hệ của NST trong quá trình chuyển giao không phải là tĩnh.

Trong quá trình hình thành trứng và tinh trùng, NST tái tổ hợp đó là sự tích tụ của các mảnh vỡ NST với nhau và trao đổi. Hai mảnh vỡ liên tiếp nhau không cùng một NST thì được gọi là điểm ngắt. Sau nhiều thế hệ, thông qua các sự kiện tái tổ hợp lặp đi lặp lại, các mảnh vỡ nhiễm sắc thể ban đầu của tổ tiên đã bị phá vỡ. Một số mảnh vỡ nhiễm sắc thể của tổ tiên trong các chuỗi DNA của nhiều thế hệ con cháu xuất hiện.

Những phần này là haplotype, nhà di truyền học có thể sử dụng nó để tìm kiếm bệnh hoặc gen liên quan đến đặc điểm quan trọng về mặt y khoa khác. TIEU LUAN MOI download : skknchat@gmail. Phát biểu bài toán cấu trúc chuỗi nguồn Trong nghiên cứu về sự tiến hóa, việc xây dựng lại cấu trúc chuỗi nguồn có một ý nghĩa lớn với lĩnh vực sinh học. Mục tiêu của bài toán là tìm ra chuỗi gen di truyền thích hợp được thiết lập để đạt được chuỗi di truyền của cá thể.

Việc thiết lập các chuỗi gen này được xem là mô hình của bài toán cấu trúc chuỗi nguồn, trong đó phải tìm ra bộ chuỗi gen mà mỗi cá thể của nó đều đạt được từ việc tái tạo chuỗi gen và giảm thiểu số lượng lai ghép.