Lựa Chọn Tag SNP Dựa Trên Phương Pháp Tối Ưu Đàn Kiến

SNP (Single Nucleotide Polymorphism) là biến thể di truyền phổ biến, thể hiện sự khác biệt nucleotide trong trình tự DNA. Chúng xảy ra khi một nucleotide duy nhất (A, T, C, hoặc G) thay thế bằng một nucleotide khác ở một vị trí cụ thể trong bộ gene. SNP chiếm khoảng 90% biến thể di truyền ở người. Chúng có thể xảy ra ở vùng mã hóa hoặc không mã hóa của gene. Nhiều SNP không ảnh hưởng đến chức năng tế bào, nhưng một số có thể ảnh hưởng đến sự nhạy cảm với bệnh tật hoặc phản ứng với thuốc. Tần số SNP phải lớn hơn 1% trong dân số để được coi là biến thể. Theo nghiên cứu, có đến 10 triệu SNP trong hệ gene người.

Lựa chọn tag SNP là quá trình chọn một tập hợp nhỏ SNP đại diện cho một lượng lớn thông tin di truyền. Điều này rất quan trọng trong các nghiên cứu liên kết gene-bệnh vì nó giảm thiểu chi phí và công sức cần thiết để phân tích bộ gene. SNP không gây bệnh, nhưng có thể giúp xác định khả năng phát triển bệnh. Từ đó tìm ra các gene liên quan đến bệnh phức tạp như tim mạch, tiểu đường. Xác định vai trò của yếu tố di truyền cho phép đánh giá vai trò của yếu tố môi trường. Theo nghiên cứu của Taillon – Miller, SNP marker có thể được sử dụng để phân lập các yếu tố di truyền liên quan đến tính trạng bệnh lý phức tạp.

Bài toán lựa chọn tag SNP thuộc lớp NP-khó, đòi hỏi phương pháp giải quyết hiệu quả. Các phương pháp hiện tại bao gồm các thuật toán dựa trên heuristic, thuật toán tiến hóa, và kỹ thuật khai thác dữ liệu. Các thuật toán dựa trên khoảng cách haplotype cũng được sử dụng. Tối ưu hóa đàn kiến là một cách tiếp cận metaheuristic mới, được giới thiệu bởi Dorigo, được nghiên cứu ứng dụng cho bài toán TƯTH. Các thuật toán ACO mô phỏng cách tìm đường đi của các con kiến thực, mỗi con kiến để lại pheromone trail và theo vết mùi của các con kiến khác để tìm đường đi. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được chọn.

Kiến tự nhiên giao tiếp thông qua pheromone, một chất hóa học được tiết ra khi di chuyển. Các con kiến khác theo vết mùi này, và đường đi có nhiều pheromone hơn có khả năng được chọn hơn. Trong ACO, kiến nhân tạo mô phỏng hành vi này. Kiến nhân tạo di chuyển qua không gian giải pháp, và “vết mùi” đại diện cho chất lượng của giải pháp tương ứng. Thuật toán cập nhật pheromone dựa trên chất lượng của các giải pháp được tìm thấy bởi các kiến. Thuật toán ACO tìm đường đi ngắn nhất từ tổ tới nguồn thức ăn. Theo ý tưởng đó, các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (heuristic) và học tăng cường qua các vết mùi của các con kiến nhân tạo để giải các bài toán TƯTH bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng của bài toán.

Giải thuật ACO cho bài toán tối ưu tổ hợp bao gồm các bước sau: Khởi tạo pheromone trên các cạnh của đồ thị. Mỗi kiến xây dựng một giải pháp bằng cách di chuyển qua đồ thị, chọn cạnh dựa trên pheromone và thông tin heuristic. Sau khi tất cả kiến đã xây dựng giải pháp, pheromone được cập nhật. Các cạnh thuộc giải pháp tốt hơn được tăng cường pheromone, trong khi pheromone trên các cạnh khác bay hơi. Quá trình này lặp lại cho đến khi đạt được một tiêu chí dừng. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được các con kiến chọn. Nhờ cách giao tiếp gián tiếp này đàn kiến tìm được đường đi ngắn nhất từ tổ tới nguồn thức ăn.

Hiệu suất của ACO phụ thuộc vào các tham số quan trọng. Thông tin Heuristic ảnh hưởng đến quyết định ban đầu của kiến. Lượng kiến ảnh hưởng đến khả năng khám phá không gian giải pháp. Tham số bay hơi (ρ) kiểm soát tốc độ loại bỏ pheromone cũ. Giá trị ρ cao dẫn đến khám phá rộng hơn, trong khi giá trị thấp dẫn đến khai thác các giải pháp tốt hiện có. Việc điều chỉnh các tham số này là rất quan trọng để đạt được hiệu suất tốt nhất. Luận văn tập trung nghiên cứu về cách tiếp cận giải bài toán lựa chọn tag SNP, phương pháp và thuật toán giải bài toán này kèm theo chương trình minh họa thuật toán với bộ dữ liệu cụ thể.

Trong thuật toán ACO, mỗi kiến xây dựng một giải pháp bằng cách lặp đi lặp lại quyết định chọn một thành phần của giải pháp. Quyết định này dựa trên pheromone và thông tin heuristic. Sau khi tất cả các kiến đã hoàn thành giải pháp, pheromone được cập nhật. Các thành phần của giải pháp tốt nhất được tăng cường pheromone, trong khi pheromone trên các thành phần khác bay hơi. Quá trình này được lặp lại cho đến khi đạt được một tiêu chí dừng. Hiệu chỉnh quy tắc cập nhật mùi bằng SMASS giúp tránh hội tụ sớm.

SMMAS (Smoothed Max-Min Ant System) là một quy tắc cập nhật pheromone cải tiến được sử dụng trong MACA. SMMAS giới hạn nồng độ pheromone trong một phạm vi hẹp ([τmin, τmax]) để ngăn chặn sự hội tụ sớm. SMMAS cũng sử dụng một cơ chế làm mịn để làm giảm sự khác biệt giữa các nồng độ pheromone. Việc này tăng cường khám phá không gian giải pháp và giúp tìm ra các giải pháp tốt hơn. Mã lệnh cho thuật toán MACA được sử dụng để kiểm chứng tính đúng đắn của thuật toán.

Thuật giải MACA bắt đầu bằng việc khởi tạo pheromone trên các cạnh của đồ thị. Sau đó, mỗi kiến xây dựng một tập hợp tag SNP bằng cách lặp đi lặp lại chọn các SNP. Sau khi tất cả các kiến đã hoàn thành tập hợp tag SNP, quy tắc SMMAS được sử dụng để cập nhật pheromone. Quá trình này được lặp lại cho đến khi đạt được một tiêu chí dừng. Cuối cùng, giải pháp tốt nhất được trả về. Thuật toán MACA có thể sử dụng bộ dữ liệu cụ thể.

Các thử nghiệm được thực hiện trên một máy tính với bộ vi xử lý Intel Core i7 và 16GB RAM. Các thuật toán được triển khai trong Java. Các bộ dữ liệu SNP được lấy từ cơ sở dữ liệu HapMap. Các tham số của thuật toán MACA được điều chỉnh bằng cách sử dụng một kỹ thuật tối ưu hóa thử và sai. Bảng 2 và 3 đưa ra kết quả khi số lượng haplotype cố định và số lượng SNP thay đổi. Bảng 3 đưa ra kết quả khi số lượng SNP cố định và số lượng haplotype thay đổi.

Các kết quả thực nghiệm cho thấy rằng MACA có thể tìm thấy các tập hợp tag SNP có độ chính xác cao và kích thước nhỏ. MACA cũng được so sánh với các thuật toán lựa chọn tag SNP khác, và kết quả cho thấy rằng MACA hoạt động tốt hơn so với các thuật toán khác trong nhiều trường hợp. Cụ thể, MACA có thể tìm thấy các tập hợp tag SNP có độ chính xác tương đương hoặc cao hơn so với các thuật toán khác, nhưng với kích thước nhỏ hơn đáng kể. Điều này cho thấy rằng MACA có hiệu quả trong việc tối ưu hóa tổ hợp thông tin di truyền.

Nghiên cứu này đã đóng góp vào lĩnh vực sinh tin học bằng cách cung cấp một phương pháp hiệu quả để lựa chọn tag SNP. Thuật toán MACA có thể được sử dụng để xác định các tập hợp tag SNP có độ chính xác cao và kích thước nhỏ, giúp giảm chi phí và công sức cần thiết cho các nghiên cứu liên kết gene-bệnh. Nghiên cứu này cũng cung cấp một cái nhìn sâu sắc về cách thức hoạt động của thuật toán ACO và cách nó có thể được điều chỉnh để giải quyết các bài toán tối ưu hóa khác nhau.

Các hướng nghiên cứu tiềm năng trong tương lai bao gồm việc ứng dụng thuật toán MACA cho các bài toán sinh tin học khác, chẳng hạn như dự đoán cấu trúc protein và phân tích biểu hiện gene. Cũng có thể nghiên cứu các biến thể khác của thuật toán ACO, chẳng hạn như thuật toán ACO đa mục tiêu, để giải quyết các bài toán lựa chọn tag SNP phức tạp hơn. Ngoài ra, có thể khám phá các phương pháp kết hợp thuật toán MACA với các thuật toán machine learning khác để cải thiện hiệu suất. Đặc biệt là trong bối cảnh Data mining trong di truyền học ngày càng phát triển.