Các thuật toán căn chỉnh trình tự

Các thuật toán căn chỉnh trình tự đo lường và hiển thị sự tương đồng giữa hai chuỗi bằng cách tìm cách ít tốn kém nhất để biến đổi chuỗi này thành chuỗi kia, sử dụng lập trình động trên các phép chèn, xóa và thay thế.

Definition

Căn chỉnh trình tự là sự sắp xếp hai (hoặc nhiều) chuỗi để tối đa hóa sự tương ứng của chúng bằng cách chèn khoảng trống và khớp, không khớp hoặc thay thế các ký tự; một thuật toán căn chỉnh tính toán một căn chỉnh tối ưu và điểm số của nó theo một mô hình chi phí hoặc tính điểm nhất định, thường thông qua lập trình động.

Scope

Chủ đề này bao gồm các thuật toán lập trình động để so sánh chuỗi: khoảng cách chỉnh sửa (Levenshtein) và chuỗi con chung dài nhất, căn chỉnh toàn cục (Needleman-Wunsch), căn chỉnh cục bộ (Smith-Waterman), và các lược đồ tính điểm (phạt khoảng trống, ma trận thay thế) định hình các căn chỉnh sinh học. Nó đề cập đến công thức truy hồi cơ bản và chi phí thời gian và không gian bậc hai của nó, cùng với các cải tiến tiết kiệm không gian. Các phương pháp dựa trên chỉ mục và khớp chính xác được đề cập trong các chủ đề liên quan.

Core questions

• Sự tương đồng giữa hai chuỗi được định lượng như thế nào dưới dạng khoảng cách chỉnh sửa hoặc điểm căn chỉnh?
• Một bảng lập trình động tính toán một căn chỉnh tối ưu như thế nào?
• Điều gì phân biệt căn chỉnh toàn cục với căn chỉnh cục bộ, và khi nào thì mỗi loại phù hợp?
• Các hình phạt khoảng trống và ma trận thay thế ảnh hưởng đến căn chỉnh kết quả như thế nào?
• Làm thế nào để giảm yêu cầu không gian bậc hai cho các chuỗi dài?

Key concepts

• khoảng cách chỉnh sửa (Levenshtein)
• chuỗi con chung dài nhất
• căn chỉnh toàn cục
• căn chỉnh cục bộ
• thuật toán Needleman-Wunsch
• thuật toán Smith-Waterman
• hình phạt khoảng trống
• ma trận thay thế

Key theories

Căn chỉnh toàn cục bằng lập trình động

Thuật toán Needleman-Wunsch điền vào một bảng lập trình động mà các mục nhập của nó cung cấp điểm căn chỉnh tốt nhất của các tiền tố chuỗi, tạo ra một căn chỉnh tối ưu từ đầu đến cuối (toàn cục) của hai trình tự trong thời gian tỷ lệ thuận với tích độ dài của chúng.

Căn chỉnh cục bộ cho các chuỗi con chung

Thuật toán Smith-Waterman sửa đổi công thức truy hồi để cho phép các căn chỉnh bắt đầu và kết thúc ở bất cứ đâu, tìm kiếm vùng khớp có điểm số cao nhất (căn chỉnh cục bộ), điều này rất cần thiết để phát hiện các đoạn được bảo tồn trong các trình tự không tương đồng khác.

Clinical relevance

Căn chỉnh trình tự là một nền tảng của sinh học tính toán, được sử dụng để so sánh các trình tự DNA, RNA và protein để tìm kiếm sự tương đồng, suy luận tiến hóa và tìm kiếm cơ sở dữ liệu (thuật toán heuristic BLAST được xây dựng dựa trên căn chỉnh cục bộ). Ngoài sinh học, cơ chế khoảng cách chỉnh sửa tương tự cũng được sử dụng trong kiểm tra chính tả, khớp văn bản mờ, so sánh phiên bản trong kiểm soát phiên bản và so sánh giọng nói và chữ viết tay.

History

Levenshtein đã giới thiệu khoảng cách chỉnh sửa vào năm 1965. Needleman và Wunsch đã đưa ra thuật toán căn chỉnh toàn cục bằng lập trình động đầu tiên cho protein vào năm 1970, và Smith và Waterman đã giới thiệu căn chỉnh cục bộ vào năm 1981. Kỹ thuật không gian tuyến tính của Hirschberg (1975) và các thuật toán heuristic sau này như BLAST đã mở rộng căn chỉnh để sử dụng thực tế quy mô lớn.

Key figures

• Saul Needleman
• Christian Wunsch
• Temple Smith
• Michael Waterman
• Vladimir Levenshtein

Seminal works

• needleman1970
• smith1981
• gusfield1997

Frequently asked questions

Sự khác biệt giữa căn chỉnh toàn cục và căn chỉnh cục bộ là gì?

Căn chỉnh toàn cục (Needleman-Wunsch) căn chỉnh hai trình tự từ đầu đến cuối và phù hợp khi chúng có độ dài tương tự và được dự kiến có liên quan trong suốt. Căn chỉnh cục bộ (Smith-Waterman) tìm thấy vùng con khớp tốt nhất và phù hợp khi chỉ một phần của các trình tự tương tự, chẳng hạn như một miền được bảo tồn trong các trình tự lớn hơn.

Căn chỉnh trình tự có giống với chuỗi con chung dài nhất không?

Chúng có liên quan chặt chẽ. Chuỗi con chung dài nhất là một trường hợp đặc biệt của căn chỉnh với cách tính điểm cụ thể (khớp được thưởng, khoảng trống miễn phí, không cho phép không khớp). Căn chỉnh tổng quát sử dụng cách tính điểm phong phú hơn với chi phí thay thế và hình phạt khoảng trống, nhưng cả hai đều được giải quyết bằng cùng một loại công thức truy hồi lập trình động.