Sebuah Tulisan Bioinformatika – Pencarian Similaritas Database (Part 3)

Hola lagi…

Setelah kemarin membahas tentang cara kerja salah satu program PSD yang paling banyak dikenal, kita akan lanjut ke program PSD lainnya. Nama program PSD tersebut adalah FASTA, yang diciptakan oleh William R. Pearson dan David J. Lipman. Hmm…ternyata fakta sejarah menunjukkan bahwa FASTA dibuat sebelum adanya BLAST, atau dengan kata lain FASTA merupakan program PSD paling awal yang pernah dibuat. FASTA dipublikasikan pada tahun 1988, dua tahun sebelum BLAST dipublikasikan oleh Oom Altschul dan kawan-kawan. Kalau sekarang teman-teman melihat publikasi pertama BLAST, kalian akan melihat David J. Lipman sebagai salah satu co-author di dalamnya.

Well, cukup untuk pelajaran sejarahnya. Sekarang mari kita masuk ke dalam topik. Bahasan kita pada tulisan ini adalah bagaimana cara kerja FASTA sebagai sebuah program PSD. Ternyata strategi yang digunakan oleh FASTA dalam pencarian similaritas cukup berbeda dari BLAST. Program pencarian ini menggunakan strategi hashing untuk mencari rangkaian pendek tanpa celah dengan panjang k yang cocok antar pasangan urutan. Rangkaian pendek ini disebut sebagai ktuples atau ktups yang mirip dengan kata pada BLAST. Strategi hashing sendiri merupakan salah satu teknik pemilahan objek ke dalam kategori tertentu berdasarkan prasyarat tertentu.

Secara keseluruhan, saia akan membagi cara kerja FASTA ke dalam tiga tahapan, yakni (i) identifikasi dan pemetaan ktups, (ii) seleksi ktups, dan (iii) penggabungan ktups. Secara garis besar, keseluruhan tiga tahapan ini mirip dengan teknik dynamic programming yang dipercepat (Gambar 2). Sebelum kita membahas tentang tiga tahapan tersebut, mari kita sejenak melihat tahapan identifikasi ktups yang menjadi titik awal sebelum proses pemetaannya. Tahapan identifikasi ktups dimulai dengan membandingkan dua buah urutan (urutan query dan urutan database) dan kemudian memasukkan posisi dari setiap residu nukleotida atau asam amino yang ada ke dalam tabel hash (Gambar 1). Selanjutnya, dari tabel hash tersebut kita dapat melihat residu apa saja yang memiliki selisih posisi yang sama. Kelompok residu dengan selisih posisi yang sama menandakan bahwa mereka terletak bersebelahan dan oleh karena itu jajaran keduanya pada posisi tersebut dapat diperoleh dengan memasukan sejumlah celah (gap). Nah setelah identifikasi selesai, kita akan mendapatkan sebuah jajaran pasangan urutan dengan sejumlah daerah dengan residu identik tanpa celah antar satu urutan dengan lainnya, inilah yang disebut sebagai ktups.

Gambar 1. Skema identifikasi ktups.

Normalnya, setiap pasangan urutan yang homolog pasti memiliki jumlah ktups yang jauh lebih banyak dibandingkan dengan pasangan yang tidak berkaitan sama sekali. Dengan kriteria ini, maka FASTA dapat menyaring kandidat urutan database mana yang berhubungan dengan yang tidak dengan cara memetakan ktups untuk seluruh pasangan urutan dan kemudian menyeleksinya berdasarkan ambang minimal panjang ktups tertentu (Gambar 2). Setelah tahap seleksi, hanya akan tersisa  ktups-ktups panjang yang akan dilanjutkan dengan tahap penggabungan ktups. Proses penggabungan ini menggunakan metode dynamic programming. Proses penggabungan ini relatif lebih cepat dibandingkan dynamic programming konvensional karena segmen pemisah antar dua ktups relatif pendek. Setelah semua ktups digabungkan kemudian akan dihitung skor similaritasnya dan kemudian di-ranking deh.

Gambar 2. Skema kerja FASTA

Jika dibandingkan, metode BLAST dan FASTA sama baiknya dalam melakukan pencarian similaritas. Perbedaan keduanya secara garis besar terletak pada tahap seeding, dimana BLAST menggunakan matriks skor sedangkan FASTA menggunakan strategi hashing, Dalam urusan kecepatan, BLAST lebih cepat dibanding FASTA karena tahapan seedingnya yang didasarkan pada sebagian kecil daerah di dalam pasangan urutan lebih efisien dibandingkan dengan membandingkan seluruh daerah antar pasangan urutan untuk dimasukkan ke dalam tabel hash. Namun demikian, perbandingan secara menyeluruh ini membuat FASTA lebih sensitif serta spesifik dalam memberikan kandidat urutan yang akan diteruskan ke tahap selanjutnya (seleksi dan penggabungan ktups).

Baik BLAST maupun FASTA menyajikan hasil dengan cara yang sama, yakni mengurutkan urutan database dari skor similaritas yang tertinggi hingga terendah. Namun demikian, selain daripada skor similaritas (atau hit) tersebut, terdapat parameter statistik lain yang membantu meyakinkan kita apakah urutan yang satu lebih mirip dengan yang lain secara signifikan. Well, parameter-parameter tersebut akan saia coba bahas pada tulisan berikutnya. Ditunggu yah :)

Salam,

KohVic

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

Sebuah Tulisan Bioinformatika - Pencarian Similaritas database (Part 1)

Apa yang paling sering kita dengar jika kita adalah seorang peneliti biologi molekular? Ya, jawabannya adalah "sequencing". Di jaman sekarang ini, kemajuan teknologi biologi molekular telah "mempermudah" para penelitinya untuk langsung memasuki inti daripada keanekaragaman hayati, yakni urutan molekul biologis. Dengan demikian, jika seseorang berhasil mengisolasi DNA atau protein, maka tindakan berikutnya adalah SEQUENCING, walaupun yang belakangan seringkali di-bypass menggunakan ilmu prediksi gen dan penggunaan tabel kode genetik alih-alih sequencing langsung molekul proteinnya.

Well, lantas setelah proses sequencing, kata apakah yang paling sering kita dengar sebagai konsekuensi kelanjutannya? Pernahkah kita semua mendengar kalimat "di-BLAST saja"? Ya, proses berikutnya adalah mem-BLAST-kan urutan DNA atau protein yang telah didapatkan. Namun demikian, apakah BLAST itu dan bagaimana cara kerjanya? Apakah ada alternatif lain selain daripada BLAST? Pertanyaan-pertanyaan itulah yang akan mengawali diskusi kita kali ini.

BLAST dan program sejenis lainnya tergolong ke dalam kelompok program pencarian similaritas database (PSD). Program-program tersebut ibarat Google Search-nya  urutan molekular. Dengan input sebuah urutan DNA atau protein (query), program PSD akan menelusuri database terkait untuk mencarikan urutan yang mirip dengan urutan query. Well, mudah kan? hanya sebatas itu. Namun mari kita coba pikirkan lagi menggunakan analogi berikut. Jika teman-teman sedang terhubung pada internet, coba buka laman berikut: https://en.wikipedia.org/?title=Bioinformatics dan bacalah dua paragraf pertama. Sudah? Nah berikutnya saia akan mengajukan dua pertanyaan berikut:

1. Ada berapa kata "bioinformatics" di dalam dua paragraf tersebut?

2. Bagaimana cara mendapatkan angka tersebut?

Oke, saia juga akan menjawab dua pertanyaan tersebut. Jawabannya ada lima buah dan saia mendapatkan angka tersebut dengan cara mengetikkan kata "bioinformatics" pada kolom search (Ctrl+F). Err..tunggu, yang diminta pada pertanyaan kedua adalah logikanya yah. Okay, jadi saia mencarinya dengan menyisir kedua paragraf tersebut dari awal hingga akhir dan kemudian menandai setiap kata "bioinformatics" yang saia temukan. Oke masalah selesai, lalu apa lagi? Nah sekarang mari kita coba kembangkan permasalah dua paragraf ini menjadi jutaan paragraf dan saia akan mengulang dua pertanyaan di atas kepada teman-teman. Saya sangat yakin dan optimis bahwa jawabannya pasti bisa. Namun jika saia tambah dengan pertanyaan ketiga, yang berbunyi:

3. Berapa lama waktu yang Anda butuhkan untuk menjawab pertanyaan nomor 1 dan 2?

Apa jawabannya? Mungkin sejam, sehari, sebulan, setahun, satu dekade..yaa tergantung dari tingkat kerajinan kita masing-masing...hehehe.

Nah inilah alkisah mengenai pencarian similaritas database. Jika seluruh peneliti biologi molekular memasukkan urutan hasil sequencing mereka ke dalam sebuah database, maka coba bayangkan seberapa cepat pertumbuhan data di dalam database tersebut per tahunnya. Yaa ini cukup sulit untuk dibayangkan, jadi silahkan lihat saja di laman berikut: http://www.ncbi.nlm.nih.gov/genbank/statistics. Jika kita mencari, katakanlah, urutan gen 16S rRNA dari sebuah bakteri yang panjangnya 1500 nukleotida, itu artinya kita harus mencari pola sepanjang 1500 di dalam kumpulan 189 milyar nukleotida. Itu sih ibarat mencari jarum di dalam tumpukan jerami, yang berarti urutan tersebut pasti bisa ditemukan namun akan butuh waktu sangat sangat lama untuk menemukannya. Bagi teman-teman yang mengikuti tulisan saia, mungkin ada yang mendapatkan ide untuk mengaplikasikan teknik dynamic programming untuk menjawab masalah ini. Namun demikian, ternyata masalah kecepatan proses juga menjadi hambatan utama bagi teknik tersebut.

Metode Pencarian similaritas database memiliki tiga kriteria yang harus dipenuhi, yakni sensitivitas, spesifisitas/selektivitas, dan kecepatan. Sensitivitas berarti kemampuan sebuah program PSD untuk mencari sebanyak mungkin urutan di dalam database yang berkaitan dengan urutan query. Spesifisitas/selektivitas merupakan kemampuan program PSD untuk mengeluarkan urutan database yang mirip namun tidak berhubungan (false positive). Terakhir, kecepatan merupakan waktu yang diperlukan oleh program PSD untuk menyelesaikan proses pencarian. Dalam pengembangannya, sebuah program PSD ternyata tidak mampu memenuhi ketiga kriteria tersebut secara optimal. Peningkatan sensitivitas berarti menurunkan spesifisitasnya. Jika kita mengoptimalkan sensitivitas dan spesifisitas, maka hal tersebut akan menurunkan kecepatannya. Seringkali, kecepatan merupakan kriteria yang paling diutamakan dalam pencarian similaritas database. Yaa tentu saja kita tidak ingin duduk diam di depan layar komputer dengan tulisan "LOADING" atau "SEARCHING IN PROGRESS" secara terus-menerus toh.

Berpindah sejenak ke permasalahan kombinatorik, jumlah kasar total kombinasi jajaran (alignment) yang dapat diperoleh dari sepasang urutan adalah produk dari panjang kedua urutan tersebut. Hal ini berarti jika kita memiliki sepasang urutan dengan panjang masing-masing 100 dan 95 nukleotida, maka total kombinasi yang muncul adalah 100 x 95 alignment. Lalu bagaimana jika menggunakan kasus di atas, yakni 1500 x 189 milyar? Well, hitung sendiri yah. Pesan moral dari paragraf ini adalah, pencarian seluruh kombinasi (atau istilahnya pencarian exhaustive / brute force) ini secara praktis tidak mungkin untuk dilakukan. Kita butuh teknik yang lebih cepat dari itu.

Teknik lain, yakni teknik pencarian heuristik memberikan alternatif solusi untuk permasalahan ini. Jika didefinisikan, pencarian heuristik adalah pencarian berbasis sampling. Hal ini membuat pencarian heuristik hanya mengevaluasi sampel kombinasi dan menetukan solusi terbaik alih-alih mengevaluasi total kombinasi yang ada. BLAST merupakan salah satu program PSD yang berbasis heuristik ini.

Well, inilah akhir dari Part 1. Saia sih berharap dari teman-teman pembaca sekalian ada yang cukup penasaran mengenai kelanjutannya. Ditunggu yah Part 2-nya...hehehe

Regards,

KohVic