Longest Common Subsequence (LCS)

Dalam aplikasi biologi sering diperlukan pembandingan DNA dari dua (atau lebih) organisme yang berbeda. Seuntai DNA terdiri dari serangkaian molekul yang disebut basis. Basis yang mungkin adalah adenin, guanin, citosin, dan timin. Keempat basis DNA ini dapat dituliskan dengan notasi huruf {A, C, G, T}.

Contoh, DNA suatu organisme misalnya S₁ = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, dan DNA untuk organisme lain  misalnya S₂ = GTCGTTCGGAATGCCGTTGCTCTGTAAA. Salah satu alasan membandingkan untaian dua DNA ini adalah untuk menentukan “kemiripan” kedua untaian tersebut sebagai ukuran kedekatan antara kedua organisme tersebut.

Untuk mengukur kemiripan untaian S₁ dan S₂ adalah dengan menemukan untaian ketiga yaitu S₃ sebagai untaian terpanjang dari kedua untaian, dimana basis di S₃ muncul di setiap S₁ dan S₂. Semakin panjang untaian S₃ yang ditemukan maka S₁ dan S₂ semakin mirip.

S₁ = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA

S₂ = GTCGTTCGGAATGCCGTTGCTCTGTAAA

S₃ = GTCGTCGGAAGCCGGCCGAA

Masalah kemiripan ini dikenal dengan istilah subsekuens bersama terpanjang (Longest Common Subsequence (LCS)). Algoritma untuk LCS telah dipelajari untuk waktu yang lama dan sekarang telah menjadi bagian penting dari ilmu komputer. Aplikasinya dipakai secara luas, tidak hanya terbatas pada lingkup ilmu komputer seperti pengenalan pola (Lu dan Fu 1978), namun juga di bidang biologi seperti yang sudah dipaparkan sebelumnya.

Definisi LCS

Subsekuens string X adalah sekumpulan karakter yang ada pada X yang urutan kemunculannya sama. Secara formal dapat didefinisikan sebagai berikut: sekuens Z = ⟨z₁, z₂, … , z_k⟩ adalah subsekuens dari X = ⟨x₁, x₂, … , x_m⟩, jika terdapat urutan menaik ⟨i₁, i₂, … , i_k⟩ yang merupakan indeks X untuk semua j = 1, 2, 3, … , k, yang memenuhi x_{i j} = z_j. Contoh, Z = ⟨B, C, D, B⟩ adalah subsekuens dari X = ⟨A, B, C, B, D, A, B⟩, dengan sekuens indeks ⟨2, 3, 5, 7⟩.

Subsekuens bersama dari dua sekuens adalah subsekuens yang terdapat pada kedua sekuens tersebut. Misal X = ⟨A, B, C, B, D, A, B⟩ dan Y = ⟨B, D, C, A, B, A⟩, maka sekuens ⟨B, C, A⟩ adalah  subsekuens bersama dari X dan Y. Tetapi bukan merupakan sekuens bersama terpanjang (LCS) dari X dan Y karena panjang sekuens 3, karena masih terdapat sekuens ⟨B, C, B, A⟩ dengan panjang 4. ⟨B, C, B, A⟩ adalah subsekuens bersama terpanjang antara X dan Y, karena tidak ada lagi subsekuens bersama yang panjangnya 5.

Pada masalah subsekuen bersama terpanjang (LCS), diberikan dua sekuens X = ⟨x₁, x₂, … , x_m⟩  dan Y = ⟨y₁, y₂, … , y_n⟩ dan bermaksud untuk menemukan panjang maksimum dari subsekuens terpanjang X dan Y. Tulisan ini menunjukkan bagaimana cara menyelesaikan masalah LCS  secara efisien dengan menggunakan pemrograman dinamis.

Metode Brute Force

Salah satu pendekatan untuk memecahkan masalah LCS adalah brute force. Semua subsekuens X akan dibangkitkan dan masing-masing subsekuens akan diperiksa apakah subsekuens tersebut juga merupakan subsekuens dari Y.

Langkah-langkah brute force:

1. Bangkitkan semua subsekuens untuk X_m dan Y_n
2. Cari sekuens yang sama
3. Ambil yang terpanjang

Contoh:

X_m = ⟨A, T, G⟩

Y_n = ⟨T, C, G⟩

Bangkitkan semua subsekuens X_m:

X₀ = ⟨ ⟩

X₁ = ⟨A⟩, ⟨T⟩, ⟨G⟩

X₂ = ⟨A, T⟩, ⟨T, G⟩, ⟨A, G⟩

X₃ = ⟨A, T, G⟩                           … diperoleh 2³ = 8 subsekuens

Bangkitkan semua subsekuens Y_n:

Y₀ = ⟨ ⟩

Y₁ = ⟨T⟩, ⟨C⟩, ⟨G⟩

Y₂ = ⟨T, C⟩, ⟨C, G⟩, ⟨T, G⟩

Y₃ = ⟨T, C, G⟩                           … diperoleh 2³ = 8 subsekuens

Cari sekuens bersama X_m dan Y:

⟨ ⟩, ⟨T⟩, ⟨G⟩, ⟨T, G⟩                            … dilakukan (maksimal) 4!/2!² = 20 perbandingan

Pilih sekuens bersama terpanjang (LCS) X_m dan Y_n:

⟨T, G⟩                                                    … dilakukan (maksimal) 2³ = 8 kali

Kompleksitas worst-case untuk penyelesaian masalah LCS dengan brute force, dengan asumsi m = n adalah:

T(n)      = T_{generate_subsequence_X} + T_{generate_subsequence_Y} + T_{find_common_subsequence} + T_{find_longest_common_subsequence}

= 2ⁿ + 2ⁿ + (2n)!/n!² + 2ⁿ

= 3.2ⁿ + (2n)!/n!²                      … 4ⁿ/(n+1)  ≤  (2n)!/n!²  ≤  4ⁿ, untuk n < 1

= O(4ⁿ)

Teorema Substruktur Optimal

Misalnya X = ⟨x₁, x₂, … , x_m⟩  dan Y = ⟨y₁, y₂, … , y_n⟩ adalah sekuens, dan Z = ⟨z₁, z₂, … , z_k⟩ adalah suatu LCS dari X dan Y.

1. Jika x_m = y_n, maka z_k = x_m = y_n dan Z_k-1 adalah suatu LCS dari X_m-1 dan Y_n-1.
2. Jika x_m ≠ y_n, maka z_k ≠ x_m mengimplikasikan bahwa Z adalah suatu LCS dari X_m-1 dan Y
3. Jika x_m ≠ y_n, maka z_k ≠ y_n mengimplikasikan bahwa Z adalah suatu LCS dari X dan Y_n-1

Metode Rekursif

Jika akan menguji satu atau dua subproblem dimana terdapat suatu LCS dari X = ⟨x₁, x₂, … , x_m⟩  dan Y = ⟨y₁, y₂, … , y_n⟩. Jika  x_m = y_n ,perlu menemukan LCS dari X_m-1 dan Y_n-1. Dengan melampirkan x_m = y_n pada LCS ini dengan menemukan LCS dari X dan Y. jika x_m ≠ y_n, kemudian harus memecahkan 2 subproblem yaitu mendapatkan sebuah LCS dari x_m-1 dan Y dan LCS dari X dan y_n-1. Mana saja dari LCS yang lebih panjang adalah LCS dari X dan Y. karena kasus ini menyeleksi semua kemungkinan, maka solusi subproblem yang optimum harus ada sebagai sebuah LCS dari X dan Y.

Untuk menemukan LCS dari X dan Y, harus mendapat LCS dari x dan y_n-1 dan x_m-1 dan y. tetapi setiap masalah subproblem ini mempunyai masalah dalam menemukan LCS dari x_m-1 dan y_n-1. Banyak lagi subproblem yang lain yang terdiri dari bagian subroblem lainnya.

Seperti masalah rantai matrik multiplikatif, solusi recursive LCS meliputi menetapkan pengulangan dari solusi yang optimum. Contoh  ini definisikan  c[i, j] adalah panjang LCS pada barisan deret x_i dan  y_i. Jika kedua i=0 atau j=0, satu dari deret memiliki panjang 0, maka LCS mempunyai panjang 0

Perhatikan rumus rekursif berikut, suatu kondisi masalah membatasi subproblem yang sedang di pertimbangkan. Ketika x_i dan y_i harus mempertimbangkan subproblem yang menemukan suatu LCS dari x_i-1 dan y_n-1. Jika tidak, cari  dua subproblem menemukan suatu LCS dari x_i dan y_i-1  dan dari x_i-1 dan y_i. Dalam menemukan sebuah LCS bukan hanya algoritma pemrograman dinamis yang mengabaikan subproblem berdasarkan kondisi pada masalah.

LCS Rec (𝑋𝑚,, 𝑌𝑛,)
If 𝑋𝑚, = 𝑌𝑛,
Z = (LCS Rec (𝑋𝑚−1,, 𝑌𝑛−1,), 𝑍𝑘,)
Maxlenght (LCS Rec ( 𝑋𝑚−1,,Y)), or (LCS Rec (X, 𝑌𝑛−1,))

Metode Pemrograman Dinamis

Dari persamaan di atas, dapat dibuat algoritme rekursif dengan waktu eksponensial untuk menghitung panjang sebuah LCS dari dua sekuens. Karena masalah LCS hanya memiliki Θ(mn) sub-masalah berbeda, kita dapat menggunakan pemrograman dinamis untuk menghitung solusi secara bottom up.

Prosedur LCS-Length mengambil dua sekuens X = ⟨x₁, x₂, … , x_m⟩  dan Y = ⟨y₁, y₂, … , y_n⟩ sebagai masukan. Nilai c[i, j] disimpan dalam tabel c[0…m, 0…n], dan menghitung isinya dalam urutan baris. (Prosedur mengisi baris pertama c dari kiri ke kanan, kemudian baris kedua, dan seterusnya.) Prosedur juga menyimpan tabel b[1…m, 1…n] untuk membantu dalam konstruksi solusi optimal. Tentu saja, b[i, j] menunjuk pada isi tabel yang bersesuaian dengan solusi sub-masalah optimal  yang dipilih saat menghitung c[i, j]. Prosedur mengembalikan tabel b dan c; dengan c[m, n] berisi panjang LCS dari X dan Y.

LCS-Length (X, Y)

m = X.length

n = Y.length

let b[1…m, 1…n] and c[0…m, 0…n] be new tables

for i = 1 to m

c[i, 0] = 0

for j = 1 to n

c[0, j] = 0

for i = 1 to m

           for j = 1 to n

                  if x_i == y_j

                 c[i, j] = c[i – 1, j – 1] + 1

                 b[i, j] = “↖”

                  elseif c[i – 1, j] ≥ c[i, j – 1]

                  c[i, j] = c[i – 1, j]

                  b[i, j] = “↑”

                 else

                c[i, j] = c[i, j – 1]

                b[i, j] = “←”

return c and b

Gambar 1 menunjukkan tabel yang dihasilkan oleh LCS-Length untuk sekuens X = ⟨A, B, C, B, D, A, B⟩ dan Y = ⟨B, D, C, A, B⟩. Waktu eksekusi prosedur ini adalah Θ(mn), karena setiap isi tabel membutuhkan waktu Θ(1) untuk menghitungnya.

Konstruksi LCS

Tabel b yang dikembalikan oleh LCS-Length membuat kita lebih cepat dalam mengkonstruksi sebuah LCS dari X = ⟨x₁, x₂, … , x_m⟩  dan Y = ⟨y₁, y₂, … , y_n⟩. Kita mulai dari b[m, n] dan menelusuri tabel dengan mengikuti arah panah. Setiap kita temui tanda “↖” pada isi b[i, j], itu artinya bahwa x_i = y_j adalah elemen LCS yang ditemukan oleh LCS-Length. Dengan metode ini, kita temukan elemen-elemen LCS dalam urutan terbalik. Prosedur rekursif berikut ini mencetak LCS dari X dan Y dalam urutan yang benar. Pemanggilan pertama ialah Print-LCS(b, X, X.length, Y.length).

Print-LCS(b, X, i, j)

if i == 0 or j == 0

return

if b[i, j] == “↖”

Print-LCS(b, X, i – 1, j – 1)

print x_i

elseif b[i, j] == “↑”

Print-LCS(b, X, i – 1, j)

else

Print-LCS(b, X, i , j – 1)

Untuk tabel b pada Gambar 1, prosedur ini akan mencetak BCBA. Prosedur ini memakan waktu O(m + n), karena salah satu i atau j akan berkurang pada tiap panggilan rekursif.

Cormen, Thomas H. Introduction to Algorithm Third Edition. MIT Press, United States of America. 2009.

S. Lu and K. Fu, A sentence-to-sentence clustering procedure for pattern analysis, Transactions on Systems, Man, and Cybernetics, 8 (1978), 381-389.