Jumat, 02 Agustus 2013

Sebuah Tulisan Evolusi dan Filogeni: Sequence Alignment (In Depth) Part 1

Wuoooo...lama sudah saia menghilang dari dunia ini dalam rangka mencari pencerahan penelitian tesis saia. Hari ini, yaa tepatnya malam ini saia pun ingin mencoba peruntungan saia dalam membuat tulisan salah satu dalam serial Sebuah Tulisan Evolusi dan Filogeni. Well, judulnya masih terkait dengan tulisan sebelumnya yang berjudul "Sebuah Tulisan Evolusi dan Filogeni: Homologi dan Alignment". Namun pada tulisan kali ini saia ingin menekankan kepada alignment itu sendiri. Yasuda, kita mulai saja yak :)

Sequence alignment dapat didefinisikan sebagai sebuah proses penjejeran dua atau lebih sequence (nukleotida atau asam amino) sehingga keduanya memiliki kemiripan setinggi mungkin dalam hal posisi karakter penyusun sequence-nya. Dengan demikian, sequence alignment merupakan proses yang dilakukan berdasarkan asumsi homologi, yakni sebuah pandangan bahwa sequence homolog dulunya berasal dari satu sequence nenek moyang yang berdivergensi akibat mutasi dan seleksi.

Nah, sekarang ketika kita menghadapi sebuah dataset berisi sequence, bagaimana caranya kita untuk meng-align sequence-sequence tersebut satu sama lain hingga tercapai kemiripan tertinggi secara keseluruhan? Oh ya mudah saja, tinggal masukan ke program komputer, klik "OK" atau "Compute", tunggu beberapa saat dan cling...wuala this is it!! sequence alignment ala chef...oops...ehem. Yaa mungkin kita bisa dengan mudahnya langsung menggunakan cara tersebut. Namun, tahukah kita bahwa akurasi dari sebuah analisis filogenetik yang paling mendasar justru terletak pada sequence alignment yang digunakan? Nah untuk itulah memahami bagaimana sebuah proses sequence alignment ini menjadi sangat penting, sekalipun nantinya kita akan meminta bantuan komputer untuk melakukan sisanya. Dalam menangani dataset sequence proses alignment dibagi menjadi dua tahap, yakni alignment pasangan sequence (pairwise sequence alignment) dan alignment banyak sequence (multiple sequence alignment). Dalam tulisan ini saia akan membahas mengenai Pairwise Sequence Alignment terlebih dahulu.

Secara umum terdapat tiga teknik dalam pairwise sequence alignment, yakni: (1) secara visual, (2) menggunakan dot-matrix, dan (3) menggunakan dynamic programming algorithm. Kita akan membahasa satu per satu. Alignment secara visual merupakan teknik yang paling sederhana, cepat, sekaligus akurat. Hal ini disebabkan karena otak kita mampu mengintegrasikan seluruh informasi tambahan kepada pasangan sequence yang sedang di-align. Namun demikian, alignment secara visual-manual ini juga memiliki keterbatasan  terhadap panjang sequence dan juga keteraturannya. Ketika seuatu pasangan sequence terlalu panjang dan semakin tidak teratur, maka dijamin otak kita akan overheat dibuatnya.

Teknik kedua adalah dengan alat bantu yang bernama dot-matrix. Ini merupakan suatu matriks dimana kita bisa menempatkan pasangan sequence pada bagian kolom dan baris sehingga kita bisa mencocokannya sekaligus juga membuat alignment darinya. Cara melakukannya akan dijelaskan di bawah ini dan untuk lebih jelasnya dapat dilihat pada Gambar 1:
1. Letakkan sequence pertama pada bagian atas matriks (kolom) dan sequence kedua pada bagian kiri matriks (baris).
2. Berikan tanda titik (dot) pada setiap karakter yang cocok antara kedua sequence tersebut.
3. Hubungkan antara titik satu dengan lainnya. Apabila pasangan sequence tersebut adalah identik atau mirip antara satu dengan lainnya, maka akan terbentuk sebuah garis diagonal pad matriks tersebut.
Perlu diketahui bahwa garis penghubung antar titik dalam dot-matrix tidak selamanya diagonal. Adanya insersi-delesi (indel) pada sequence dapat mengubah garis tersebut menjadi vertikal atau horizontal. Garis vertikal mencerminkan adanya delesi pada sequence pertama atau insersi pada sequence kedua dan garis horizontal adalah sebaliknya. Terkadang garis diagonal yang dibuat pun tidak selalu melewati seluruh titik yang ada. Apabila ada suatu elemen kosong (tanpa tanda titik) dalam matriks yang dilewati oleh garis, maka itu menandakan adanya substitusi pada yang terjadi antara kedua sequence yang dibandingkan.
Gambar 1. Dot-matrix sequence alignment.
Penarikan garis dalam dot-matrix terkadang juga menghasilkan lebih dari satu garis. Hal ini berarti ada lebih dari satu skenario alignment yang perlu dipertimbangkan. Gambar 2 memberikan contoh kasus dimana terdapat dua skenario yang dapat dipakai dalam alignment pasangan sequence. Skenario pertama memberikan alignment dengan dua buah substitusi dan satu buah gap, sementara skenario kedua memberikan alignment dengan lima buah gap dan tanpa substitusi.
Gambar 2. Two possible alignment scenarios.
Penggunaan dot-matrix dalam alignment pasangan sequence cukup bagus untuk dilakukan pada sequence yang pendek. Seiring dengan semakin bertambahnya panjang sequence, maka titik yang muncul dalam dot-matrix akan semakin banyak. Hal ini disebabkan suatu pasangan sequence nukleotida yang hanya memiliki empat karakter (A, T, G, dan C) memiliki probabilitas kesamaan posisi nukleotida sebesar 25%. Dengan demikian, seiring dengan semakin panjangnya suatu sequence, akan semakin banyak terdapat garis-garis diagonal atau alignment semu akibat kemiripan nukleotida secara kebetulan ini.

Untuk mengatasi masalah ini, dikembangkan metode pemberian skor (scoring) untuk menghasilkan sebuah alignment yang bagus. Salah satu metode yang umum digunakan didasarkan pada nilai similaritas nukleotida antar pasangan sequence yang kemudian diadaptasi dalam program komputer. Metode ini disebut juga dengan Needleman-Wunsch Dynamic Programming Algoritm atau yang lebih sering disebut sebagai Dynamic Programming.  Algoritme ini mengikuti Bellman's Optimality Principle yang berbunyi "if the final element reports the score for the best path, then the sub-solution leading to this element is also lying on the optimal path."

Nah berdasarkan prinsip Oom Bellman tersebut tentunya skor perlu diberikan dalam setiap elemen di dalam matriks alignment nya. Terdapat sedikit perbedaan dalam pemberian skor untuk alignment sequence nukleotida dan asam amino, dimana pemberian skor dalam sequence nukleotida biasanya bernilai 1 dan kelipatannya. Hal ini didasarkan pada asumsi bahwa substitusi pada nukleotida bersifat simetris/sama dari satu nukleotida ke nukleotida lainnya. Asumsi ini tidak berlaku pada sequence asam amino karena adanya pertimbangan sifat biokimia rantai sampingnya. Dalam tulisan ini saia akan memakan sequence nukleotida sebagai contohnya.

Gambar 3. Dynamic programming sequence alignment.
Pemberian skor didasarkan pada kesamaan nukleotida dari sequence pertama dengan sequence kedua. Apabila sama, maka elemen dalam matriks mendapatkan tambahan nilai 1. Apabila tidak maka skornya 0. Pemberian skor ini dilakukan secara berurut dari kiri ke kanan dan atas ke bawah. Nah sekarang coba perhatikan Gambar 3. Skor 1 diberikan pada elemen baris pertama kolom pertama di dalam matriks karena kedua sequence sama-sama memiliki nukleotida A. Kenapa nilainya 1? itu karena nilai awal dalam mengisi suatu alignment adalah nol akibat tidak ada yang dibandingkan, sehingga nilai 1 pada elemen pertama itu adalah hasil dari penjumlahan 0+1=1. Selanjutnya kita akan mengisi elemen lainnya dari kiri ke kanan. Elemen lainnya pada baris pertama diisi dengan nilai 0 karena selain seperti hal di atas yakni tidak ada nukleotida sebelumnya yang bisa dibandingkan, nukleotida A pada sequence kedua (baris pertama) tidak cocok dengan nukleotida lainnya pada sequence pertama (kolom kedua hingga kelima). Masih bertahan di Gambar 3, sekarang coba perhatikan elemen pada baris kedua kolom kedua. Kedua sequence sama-sama memiliki nukleotida T dan itu berarti cocok. Dengan demikian skor tambahan 1 diberikan pada elemen ini. Perhatikan bahwa ada elemen yang sebelumnya telah mendapat nilai 1. Hal ini berarti elemen pada baris kedua kolom kedua bernilai 2 sebagai akibat dari skor 1 dari elemen sebelumnya tersebut ditambah skor 1 dari kecocokan nukleotida pada elemen ini. Pengisian elemen ini dilakukan dengan cara seperti itu hingga semuanya terisi.

Setelah semuanya terisi, maka selanjutnya kita akan menggambarkan penunjuk (pointer) untuk membantu kita mengarahkan dari elemen mana skor-skor tersebut berasal. Suatu penunjuk digambar dari elemen pojok kanan bawah ke elemen yang terletak di sebelah kiri atasnya yang memiliki skor sama atau lebih rendah dari elemen tersebut (Gambar 3, tengah). Sesudah itu kita kemudian dapat menentukan mana alignment yang terbaik berdasarkan penunjuk ini. Sebuah prosedur yang dinamakan sebagai Traceback untuk menghasilkan suatu grafik arah (Path Graph). Prinsip traceback ini didasarkan pada prinsip Oom Bellman di atas dan dimulai dari elemen ujung kanan bawah yang memiliki skor tertinggi. Pada Gambar 3 (kanan) kita melihat bahwa elemen ujung kanan bawah dengan skor tertinggi adalah 4, maka dari titik inilah kita membuat alignment untuk kedua sequence yang dibandingkan. Yup, sequence alignment menggunakan metode ini dibuat dari kanan ke kiri. Berdasarkan path graph yang dihasilkan dari proses traceback, maka kita dapat menghasilkan alignment nya.

Perlu diketahui bahwa proses alignment yang dijelaskan di atas belum mengikutsertakan gap penalty akibat adanya gap/indel yang terbentuk selama proses alignment. Umumnya kita menganggap bahwa indel lebih jarang terjadi dibandingkan dengan substitusi, sehingga sebuah alignment dengan jumlah gap yang lebih banyak ketimbang residu nukleotidanya seperti contoh di bawah ini tentu tidak masuk akal:

VHLTPEEKSAVTALWGKVNVDEVGGEAL...
V-----------------NEEEVGGEAL...

Nah untuk menghindari adanya alignment seperti ini, gap penalty perlu dintegrasikan ke dalam algoritme alignment. Detail mengenai gap penalty dapat dibaca lebih lanjut dalam buku-buku analisis filogenetik lainnya seperti Graur & Li (1991) atau Nei & Kumar (2000).

Oke, saia rasa tulisan kali ini saia cukupkan hingga disini dulu. Selanjutnya saia akan membahas tentang multiple sequence alignment, yakni bagaimana proses alignment untuk lebih dari dua sequence. Ditunggu yak!!

Regards,
Victor Apriel (KohVic)

2 komentar:

Unknown mengatakan...

salam kenal...
s2 math juga belajar bioinformatika hehe... thanx bwt sharing ilmunya... ijin copas yaaa referensinyaaa

Anonim mengatakan...

Salam kenal juga. Maaf saia belakangn ini jarang buka blog ini. Okay, silahkan copy.