Tin sinh học (Bioinformatics)
Needleman-Wunsch Global Alignment
ID: #383
Xem trên trang chủ
Thời gian (Time)
O(M * N)
Không gian (Space)
O(M * N)
Mô tả nguyên lý
Thuật toán quy hoạch động căn chỉnh toàn cục hai chuỗi sinh học (ADN/Protein) tối ưu.
Cài đặt mẫu (Implementation)
// Xây dựng ma trận điểm số phạt khoảng trống (gap penalty) và khớp ký tự từ dưới lên (traceback).
Tin sinh học (Bioinformatics)
Smith-Waterman Local Alignment
ID: #384
Xem trên trang chủ
Thời gian (Time)
O(M * N)
Không gian (Space)
O(M * N)
Mô tả nguyên lý
Cải tiến của Needleman-Wunsch chuyên tìm đoạn tương đồng cục bộ tốt nhất giữa hai chuỗi.
Cài đặt mẫu (Implementation)
// Không cho phép điểm số ma trận giảm xuống dưới 0, bắt đầu traceback từ giá trị lớn nhất trong bảng.