MỞ ĐẦU Nghiên cứu về mối liên kết giữa gene và bệnh ở người là một trong những vấn đề nghiên cứu thuộc lĩnh vực Tin sinh học, một trong những lĩnh vực khoa học liên ngành đang thu hút được sự quan tâm của nhiều nhà khoa học thuộc nhiều lĩnh vực có liên quan, trong đó có chuyên ngành “Khoa học máy tính”. Lựa chọn tag SNP (tag SNP selection) là bài toán có ý nghĩa quan trọng trong nghiên cứu về liên kết giữa gene và bệnh ở người - nhằm tìm ra các gene gây ra kiểu hình bệnh nào đó, hướng tới việc tìm cách điều trị phù hợp. Bài toán lựa cho ̣n tag SNP đã đươ ̣c chứng minh là bài toán thuộc lớp NP- khó [20], thuộc thể loại các bài toán tối ưu tổ hợp (sau đây viết tắt là TƯTH) và hiện nay việc lựa chọn phương pháp giải bài toán trên đang là vấn đề được quan tâm của các nhà nghiên cứu. Với các bài toán TƯTH, trừ các bài toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thường không thể tìm được lời giải tối ưu.
Đối với các bài toán cỡ lớn không có phương pháp giải đúng, hiện nay, người ta thường tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên như giải thuật di truyền (Genetic Algorithm - GA), tối ưu bầy đàn (Particle Swarm Optimization -PSO)… Trong các phương pháp mô phỏng tự nhiên, tối ưu đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận metaheuristic tương đối mới, được giới thiệu bởi Dorigo năm 1991 đang được nghiên cứu và ứng dụng rộng rãi cho các 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. Trên đường đi, mỗi con kiến thực để lại một vết hoá chất gọi là vết mùi 1 (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 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. 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. Bài luận văn này trình bày phương pháp tối ưu hóa đàn kiến ACO để giải quyết bài toán lựa chọn tag SNP (tag SNP selection). 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ể.
TỔNG QUAN VỀ TỐI ƯU ĐÀN KIẾN VÀ BÀI TOÁN LỰA CHỌN TAG SNP 1. Tìm hiểu về SNP 1. SNP (Single Nucleotide Polymorphisms) Tính cách hay đặc điểm con người đến từ một chất di truyền được gọi là DNA, chứa tất cả bốn loại cơ sở, cụ thể là, Adenine (A), thymine (T), Guanine (G) và Cytosine (C) được liên kết trong một sợi dài. Thực tế rằng con người khác biệt nhau, chẳng hạn như hiển thị mức độ bệnh khác nhau hoặc phản ứng khác nhau với thuốc, là do trình tự cơ sở khác nhau trên sợi DNA.
SNP (được phát âm là snip) được viết tắt từ chữ Single Nucleotide Polymorphisms, là một loại lệch thứ tự DNA được đặc trưng bởi sự thay đổi của một nucleotide trong một gen, gây ra các gen là khác nhau từ các bộ gen của các sinh vật khác cùng loài, hoặc là khác nhau từ nhiễm sắc thể khác trong cùng sống sinh vật. Ví dụ, đoạn DNA ở vị trí tương đương từ hai người khác nhau như AAGCCTA và AAGCTTA (hình 1) có thể được tìm thấy là có một sự khác biệt ở một nucleotide. Như vậy, có thể nói rằng SNPs này chứa hai alen: C và T và hầu hết SNPs chỉ có hai alen. Một SNP (Single Nucleotide Polymorphisms)[28] Đối với một biến thể được coi là một SNP, nó phải xảy ra trong ít nhất 1% dân số.
SNPs, tạo nên khoảng 90% của tất cả các biến thể di truyền của con người, xảy ra mỗi 100 đến 300 căn cứ dọc theo hệ gen của con người 3-tỷ-base. Hai trong số ba mỗi SNPs liên quan đến sự thay thế của cytosine (C) với thymine (T). SNPs có thể xảy ra trong khu vực của bộ gen mã hóa (gen) và không mã hoá. Nhiều người SNPs không có ảnh hưởng đến chức năng tế bào, nhưng các nhà khoa học tin rằng những người khác có thể predispose người bệnh hoặc ảnh hưởng đến phản ứng của họ với một loại thuốc.
SNPs diễn ra bình thường trong suốt DNA của một người. Trung bình xảy ra một lần trong mỗi 300 nucleotide, có nghĩa là có khoảng 10 triệu SNPs trong hệ gen của con người. Thông thường nhất, những biến thể này được tìm thấy trong DNA giữa các gen. Nó được xem như là đánh dấu sinh học, các nhà khoa học giúp xác định vị trí các gen liên quan đến bệnh.
Khi SNPs xảy ra trong gen hoặc trong một khu vực gần một gen quy định, nó có thể có vai trò trực tiếp đến sự xuất hiện bệnh bằng cách ảnh hưởng đến chức năng của gen. 4 Mặc dù hơn 99% trình tự ADN của con người đều giống nhau, sự thay đổi trong chuỗi DNA có thể có tác động lớn đến việc làm thế nào con người bệnh, các yếu tố môi trường, chẳng hạn như vi khuẩn, virus, độc tố, các hóa chất, các loại thuốc và các liệu pháp điều trị khác. Điều này làm cho SNPs có giá trị cho nghiên cứu y sinh học và phát triển các sản phẩm dược phẩm hoặc chẩn đoán y khoa. SNPs cũng tiến hóa ổn định, không thay đổi nhiều từ thế hệ này sang thế hệ khác làm cho chúng ta dễ dàng hơn khi nghiên cứu dân số.
SNP là những biến dạng của chuỗi DNA được tìm thấy với tần suất cao trong genome người (Taillon – Miller và ctv. Chúng ta có thể sử dụng SNP marker để phân lập các yếu tố di truyền có liên quan đến tính trạng bệnh lý vô cùng phức tạp (Taillon – Miller và ctv. Người ta có thể dự đoán 100.000 hoặc nhiều hơn nữa SNP marker (trong quãng 30-kb, hoặc 5 marker cho một gen) trong genome người (Collins và ctv. Những phương pháp đánh giá kiểu gen với kết quả cao đòi hỏi một kiến thức về chuỗi trình tự rất chính xác của SNP.
Do đó, bất cứ công bố nào về SNP phải hàm chứa hai nội dung: (1) Xác định chuỗi trình tự DNA. (2) Tần số alen. Phương pháp xác định SNP Có hai phương pháp để tạo ra SNP, một là dùng trực tiếp mã trình tự di truyền và thứ hai là phân biệt các đột biến điểm thông qua dùng tách sắc ký lỏng (DHPLC). Thông thường dùng primer để thiết kế mã trình tự và các đoạn khuyết đại khoảng 500 cặp base.
Chúng ta có thể dùng phương pháp PCR tách hai cá thể và trộn các cá thể này chung, sau đó đun nóng và lai để thành lập các 5 dulex tương đồng và dị biệt. Các bước để phân tích axit nucleic bằng SNP như sau: + Phân lập DNA nền + Chọn lựa primer và thiết kế primer để cho khuếch đại trong PCR + Tách SNP trên bước sóng tương thích (DHPLC) + Phối hợp số liệu, mã trình tự DNA và cloning Theo phân tích chi tiết chuỗi trình tự của những phần nào đó trong genome, những trình tự DNA này từ hai cá thể khác nhau phần lớn đều giống nhau, với số cặp base khác biệt nhau nằm trong khoảng cho phép 500 – 1000bp. Một cặp base ở tại vị trí nào đó biểu thị sự khác nhau của cá thể có tính chất rất phổ biến và một cặp base khác là “variant” ít phổ biến hơn ở cùng một vị trí. Nếu cặp base có tính chất ít phổ biến hơn xuất hiện xuất hiện với xác suất nhỏ hơn 1% trong quần thể, người ta định nghĩa vị trí của cặp base đó là vị trí một SNP.
Hiện nay, người ta công bố 3.000 SNP trong genome người (Rusell 2002), nhiều hơn bất cứ DNA marker đã được công bố trước đó. Kiểu đa hình như vậy vô cùng quan trọng trong di truyền người vì chúng đại diện cho hơn 98% tất cả đa hình DNA. Các alen của một SNP có thể dễ dàng được xem xét bởi phân tích lai với phân tử oligonucleotide nào đó. Tính chất của SNP SNP có tính chất “diallelic” trong quần thể và tần số alen của nó có thể được ước đoán dễ dàng trong bất cứ quần thể nào, thông qua một loạt xét nghiệm kỹ thuật (Kwor và ctv.
SNP là những marker có tính ổn định rất cao về mặt di truyền. Là sản phẩm của PCR. Được tìm thấy với tần suất cao nhất trong genome người. Ứng dụng và triển vọng của nghiên cứu SNP + SNPs bản đồ Người ta đã phát hiện một chiến lược nghiên cứu giúp cho việc phát hiện nhanh chóng những SNP từ số liệu lưu trữ EST (Expressed Sequence Tag) (Picuolt – Newberg và ctv.
Sự kiện phát triển in vitro nhằm khuếch đại những trình tự ở vị trí đặc biệt, ví dụ như PCR và khám phá marker có tính đa hình và có thông tin di truyền cao như microsatallite, STR (short tandem repeat), sự kiện như vậy đã và đang tạo điều kiện thuận lợi để chúng ta sáng tạo ra những bản đồ di truyền có mật độ thấp (lom density maps) của người, ứng dụng có hiệu quả trong lĩnh vực y khoa, thí dụ xét nghiệm bệnh u xơ, bệnh Huntington, bệnh tiểu đường, … (Broman và ctv. Các nhà khoa học tin rằng SNP bản đồ sẽ giúp họ xác định được nhiều gen liên quan với các bệnh phức tạp như ung thư, bệnh tiểu đường, bệnh mạch máu, và một số hình thức của bệnh tâm thần. 7 Một vài nhóm làm việc để tìm SNPs và cuối cùng tạo ra SNP bản đồ hệ gen của con người. Trong số đó là Mỹ Human Genome Project (HGP) và một nhóm lớn của các công ty dược phẩm được gọi là SNP Consortium, dự án TSC.
Khả năng trùng lặp giữa các nhóm nhỏ là khó xảy ra vì có khoảng 3 triệu SNPs, và phần thưởng tiềm năng của một bản đồ SNP là cao. Ngoài ý nghĩa nghiên cứu pharmacogenomic trong chẩn đoán, y sinh học, SNP bản đồ còn giúp để xác định hàng ngàn các dấu hiệu bổ sung trong bộ gen, do đó hướng nghiên cứu của bản đồ bộ gen là rất lớn. + Làm thế nào SNPs có thể được sử dụng như là yếu tố nguy cơ phát triển bệnh?