Nghiên cứu thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tương tự nhanh

Luận văn thạc sĩ VNU UET nghiên cứu thuật toán tìm kiếm chuỗi DNA bằng phương pháp tìm kiếm tương tự nhanh, đóng góp cho lĩnh vực máy tính.

• Tác giả: Nguyễn Hoàng Anh
• Người hướng dẫn: Tiến Sĩ Nguyễn Thị Hậu
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nghiên Cứu Thuật Toán Tìm Kiếm Chuỗi DNA Sử Dụng Phương Pháp Tìm Kiếm Tương Tự Nhanh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA
• 1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn
• 1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ
• 1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh
• 1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng
• 1.5. Phƣơng pháp sử dụng mô hình kết hợp chính xác và gần chính xác
• 2. CHƯƠNG 2: THUẬT TOÁN TÌM KIẾM CHUỖI DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM
• 2.1. Mô hình N-Gram
• 2.2. Một số khái niệm
• 2.3. Mô hình ngôn ngữ N-gram
• 2.4. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram
• 2.5. Các phương pháp khắc phục cụm N-Gram phân bố không đều
• 2.6. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA
• 2.7. Phân đoạn DNA
• 2.8. Quá trình tìm kiếm chuỗi và hiển thị kết quả
• 2.9. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram
• 2.10. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram
• 2.11. Cải thiện thời gian tìm kiếm
• 2.12. Tiết kiệm bộ nhớ trong quá trình tìm kiếm
• 3. CHƯƠNG 3: THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP BLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN
• 3.1. Môi trƣờng thực nghiệm
• 3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp Smith-Water Man
• 3.3. Phân tích và đánh giá kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về nghiên cứu thuật toán tìm kiếm chuỗi DNA hiệu quả

Nghiên cứu về thuật toán tìm kiếm chuỗi DNA đã trở thành một lĩnh vực quan trọng trong sinh học và công nghệ thông tin. Với sự phát triển nhanh chóng của công nghệ sinh học, việc phân tích và tìm kiếm các chuỗi DNA ngày càng trở nên cần thiết. Các thuật toán này không chỉ giúp xác định cấu trúc gen mà còn hỗ trợ trong việc phát hiện các bệnh di truyền và nghiên cứu tiến hóa. Tuy nhiên, việc xử lý khối lượng dữ liệu khổng lồ từ các chuỗi DNA đặt ra nhiều thách thức cho các nhà nghiên cứu.

1.1. Định nghĩa và vai trò của chuỗi DNA trong sinh học

Chuỗi DNA (Deoxyribonucleic Acid) là thành phần chính mang thông tin di truyền trong tất cả các sinh vật. Nó bao gồm bốn loại nucleotide: Adenine, Thymine, Cytosine và Guanine. Mỗi nucleotide kết hợp với nhau tạo thành các chuỗi dài, chứa thông tin cần thiết cho sự phát triển và chức năng của sinh vật. Việc tìm kiếm và phân tích các chuỗi DNA giúp hiểu rõ hơn về di truyền và các bệnh lý liên quan.

1.2. Tầm quan trọng của thuật toán trong nghiên cứu DNA

Các thuật toán tìm kiếm chuỗi DNA đóng vai trò quan trọng trong việc phân tích dữ liệu sinh học. Chúng giúp xác định sự tương đồng giữa các chuỗi DNA, từ đó hỗ trợ trong việc phát hiện các gen gây bệnh và nghiên cứu tiến hóa. Sự phát triển của các thuật toán này cũng giúp cải thiện độ chính xác và tốc độ trong việc xử lý dữ liệu lớn.

II. Các thách thức trong việc tìm kiếm chuỗi DNA hiệu quả

Mặc dù có nhiều thuật toán tìm kiếm chuỗi DNA đã được phát triển, nhưng vẫn tồn tại nhiều thách thức trong việc áp dụng chúng vào thực tiễn. Một trong những vấn đề lớn nhất là khối lượng dữ liệu ngày càng tăng, yêu cầu các thuật toán phải có khả năng xử lý nhanh chóng và hiệu quả. Ngoài ra, độ chính xác của các thuật toán cũng là một yếu tố quan trọng, ảnh hưởng đến kết quả nghiên cứu.

2.1. Khó khăn trong việc xử lý dữ liệu lớn

Khối lượng dữ liệu từ các chuỗi DNA ngày càng lớn, điều này đặt ra yêu cầu cao về khả năng lưu trữ và xử lý. Các thuật toán cần phải được tối ưu hóa để có thể xử lý nhanh chóng mà không làm giảm độ chính xác của kết quả.

2.2. Độ chính xác và độ nhạy của thuật toán

Độ chính xác của các thuật toán tìm kiếm chuỗi DNA là rất quan trọng. Một thuật toán có độ nhạy cao sẽ giúp phát hiện ra nhiều gen và cấu trúc di truyền hơn, từ đó cung cấp thông tin hữu ích cho các nghiên cứu y sinh học.

III. Phương pháp tìm kiếm chuỗi DNA hiệu quả nhất hiện nay

Có nhiều phương pháp khác nhau được sử dụng để tìm kiếm chuỗi DNA, mỗi phương pháp có những ưu điểm và nhược điểm riêng. Một số phương pháp nổi bật bao gồm mô hình Markov ẩn, phương pháp Smith-Waterman và BLAST. Mỗi phương pháp này đều có ứng dụng riêng trong việc phân tích và tìm kiếm chuỗi DNA.

3.1. Mô hình Markov ẩn trong tìm kiếm DNA

Mô hình Markov ẩn là một trong những phương pháp phổ biến trong việc tìm kiếm chuỗi DNA. Phương pháp này sử dụng các tham số thống kê để xác định sự tương đồng giữa các chuỗi, giúp cải thiện độ chính xác trong việc phân tích dữ liệu.

3.2. Phương pháp Smith Waterman và ứng dụng của nó

Phương pháp Smith-Waterman là một thuật toán quy hoạch động, được sử dụng để tìm kiếm sự tương đồng cao giữa hai chuỗi DNA. Phương pháp này có độ chính xác cao nhưng yêu cầu thời gian xử lý lớn, điều này có thể là một hạn chế trong một số trường hợp.

3.3. BLAST Phương pháp tìm kiếm nhanh chóng

BLAST (Basic Local Alignment Search Tool) là một trong những công cụ tìm kiếm chuỗi DNA nhanh nhất hiện nay. Phương pháp này cho phép so sánh chuỗi DNA với cơ sở dữ liệu lớn, giúp tìm ra các chuỗi tương đồng một cách nhanh chóng và hiệu quả.

IV. Ứng dụng thực tiễn của thuật toán tìm kiếm chuỗi DNA

Các thuật toán tìm kiếm chuỗi DNA không chỉ có giá trị trong nghiên cứu mà còn có nhiều ứng dụng thực tiễn trong y học, nông nghiệp và khoa học hình sự. Việc phát hiện các gen gây bệnh, kiểm tra huyết thống và nghiên cứu tiến hóa đều dựa vào các thuật toán này.

4.1. Phát hiện gen gây bệnh và ứng dụng y học

Các thuật toán tìm kiếm chuỗi DNA giúp phát hiện các gen liên quan đến bệnh tật, từ đó hỗ trợ trong việc chẩn đoán và điều trị. Việc phân tích chuỗi DNA có thể giúp xác định nguy cơ mắc bệnh và phát triển các phương pháp điều trị hiệu quả.

4.2. Kiểm tra huyết thống và ứng dụng trong pháp y

Xét nghiệm DNA là một ứng dụng phổ biến trong việc kiểm tra huyết thống. Các thuật toán tìm kiếm chuỗi DNA giúp xác định mối quan hệ di truyền giữa các cá nhân, từ đó hỗ trợ trong các vụ án hình sự và các vấn đề pháp lý.

V. Kết luận và tương lai của nghiên cứu thuật toán tìm kiếm chuỗi DNA

Nghiên cứu về thuật toán tìm kiếm chuỗi DNA đang tiếp tục phát triển với nhiều hướng đi mới. Các công nghệ mới như trí tuệ nhân tạo và học máy đang được áp dụng để cải thiện độ chính xác và tốc độ của các thuật toán. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều đột phá trong nghiên cứu sinh học và y học.

5.1. Xu hướng phát triển công nghệ trong tìm kiếm DNA

Công nghệ mới như trí tuệ nhân tạo đang được áp dụng để cải thiện các thuật toán tìm kiếm chuỗi DNA. Những cải tiến này có thể giúp tăng cường độ chính xác và giảm thời gian xử lý dữ liệu.

5.2. Tầm quan trọng của nghiên cứu liên ngành

Nghiên cứu về thuật toán tìm kiếm chuỗi DNA cần sự hợp tác giữa các lĩnh vực như sinh học, công nghệ thông tin và y học. Sự kết hợp này sẽ giúp phát triển các giải pháp hiệu quả hơn cho các vấn đề phức tạp trong nghiên cứu di truyền.

Nội dung chính

Tổng quan nghiên cứu

Việc tìm kiếm chuỗi DNA trong các cơ sở dữ liệu gen ngày càng trở nên quan trọng trong lĩnh vực tin sinh học và y sinh học hiện đại. Với khoảng 3 tỷ base trong bộ gen người và hàng tỷ nucleotide trong các cơ sở dữ liệu gen toàn cầu, việc xử lý, lưu trữ và truy xuất dữ liệu DNA đòi hỏi các thuật toán tìm kiếm hiệu quả về tốc độ và bộ nhớ. Nghiên cứu tập trung vào phát triển thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tìm kiếm tương tự nhanh áp dụng mô hình N-Gram nhằm cải thiện thời gian tìm kiếm và tiết kiệm bộ nhớ so với các phương pháp truyền thống như Smith-Waterman hay BLAST.

Mục tiêu chính của luận văn là xây dựng và đánh giá thuật toán tìm kiếm chuỗi DNA dựa trên mô hình N-Gram, áp dụng cho các bộ dữ liệu gen thực tế từ 3 loài với tổng số 178 gen, trong đó có 120 gen người và 58 gen E. Thuật toán được thiết kế để xử lý các chuỗi DNA dài, phân đoạn thành các đoạn nhỏ 500 ký tự và tách thành các "từ DNA" có độ dài 12 ký tự (12-gram) nhằm tối ưu hóa quá trình truy xuất dữ liệu. Phạm vi nghiên cứu tập trung vào dữ liệu gen định dạng FASTA, phổ biến trong các ngân hàng gen như NCBI.

Ý nghĩa của nghiên cứu thể hiện qua việc cải thiện đáng kể thời gian tìm kiếm (chỉ từ 1 đến 11 giây cho các bộ dữ liệu từ 1MB đến 400MB) và giảm thiểu bộ nhớ sử dụng (từ vài MB đến khoảng 300MB RAM), giúp tăng hiệu quả truy xuất dữ liệu DNA trong các ứng dụng y sinh, khoa học hình sự, và nghiên cứu tiến hóa.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mô hình N-Gram: Là mô hình ngôn ngữ thống kê, trong đó xác suất xuất hiện của một phần tử phụ thuộc vào n phần tử liền trước. Ứng dụng trong phân tích chuỗi DNA, N-Gram giúp phân đoạn chuỗi thành các "từ DNA" có độ dài cố định (n=12) để xây dựng bảng chỉ số tìm kiếm nhanh.

• Phương pháp tìm kiếm tương tự nhanh (Fast Similarity Search): Thuật toán so sánh chuỗi truy vấn với cơ sở dữ liệu dựa trên các đoạn con có điểm số tương tự cao, giảm thiểu thời gian xử lý so với các thuật toán chính xác như Smith-Waterman.

• Mô hình Markov ẩn (Hidden Markov Model - HMM): Mô hình thống kê dùng để mô phỏng quá trình sinh chuỗi DNA, hỗ trợ trong việc đánh giá độ tương đồng và xác suất xuất hiện chuỗi.

• Thuật toán Smith-Waterman: Thuật toán quy hoạch động dùng để tìm kiếm sự tương đồng cục bộ giữa hai chuỗi DNA với độ chính xác cao nhưng chi phí tính toán lớn.

Các khái niệm chính bao gồm: chuỗi nucleotide (A, T, G, C), phân đoạn DNA, chỉ số N-Gram, bảng ma trận điểm số, và các thuật toán tìm kiếm chuỗi.

Phương pháp nghiên cứu

Nguồn dữ liệu sử dụng là các tệp gen định dạng FASTA được trích xuất từ ngân hàng gen NCBI, bao gồm 120 gen người và 58 gen E. Các chuỗi DNA được phân đoạn thành các đoạn nhỏ 500 ký tự để thuận tiện cho việc xử lý và đánh chỉ số.

Phương pháp phân tích gồm hai bước chính:

1. Tiền xử lý dữ liệu: Chia chuỗi DNA thành các đoạn 500 ký tự, đánh ID cho từng đoạn, sau đó tách tiếp thành các "từ DNA" 12 ký tự (12-gram). Các từ này được lưu trữ trong các tệp chỉ số (index files) như *.n-gram, *.idx, *.inv để phục vụ truy xuất nhanh.

2. Tìm kiếm và hiển thị kết quả: Chuỗi truy vấn được nhập từ bàn phím, tách thành các segment 12-gram, sau đó truy xuất các vị trí tương ứng trong tệp chỉ số để xác định các đoạn DNA chứa chuỗi cần tìm. Kết quả được sắp xếp theo số lần xuất hiện và hiển thị chi tiết gồm tên gen, vị trí trong đoạn, tổng số kết quả và thời gian tìm kiếm.

Cỡ mẫu nghiên cứu gồm 11 bộ dữ liệu thử nghiệm với dung lượng từ 1MB đến 400MB, sử dụng máy tính cá nhân thông thường. Phương pháp chọn mẫu dựa trên các gen chuẩn phổ biến trong nghiên cứu sinh học phân tử. Phân tích kết quả dựa trên các chỉ số thời gian xử lý, bộ nhớ sử dụng và độ chính xác tìm kiếm.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tăng tốc độ tìm kiếm đáng kể: Thuật toán tìm kiếm tương tự nhanh áp dụng N-Gram cho thấy thời gian tìm kiếm chỉ từ 1 đến 11 giây trên các bộ dữ liệu từ 1MB đến 400MB, nhanh hơn nhiều so với các phương pháp truyền thống như Smith-Waterman vốn có chi phí thời gian lớn.

2. Tiết kiệm bộ nhớ hiệu quả: Bộ nhớ RAM sử dụng trong quá trình tìm kiếm dao động từ khoảng 1MB đến 308MB tùy theo kích thước dữ liệu, thấp hơn đáng kể so với các thuật toán đòi hỏi lưu trữ ma trận lớn như Smith-Waterman.

3. Độ chính xác tìm kiếm cao: Thuật toán đảm bảo tìm được các đoạn chuỗi DNA tương tự với độ dài 12 ký tự, phù hợp với yêu cầu truy xuất nhanh và chính xác trong các ứng dụng thực tế.

4. Khả năng xử lý dữ liệu lớn và đa mẫu: Thuật toán có thể xử lý đồng thời nhiều mẫu chuỗi DNA, phù hợp với xu hướng giải trình tự thế hệ mới (HTS) với khối lượng dữ liệu khổng lồ.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện về tốc độ và bộ nhớ là do việc áp dụng mô hình N-Gram giúp phân đoạn chuỗi DNA thành các "từ" có độ dài cố định, từ đó xây dựng bảng chỉ số tuần tự và chỉ truy xuất các vị trí liên quan thay vì so sánh toàn bộ chuỗi. So với phương pháp Smith-Waterman, vốn sử dụng ma trận điểm số quy hoạch động với độ phức tạp tính toán cao, thuật toán N-Gram giảm thiểu đáng kể các phép tính không cần thiết.

So sánh với BLAST, thuật toán N-Gram có ưu thế trong việc xử lý dữ liệu lớn với thời gian tìm kiếm nhanh và bộ nhớ sử dụng hợp lý, đồng thời vẫn giữ được độ chính xác tương đối cao. Các phương pháp như Bowtie hay Mpscan cũng có những ưu điểm riêng nhưng thường phức tạp hơn trong cài đặt và yêu cầu phần cứng cao hơn.

Dữ liệu có thể được trình bày qua biểu đồ thời gian tìm kiếm và bộ nhớ sử dụng theo dung lượng dữ liệu, hoặc bảng so sánh chi tiết các chỉ số giữa các thuật toán. Điều này giúp minh họa rõ ràng hiệu quả của phương pháp N-Gram trong thực tế.

Đề xuất và khuyến nghị

1. Triển khai thuật toán N-Gram trong các hệ thống truy xuất gen quy mô lớn: Động từ hành động "triển khai" nhằm mục tiêu giảm thời gian truy xuất dữ liệu gen xuống dưới 10 giây cho các bộ dữ liệu trên 100MB, thực hiện trong vòng 12 tháng, chủ thể là các trung tâm tin sinh học.

2. Phát triển giao diện người dùng thân thiện cho công cụ tìm kiếm DNA: Thiết kế giao diện trực quan giúp người dùng không chuyên có thể nhập chuỗi truy vấn và nhận kết quả nhanh chóng, hoàn thành trong 6 tháng, do nhóm phát triển phần mềm đảm nhiệm.

3. Tối ưu hóa bộ nhớ và xử lý song song: Áp dụng các kỹ thuật tối ưu bộ nhớ và xử lý đa luồng để nâng cao hiệu suất tìm kiếm trên các máy chủ đa nhân, mục tiêu giảm bộ nhớ sử dụng xuống 20%, thực hiện trong 18 tháng, do nhóm nghiên cứu và kỹ sư phần mềm phối hợp.

4. Mở rộng ứng dụng thuật toán cho các loại dữ liệu sinh học khác: Nghiên cứu áp dụng mô hình N-Gram cho chuỗi RNA và protein, nhằm tăng phạm vi ứng dụng trong y sinh học, hoàn thành trong 24 tháng, do các nhà khoa học sinh học phân tử và tin sinh học phối hợp thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu tin sinh học: Có thể áp dụng thuật toán N-Gram để phát triển các công cụ tìm kiếm gen nhanh, phục vụ nghiên cứu di truyền và giải trình tự gen.

2. Chuyên gia y sinh học và di truyền học: Sử dụng phương pháp để phân tích gen bệnh, xác định biến thể gen liên quan đến bệnh lý, hỗ trợ chẩn đoán và điều trị.

3. Cán bộ khoa học hình sự: Áp dụng thuật toán trong việc phân tích mẫu DNA hiện trường, tăng tốc độ truy xuất và so sánh với cơ sở dữ liệu tội phạm.

4. Nhà phát triển phần mềm sinh học: Tham khảo để xây dựng các ứng dụng phần mềm tìm kiếm chuỗi DNA hiệu quả, tích hợp vào các hệ thống quản lý dữ liệu sinh học.

Câu hỏi thường gặp

1. Thuật toán N-Gram có thể áp dụng cho các chuỗi DNA dài bao nhiêu ký tự?
   Thuật toán có thể xử lý các chuỗi DNA dài hàng triệu ký tự bằng cách phân đoạn thành các đoạn nhỏ 500 ký tự và tách thành các "từ" 12 ký tự, giúp giảm độ phức tạp và tăng tốc độ tìm kiếm.

2. So với BLAST, thuật toán N-Gram có ưu điểm gì?
   N-Gram có thời gian tìm kiếm nhanh hơn và sử dụng bộ nhớ hiệu quả hơn, đặc biệt khi xử lý các bộ dữ liệu lớn, trong khi BLAST có thể chậm hơn do tính toán heuristic phức tạp.

3. Độ chính xác của thuật toán N-Gram như thế nào?
   Thuật toán đảm bảo tìm kiếm chính xác các đoạn chuỗi có độ dài 12 ký tự tương tự, phù hợp với nhiều ứng dụng thực tế, mặc dù không đạt độ chính xác tuyệt đối như Smith-Waterman.

4. Có thể tìm kiếm nhiều chuỗi DNA cùng lúc không?
   Có, thuật toán hỗ trợ tìm kiếm đồng thời nhiều mẫu chuỗi DNA, phù hợp với các ứng dụng giải trình tự thế hệ mới (HTS) với khối lượng dữ liệu lớn.

5. Thuật toán có thể áp dụng cho các loại dữ liệu sinh học khác ngoài DNA không?
   Có thể mở rộng áp dụng cho chuỗi RNA và protein, tuy nhiên cần điều chỉnh tham số n trong mô hình N-Gram và các bước tiền xử lý phù hợp với đặc điểm dữ liệu.

Kết luận

• Thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tương tự nhanh áp dụng mô hình N-Gram đã cải thiện đáng kể thời gian tìm kiếm và tiết kiệm bộ nhớ so với các phương pháp truyền thống.
• Phương pháp phân đoạn chuỗi DNA thành các đoạn 500 ký tự và tách thành các "từ" 12 ký tự giúp tối ưu hóa quá trình truy xuất dữ liệu.
• Thuật toán phù hợp với các bộ dữ liệu gen lớn, có thể xử lý đồng thời nhiều mẫu, đáp ứng nhu cầu của giải trình tự thế hệ mới.
• Kết quả thử nghiệm trên 11 bộ dữ liệu thực tế cho thấy thời gian tìm kiếm chỉ từ 1 đến 11 giây với bộ nhớ sử dụng hợp lý.
• Hướng phát triển tiếp theo là tối ưu hóa bộ nhớ, xử lý song song và mở rộng ứng dụng cho các loại dữ liệu sinh học khác, đồng thời phát triển giao diện người dùng thân thiện.

Luận văn khuyến khích các nhà nghiên cứu và phát triển phần mềm trong lĩnh vực tin sinh học áp dụng và mở rộng thuật toán nhằm nâng cao hiệu quả xử lý dữ liệu gen trong tương lai.

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

Chương 1 trình bày về tổng quan các phương pháp sử dụng để tìm kiếm chuỗi DNA. Thuật toán tìm kiếm cụ thể mà người viết tập trung nghiên cứu là thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram được trình bày ở chương 2. Chương 3 của luận văn mô tả môi trường thực nghiệm so sánh thuật toán tương tự nhanh áp dụng N-gram với phương pháp tìm kiếm khác và một số phân tích đánh giá của người viết về kết quả đạt được. Cuối cùng là kết luận về hiệu quả cũng như hạn chế còn tồn tại và hướng phát triển trong tương lai cho việc nghiên cứu và cải tiến phương pháp tìm kiếm chuỗi DNA.

12 LUAN VAN CHAT LUONG download : add [e-mail] CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA Ở phầ n trước, người viết đã giới thiệu sơ lược về cấu trúc DNA, các ứng dụng của DNA trong đời sống. Khái quát, một số phương pháp thường được sử dụng để tìm kiếm chuỗi DNA. Chương này, người viết sẽ trình bày cụ thể hơn về các thuật toán tìm kiếm chuỗi: Đặc trưng chung của các dạng tìm kiếm, các phương pháp nổi bật của từng dạng, ưu điểm, nhược điểm của các dạng tìm kiếm chuỗi.

Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn Mô hình Markov ẩn được bắt đầu xây dựng và công bố từ những năm 1960, đây là mô hình toán học về thống kê, tính toán xác suất. Nhiều năm sau đó (1980) mô hình được bắt đầu được nghiên cứu để ứng dụng trong lĩnh vực nhận dạng. Thuật toán tìm kiếm chuỗi sử dụng mô hình Markov ẩn dùng phương pháp mô hình hóa quá trình tìm kiếm chuỗi trong đó có sử dụng các tham số quan sát được và các tham số không biết trước – mô hình Markov. Sau đó sẽ xác định các tham số không biết trước từ các tham số quan sát được.

Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Với mô hình Markov ẩn cấu trúc mô hình có thể thay đổi dễ dàng cho phù hợp với từng ứng dụng cụ thể. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn Thuật toán: Cho 2 chuỗi: Chuỗi quan sát: x = x1x2. Chuỗi so sánh: y = y1y2.

Xn là số vị trí của giá trị có thể từ tập quan sát O = {O1O2,.,ON} Yn nhận giá trị từ tập trạng thái S = {1,2,. N và M biểu thị vị trí quan sát và số lượng các trạng thái trong mô hình. Cho chuỗi trạng thái ẩn xuất hiện đồng thời trong chuỗi Markov. Điều này có nghĩa là trạng thái đầu vào j sau sẽ phụ thuộc vào trạng thái i trước đó.

Trạng thái này có thể sẽ không đổi. P{yn+1=j|yn=i, yn −1=in−1,.,y1=i1}=P{yn+1=j| yn =i}=t(i,j) với mọi i, j ∈ S và n≥1 [5] 13 LUAN VAN CHAT LUONG download : add [e-mail] Các trạng thái chuyển từ trạng thái i sang trạng thái j gọi là trạng thái chuyển tiếp. Gọi hàm chuyển tiếp là t(i,j). Trạng thái bắt đầu Y1 có thể ở bất kỳ i ∈ S.

Ở vị trí quan sát xn=x có thể chỉ phụ thuộc vào trạng thái yn. Do vậy: P{xn=x|yn=i,yn−1,xn−1,.}=P{xn=x|yn=i}=e(x|i) [5] Với mọi x ∈ O, mọi i ∈ S, và mọi n ≥ 1; e(x|i) là hàm giá trị x tạo ra tại trạng thái i. Ba độ đo: t(i, j), π(i), and e(x | i) là 3 tham số mô tả cho mô hình HMM. Gọi tập 3 tham số này là Θ.

Dựa vào 3 tham số trên, ta có thể tính được chuỗi quan sát x = x1 x2. xL sẽ sinh ra chuỗi y = y1 y2. Như vậy dựa vào mô hinh khi biết chuỗi trạng tháivà đầu vào ta có thể biết được chuỗi quan sát. Ví dụ minh họa cho mô hình Markov ẩn: Hình 1.1: Mô hình Markov ẩn [5] a.

Sắp xếp các chuỗi ban đầu. 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô hình Markov ẩn (bỏ khoảng trống giữa các trạng thái). Mô hình hóa sự liên kết theo Mô hình Markov ẩn Mô hình Markov ẩn hiệu quả cho mô hình hóa thông tin về các chuỗi liên kết, phù hợp cho các cấu trúc chuỗi mẫu vì mô hình này có cấu trúc trái sang phải tuyến tính mà không chứa bất kỳ chu kỳ nào.

Mô hình sử dụng ba loại trạng thái: ẩn(delete), quan sát được(insert) và kết quả(match). Ví dụ: Việc so sánh hai chuỗi sinh học theo Mô hình Markov ẩn sẽ sắp xếp các chuỗi dựa trên sự giống nhau, tính toán số điểm liên kết của chúng, và đánh giá các liên kết thống kê được. Tuy nhiên, để tìm ra sự liên kết tốt giữa các trình tự, chúng ta phải đưa ra được một bảng xếp hạng dựa trên sự giống nhau của các chuỗi. Căn cứ vào bảng này, chúng ta có thể chọn các liên kết nhằm tối đa hóa điểm số liên kết.

Ví dụ về mô hình cặp HMM [5] Mô hình cặp -HMM tạo ra cặp liên kết chuỗi. Hai chuỗi DNA x và z được đồng thời tạo ra bởi các cặp-HMM, các dãy trạng thái cơ bản là y. Các trạng thái y xác định chỉ 1 liên kết duy nhất giữa x và z. Ưu điểm: Phương pháp này đã được sử dụng rộng rãi trong tin sinh học vì độ chính xác cao.

Cách mô hình hóa dễ sử dụng. Nhược điểm: Chi phí thời gian lớn và các hàm tính toán phức tạp. Phƣơng pháp liên kết nhạy cảm đầy đủ Phương pháp này được sử dụng để tìm sự giống nhau hoặc có độ tương đồng cao của hai chuỗi. Bằng cách lập ma trận, tính độ đo để tìm ra sự giống hoặc có độ 15 LUAN VAN CHAT LUONG download : add [e-mail] tương đồng cao của tất cả độ dài các phân đoạn của hai xâu, hai chuỗi protein hoặc nucleotide.

Với chuỗi đã được tìm kiếm và có độ tương đồng cao trước đó, phương pháp có thể mở rộng phạm vi tìm kiếm về hai phía (trước hoặc sau). Phương pháp này có ưu điểm là độ chính xác cao. Tuy nhiên chi phí thời gian lớn. Phương pháp đặc trưng của dạng này là phương pháp Smith & Waterman do hai nhà khoa học T.Waterman công bố năm 1981.

[18] Thuật toán Smith & Waterman Thuật toán Smith-Waterman là một thuật toán quy hoạch động dùng để tìm kiếm cơ sở dữ liệu phát triển bởi T.S Waterman vào năm 1981 và dựa trên một mô hình thích hợp trước đó có tên Needleman và Wunsch. Thuật toán sử dụng bảng ma trận để đánh giá sự tương đồng của hai chuỗi. Tìm kiếm lần lượt từ đầu đến cuối trong hai chuỗi xem mức độ tương đồng ở mức nào (tương đồng hoặc không tương đồng). Với các mức độ tương đồng khác nhau sẽ có những chỉ số độ đo khác nhau.

Đặc điểm của thuật toán Smith-Waterman là thuật toán so sánh các cặp chuỗi cục bộ dựa trên quy hoạch động để tính điểm cho quá trình so sánh.Giải thuật này giúp nhận ra những miền tương đồng giữa hai chuỗi tìm kiếm cho giống chuỗi cục bộ tối ưu hơn. Giải thuật Smith-Waterman thực hiện so sánh đối xứng ở dạng cục bộ, khác với giải thuật so sánh đối xứng toàn cục (ví dụ: Needleman- Wunsch), giải thuật sắp hàng hay so sánh đối xứng cục bộ chỉ thực hiện việc so sánh đối xứng trên một số phần của các trình tự được so sánh. Để tìm cặp tương đồng (a,b) ta lập ma trận H. Đặt: HkO = HoL, = 0 for 0 ≤ k ≤ n and 0 ≤ l ≤ m.

[6] Hij thể hiện mức độ tương đồng của ai,bj. Hij được tính bằng công thức: Hij=max{Hi-1,j-1 + s(ai,bj).max(Hi-k,j - wk}.max{ Hi,j-l - wl},0} (1) k≥1 l≥1 với l ≤ i ≤ n và l ≤ j ≤ m. [6] Công thức Hij tính bởi các giá trị ở cuối các đoạn tại bất kỳ giá trị ai và bj nào. (1) Nếu ai và bj có liên kết, độ tương tự tính như sau: 16 LUAN VAN CHAT LUONG download : add [e-mail] Hi-1,j-1 + s(ai.bj) (2) Nếu ai tại vị trí cuối của dãy xóa k, độ tương tự tính bằng công thức Hi-k,j - Wk (3) Nếu bj là vị trí cuối của vị trí xóa có độ dài l, độ tương tự xác định bởi Hi-k,j – Wl (4) Giá trị 0 đã bao gồm biểu thị cho mức độ không tương đồng, nó chỉ ra rằng mức độ không tương đồng cho đến giá trị ai và bj Giá trị H càng cao thì mức độ tương đồng của Hij càng lớn.

Đầu tiên ta tìm chỉ số cao nhất của ma trận. Sau đó, duyệt ngược trở lại. Ta sẽ tìm được mức độ tương đồng của 2 chuỗi cần chọn. Thuật toán: - Đầu vào : Hai chuỗi S1 và S2 với chiều dài tương ứng là n, m.

Ma trận thay thế S.  Đầu ra : Hai chuỗi S1’, S2’.  Bước 1 : Khởi tạo : + H(0,0) = 0 + H(i,0) = 0 0 ≤ i ≤ m + H(0,j) = 0 0 ≤ j ≤ n  Bước 2 : Điền giá trị vào ma trận. Tính H(i, j) theo công thức H(i, j) = MAX (0, H(i-1,j-1) + S(i,j), H(i-1,j)+d, H(i,j-1) + d) (1) [6] Mỗi khi tính H(i, j) lưu lại chỉ số của số hạng ở vế phải (1)  Bước 3 : Tìm ô (i_max, j_max) có điểm cao nhất (0  i  m, 0  j  n)  Bước 4 : Quay lại bước 2.

 Xuất phát từ ô (i_max, j_max).Dựa vào những chỉ số đã lưu ở bước 2 để tìm giá trị cho đến khi gặp ô H(i,j) = 0 thì dừng.  Nếu đường đi theo chiều ngang hay từ ô (i,j-1) sang ô (i,j) thì thêm “-“ vào S2’ và thêm kí tự S1(j) vào S1’.  Nếu đường đi theo chiều thẳng đứng hay từ ô (i-1, j) xuống ô (i,j) thì thêm “-“ vào S1’ và thêm kí tự S2(i) và S2’.  Nếu đường đi theo đường chéo hay từ ô (i-1, j-1) đến ô (i,j) thì thêm kí tự S1(j) vào S1’ và S2(i) vào S2’  Đảo ngược S1’, S2’ 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.