Bài toán chuỗi con chung dài nhất

Vấn đề chuỗi con chung dài nhất (tiếng anh: Longest common subsequence - LCS) là vấn đề trong việc tìm kiếm một chuỗi con chung dài nhất cho tất cả các chuỗi trong một bộ chuỗi (thường chỉ hai chuỗi). Nó khác với vấn đề về xâu con chung dài nhất ở chỗ: không giống như các xâu con, các chuỗi con không bắt buộc phải chiếm các vị trí liên tiếp trong các chuỗi ban đầu. Bài toán chuỗi con chung dài nhất là một trong những bài toán khoa học máy tính cổ điển, là cơ sở của các chương trình so sánh dữ liệu như diff, và có các ứng dụng trong ngôn ngữ học tính toán và tin sinh học. Nó cũng được sử dụng rộng rãi bởi các hệ thống quản lý phiên bản như Git để điều chỉnh nhiều thay đổi được thực hiện cho một bộ sưu tập tệp được kiểm soát sửa đổi.

Ví dụ, hãy xem xét các chuỗi (ABCD) và (ACBAD). Chúng có 5 chuỗi con chung có độ dài bằng 2: (AB), (AC), (AD), (BD) và (CD); 2 chuỗi con chung có độ dài bằng 3: (ABD) và (ACD); và không còn chuỗi con chung nào khác có độ dài lớn hơn nữa. Vì vậy (ABD) và (ACD) là hai dãy con chung dài nhất của hai chuỗi ban đầu.

Độ phức tạp[sửa | sửa mã nguồn]

Đối với trường hợp tổng quát với số lượng chuỗi trình tự đầu vào là tùy ý, vấn đề là NP-khó.^[1] Khi số lượng chuỗi trình tự không đổi, bài toán có thể giải được trong thời gian đa thức bằng quy hoạch động.

Thuật toán cho hai chuỗi[sửa | sửa mã nguồn]

Bài toán LCS có một cấu trúc con tối ưu: Có nghĩa là bài toán có thể được chia thành các bài toán con nhỏ hơn và đơn giản hơn, và các chính bài toán con cũng được chia thành các bài toán con đơn giản hơn, và cứ thế, cho đến khi, cuối cùng, nghiệm của bài toán trở nên đơn giản và dễ nhận thấy. LCS nói riêng có các bài toán con chồng chéo: các nghiệm cho các bài toán con cấp cao sẽ sử dụng lại các nghiệm cho các bài toán con cấp thấp hơn. Các vấn đề với hai thuộc tính này có thể giải quyết được bằng quy hoạch động, trong đó các nghiệm của bài toán con sẽ được lưu lại để xử lý lúc sau.

Tiền tố[sửa | sửa mã nguồn]

Ta định nghĩa tiền tố S_n của S là chuỗi chứa n ký tự đầu tiên của S. ^[2] Ví dụ: các tiền tố của S = (AGCA) là

S₀ = ()

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA).

Gọi LCS(X, Y) là một hàm tính toán chuỗi con chung dài nhất cho X và Y. Một hàm như vậy có hai tính chất đặc biệt như sau:

Tính chất đầu tiên[sửa | sửa mã nguồn]

LCS(X^A, Y^A) = LCS (X, Y)^A, cho tất cả các chuỗi X, Y và tất cả các ký hiệu A, trong đó dấu ^ biểu thị phép nối xâu. Điều này cho phép chúng ta đơn giản hóa việc tính toán LCS cho hai chuỗi kết thúc cùng một ký hiệu. Ví dụ: LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN") ^ "A", Tiếp tục cho các ký hiệu chung còn lại, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ") ^" ANA".

Tính chất thứ hai[sửa | sửa mã nguồn]

Nếu A và B là hai ký hiệu riêng biệt (A≠B), thì LCS (X^A, Y^B) là một trong hai xâu có độ dài cực đại trong tập {LCS(X^A, Y), LCS(X, Y^B)}, cho tất cả các xâu X và Y.

Ví dụ: LCS ("ABCDEFG", "BCDGK") là xâu dài hơn của LCS ("ABCDEFG", "BCDG") và LCS ("ABCDEF", "BCDGK"); nếu cả hai có độ dài bằng nhau, ta có thể chọn tùy ý một trong những chuỗi thỏa mãn.

Định nghĩa hàm LCS[sửa | sửa mã nguồn]

Cho hai chuỗi được xác định như sau: $X=(x_{1}x_{2}\cdots x_{m})$ và $Y=(y_{1}y_{2}\cdots y_{n})$ . Các tiền tố của $X$ là $X_{1,2,\dots ,m}$ ; tiền tố của $Y$ là $Y_{1,2,\dots ,n}$ . Gọi ${\mathit {LCS}}(X_{i},Y_{j})$ là đại diện cho tập hợp các chuỗi con chung dài nhất cho các tiền tố của $X_{i}$ và $Y_{j}$ . Tập hợp các chuỗi này được định nghĩa như sau.

{\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}

Làm việc với ví dụ[sửa | sửa mã nguồn]

Để lấy ví dụ, ta sẽ tìm chuỗi con dài nhất chung cho hai xâu R = (GAC) và C = (AGCAT). Vì hàm LCS xét từ vị trí 0, nên để thuận tiện, ta sẽ xác định các tiền tố 0 là trống cho các chuỗi này: R₀ = Ø; và C₀ = Ø. Tất cả các tiền tố được đặt trong một bảng với C ở hàng đầu tiên và R ở cột đầu tiên:

Chuỗi LCS
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

Bảng này được sử dụng để lưu trữ trình tự tính LCS cho mỗi bước tính toán. Cột thứ hai và hàng thứ hai đã được điền bằng Ø, bởi vì khi một chuỗi trống được so sánh với một chuỗi không trống, chuỗi con chung dài nhất luôn là chuỗi trống.

LCS (R₁, C₁) được xác định bằng cách so sánh các phần tử đầu tiên trong mỗi chuỗi. G và A không giống nhau, vì vậy LCS này nhận (sử dụng tính chất thứ hai trên) chuỗi dài nhất trong hai chuỗi, LCS(R₁, C₀) và LCS (R₀, C₁). Theo bảng, cả hai đều trống, vì vậy LCS (R₁, C₁) cũng trống. Các mũi tên biểu thị chuỗi nhập vào: chuỗi đến từ ô ở trên, LCS (R₀, C₁) và chuỗi đến từ ô ở bên trái, LCS(R₁, C₀).

LCS (R₁, C₂) được xác định bằng cách so sánh G và G. Chúng khớp với nhau, nên G được nối vào chuỗi phía trên bên trái, LCS(R₀, C₁), là (Ø), cho (ØG), ta được (G).

Đối với LCS (R₁, C₃), G và C không khớp. Chuỗi trên trống; Chuỗi bên trái chứa một phần tử, (G). Chọn phần tử có độ dài dài nhất trong hai chuỗi này, ta được LCS (R₁, C₃) là (G). Mũi tên chỉ sang trái, vì đó là chuỗi dài nhất trong hai chuỗi.

Tương tự như vậy, LCS(R₁, C₄) và LCS(R₁, C₅) là (G).

Hoàn thành hàng "G"
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø
C	Ø

Tương tự như vậy, ta hoàn thành hàng R₂

Hoàn thành hàng "G" và hàng "A"
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø

Bảng hoàn thiện cuối cùng là

Bảng LCS đã hoàn thiện
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø	${\overset {\ \uparrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (AC) & (GC)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)

Lưu độ dài, thay vì chuỗi
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Mã cho giải pháp quy hoạch động[sửa | sửa mã nguồn]

Tính độ dài của LCS[sửa | sửa mã nguồn]

Hàm bên dưới nhận như chuỗi đầu vào X[1..m] và Y[1..n], tính LCS giữa X[1..i] và Y[1..j] cho tất cả 1 ≤ i ≤ m và 1 ≤ j ≤ n, và lưu trữ nó trong C[i,j]. C[m,n] sẽ chứa độ dài LCS của X và Y

function LCSLength(X[1..m], Y[1..n])
  C = array(0..m, 0..n)
  for i:= 0..m
    C[i, 0] = 0
  for j:= 0..n
    C[0, j] = 0
  for i:= 1..m
    for j:= 1..n
      if X[i] = Y[j]
        C[i, j]:= C[i-1, j-1] + 1
      else
        C[i, j]:= max(C[i, j-1], C[i-1, j])
  return C[m, n]

Tham khảo[sửa | sửa mã nguồn]

^ David Maier (1978). “The Complexity of Some Problems on Subsequences and Supersequences”. J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075.
^ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. tr. 24. ISBN 978-0-387-71336-6.

liên kết ngòai[sửa | sửa mã nguồn]

[1] David Maier (1978). “The Complexity of Some Problems on Subsequences and Supersequences”. J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075.

[2] Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. tr. 24. ISBN 978-0-387-71336-6.

[1]

[2]