Penyejajaran DNA

Apa yang membuat kamu beda? Secara genetika jawabannya adalah susunan rantai DNA. DNA atau ribonucleid acids merupakan salah satu dari dua jenis asam nukleat yang kita miliki dan menjadi dasar pembuatan protein. Kode DNA tersusun atas urutan empat basa yang berbeda, yaitu A, G, C, dan T, sehingga DNA dapat dipandang sebagai barisan panjang yang dibentuk oleh empat huruf. Susunan barisan ini membentuk sebuah bank data yang berisikan semua informasi tentang mahluk hidup dan melandasi perbedaan pada tiap species.

 

Susunan DNA dapat dimanfaatkan sebagai indentifikasi forensik, seperti penentuan identitas tunggal seseorang, penentuan kecocokan organ terhadap resipien dalam transplantasi, dan mengidentifikasi makanan yang boleh dimakan, juga indentifikasi penyakit. Banyak penyakit yang bersumber pada kerusakan susunan DNA atau karena kehadiran atau keabsenan gen tertentu. Fakta ini membuat teknologi untuk mengidentifikasi DNA berkembang. Salah satu masalah dalam perkembangan teknologi  ini adalah masalah bagaimana menentukan derajat kesamaan dua urutan DNA yang berbeda?

 

Penyejajaran Umum

 

Untuk dapat mendeteksi kesamaan atau perpedaan antara dua barisan kode DNA, salah satu caranya adalah melakukan penjajaran kedua barisan itu. Misalkan diberikan dua barisan kode DNA dengan panjang tidak harus sama. Ide utama penjajaran adalah memberikan gap (ditulis sebagai tanda hubung) secara acak pada posisi tertentu barisan kode yang panjangnya lebih pendek sehingga didapat barisan kode baru yang panjangnya sama dengan barisan kode lainnya. Sebagai contoh

 

  1. Pandang dua barisan tersebut sebagai komponen baris dari matriks berukuran 2 x panjang DNA terpanjang.
  2. Beri bobot setiap kolom: +1 jika ditemukan dua kode yang identik pada kolom itu, -1 jika ditemukan dua kode yang tidak identik dan -2 jika ditemukan kode dan gap. Sebutlah masing-masing kondisi sebagai cocok, tidak cocok, dan gap secara berurutan.
  3. Definisikan skor dua barisan kode DNA itu sebagai +1 x (#cocok) -1 x (#tidak cocok) – 2 x (#gap).

 

Masalah utama penjajaran ini adalah mencari penjajaran efektif sehingga didapat skor maksimum.

 

Sebagai contoh, misalkan A adalah barisan GACGGATTAG dan barisan B, GATCGGAATAG. Salah satu selesain penjajaran antara A dan B adalah dengan menambahkan gap sebagai suku ke-3 pada barisan A, yaitu

 

G   A       C   G   G   A   T    T    A   G

G   A   T    C   G   G   A   A   T    A   G

+1  +1  -2   +1  +1  +1  +1  -1   +1  +1  +1                   

 

Sehingga didapat skor(A, B) = 9.

 

Kita dapat pula mendefinisikan pemberian skor yang lebih umum: +c jika cocok, -t jika tidak cocok, dan -g jika gap, sehingga skornya adalah +c x (#cocok) – t x (#tidak cocok) -g x (#gap). Misalkan S matriks penjajaran dan S(a,b) adalah skor kecocokan karakter a dan karakter b. Sebagai kasus mainan gap sudah dipertimbangkan di S. Kasus lainnya yang lebih nyata adalah gap diperlakukan berbeda alias tersendiri karena pemberian bobot gap harus tergantung pada frekuensi kemunculan gap. Pada kasus ini kita tidak ingin memberi bobot yang sama untuk gap pada kemunculan pertama dengan gap pada kemunculan setelahnya karena nyatanya kemungkinan muncul gap setelah ada gap sebelumnya lebih besar dibandingkan kemungkinan gap muncul pertama kali. Sehingga akan didapat fungsi gap non-linier diluar cakupan S.

 

Penyelesaian paling alami untuk masalah pencarian penjajaran efektif adalah dengan mengaplikasika algoritma greedy, si tamak, yang mendaftarkan semua kemungkinan penjajaran dan baru dicari mana yang menghasilkan skor maksimum. Sayangnya, banyaknya kemungkinan penjajaran yang mungkin berkembang secara eksponensial seiring dengan panjang barisan, sehingga penerapan algoritma ini akan sangat lambat.

 

Jadi kita sudah punya cukup masalah untuk dimodelkan. Bersambung..

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s