Sebuah Tulisan Bioinformatika - Pencarian Similaritas Database (Part 2)

Hola...kembali lagi bersama saia KohVic di lanjutan cerita pecarian similaritas database. Jika sebelumnya pada Part 1 kita telah mendiskusikan mengenai permasalahan yang dihadapi dalam pencarian database urutan nukleotida/protein, maka pada Part 2 ini kita akan membahas solusinya. Di akhir Part 1 saia berencana untuk membahas salah satu program yang paling terkenal dalam pencarian tersebut, yakni BLAST. Oke, mari kita ikuti di bawah ini.

Well, apakah itu BLAST? BLAST merupakan singkatan dari Basic Local Alignment Search Tool yang mampu mencari urutan di dalam database yang cocok dengan urutan query yang diberikan. BLAST melakukan pencarian similaritas database menggunakan pendekatan heuristik. Bagaimana caranya dan apa bedanya dengan metode dynamic programming? Sebelumnya perkenankan saia untuk menjelaskan apa itu heuristik. Dalam konteks komputasi, pencarian sebuah solusi dapat dilakukan dengan cara exhaustive dan juga heuristik. Pencarian exhaustive dilakukan dengan cara meninjau seluruh solusi yang dapat memecahkan suatu permasalahan lalu membandingkannya untuk mendapatkan solusi terbaik. Dengan pencarian exhaustive ini, solusi terbaik pasti didapatkan atau dengan kata lain pencarian ini memaksimalkan sensitivitas dan spesifisitas. Namun kelemahannya terletak pada kecepatan pencarian solusi tersebut. Di sisi lain, pencarian heuristik mampu melakukan pencarian jauh lebih cepat dibandingkan pencarian exhaustive. Namun demikian, pencarian heuristik yang didasarkan pada proses sampling tidak dapat menjamin bahwa solusi terbaik akan ditemukan.

Bingung? Hmm…saia akan coba menjelaskannya lagi dengan analogi yang sama tidak nyambungnya. Jadi gini, bayangkan bahwa kita berada di lantai tertinggi sebuah mal baru dan kita ingin menuju pintu keluar yang terletak di lantai dasar. Jika kita memiliki pemikiran serupa dengan pencarian exhaustive, kita akan menelusuri setiap jengkal lantai atas tersebut, memetakan setiap jalan yang dapat ditempuh untuk menuju lantai bawah dan kemudian menentukan mana solusi terbaik (dalam hal ini, tercepat) untuk menuju ke lantai bawah. Dalam perjalanannya kita mungkin menemukan tangga darurat, eskalator dan elevator. Setelah membandingkan ketiganya, kita menyimpulkan bahwa elevator merupakan yang tercepat, sehingga itu merupakan solusi terbaik untuk membawa kita menuju lantai bawan dan kemudian pintu keluar. Di sisi lain, pemikiran secara heuristik tidak akan mengevaluasi seluruh jengkal lantai atas tersebut (kurang kerjaan apa?) namun akan langsung mencari jalur yang membawa menuju ke lantai bawah dan menganggapnya sebagai yang tercepat. Dengan asumsi bahwa tempat itu merupakan sebuah mal, maka saia menyimpulkan jumlah eskalator lebih banyak tersebar dibandingkan dengan elevator dan tangga darurat yang cenderung terpusat di tempat tertentu. Nah, jika kita berpikiran secara heuristik (dan memang seperti itulah pemikiran kita), kita akan mengambil eskalator terdekat untuk menuju satu lantai kebawah, mencari eskalator lainnya, menuju satu lantai lagi ke bawah dan seterusnya hingga mencapai lantai dasar dan pintu keluar. Pencarian solusi secara heuristik, yakni mencari eskalator terdekat jelas lebih praktis dibandingkan menyisir setiap jengkal lantai tertinggi itu untuk mencari solusi lain yang lebih optimal (dalam hal ini elevator).

Nah, apa hubungannya antara cerita di atas dengan BLAST? Well, agak blur sih…tapi yang penting sekarang kita mendapatkan pesan moral mengenai exhaustive dan heuristik. Nah perlu diingat bahwa dalam BLAST, kita membandingkan sebuah urutan masukan (query) dengan 185 juta urutan lainnya di dalam database GenBank. So, apa kesimpulannya? Err..kesimpulannya adalah sebaiknya saia tidur siang saja. No!! kesimpulannya adalah sebagian besar dari 185 juta urutan tersebut tentunya tidak berhubungan dengan query kita, sehingga kita perlu mendesain strategi yang dapat memisahkan sebagian besar urutan tersebut agar tidak dibandingkan dengan urutan query kita. Nah Stephen Altschul, si empunya BLAST ini mengimplementasikan trik jenius untuk pemisahan tersebut. Dalam algoritmanya, BLAST akan memecah urutan query menjadi sekelompok kombinasi “kata-kata” berukuran pendek (hanya puluhan nukleotida/asam amino) sebagai alat untuk menyeleksi urutan database mana yang berhubungan dan mana yang tidak.

 

Gambar 1. Skema BLAST

Secara teknis, terdapat tiga tahapan dalam BLAST, yakni (i) seeding, (ii) extension, dan (iii) result display. Seluruh tahapan itu saia muat dalam Gambar 1. Tahap seeding merupakan tahap pembuatan “kata” dari query yang dimasukkan. Nantinya, “kata” tersebut akan bertindak sebagai penyeleksi urutan yang berhubungan atau tidak di dalam database. Tahap seeding akan menghasilkan sejumlah urutan kandidat yang akan diteruskan pada tahap selanjutnya, yakni tahap extension. Pada tahap extension ini, pencocokan akan dimulai dari lokasi pasangan kata dan diperpanjang ke sisi kiri dan kanan pasangan urutan. Selama tahap extension ini akan dihtung juga skor HSP (high-scoring segment pair) dari masing-masing pasangan urutan. Skor HSP ini akan digunakan sebagai dasar penentuan peringkat kecocokan urutan database terhadap urutan query pada tahap result display.

Mudah kan? Ada pertanyaan? Oke, saia yakin bahwa pertanyaannya pasti akan menyangkut soal definisi “cocok”. Dalam hal ini, kecocokan didefinisikan sebagai sebuah skor yang sama atau melebihi sebuah ambang batas minimal. Lalu bagaimana caranya menghitung skor kecocokan semacam itu. Disini, BLAST menggunakan matriks skor substitusi asam amino. Terdapat beberapa matriks semacam itu, di antaranya PAM120, BLOSUM62, JTT, dan lainnya. Matriks tersebut berisikan skor untuk setiap kombinasi pasangan asam amino yang dibuat dari analisis konservasi pola asam amino dalam molekul protein yang berkerabat dekat. Pasangan asam amino yang mirip sifat fisikokimiawinya cenderung memiliki skor positif dan demikian juga sebaliknya, pasangan yang berbeda sifat fisikokimiawinya cenderung memiliki skor negatif. Jadi, dengan panduan matriks skor tersebut, kita dapat menghitung skor masing-masing pasangan urutan query dengan urutan database.

Hmm…sebenarnya saia mau melanjutkan ke program PSD berikutnya yang mungkin pernah kita dengar namun kurang terkenal. Namanya adalah FASTA. Ya sudahlah, rincian mengenai program FASTA itu akan saia bahas pada part berikutnya. Ditunggu yahh!!!

Salam,

KohVic