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
Tidak ada komentar:
Posting Komentar