Perpustakaan Digital ITB

Sequence alignment merupakan perangkat penting dalam bidang biologi dalam melakukan perbandingan sequence, yaitu sebelum melakukan analisis sequence secara struktural maupun fungsional. Membandingkan sequence dengan sequence alignment adalah mencari solusi optimal yaitu berupa pasangan-pasangan residu sequence dengan kumulatif skor similaritas terbaik. Skor dipilih dengan mempertimbangkan bobot kecocokan pasangan residu yang merepresentasikan karakteristik biologi. Dynamic Programming (DP) merupakan algoritma klasik untuk solusi problem optimasi. Algoritma ini masih menjadi algoritma utama dalam berbagai perangkat sequence alignment. Karakterisktik DP yang memeriksa semua ruang solusi menjamin diperolehnya solusi optimal, tetapi membutuhkan waktu komputasi tinggi. Pada ukuran tertentu waktu komputasi DP menjadi tidak realistis. Bit-parallelism adalah salah satu solusi pada problem approximate string matching yang memperbaiki kinerja algoritma DP dan automaton . Bit-parallelism memperbaiki proses komputasi dengan menggabungkan unit proses menjadi satu unit baru pemrosesan unit baru seperti memproses paralel unit-unit proses asalnya. Penggabungan ini mengadaptasi pemrosesan bit-bit dalam word pada sistem komputer. Penggabungan proses mereduksi waktu komputasi. Transformasi diperlukan untuk menjadikan bentuk gabungan unit proses menyerupai sebuah word. Identifikasi algoritma pada bentuk yang baru juga diperlukan untuk menghasilkan komputasi dalam unit-unit yang lebih efisien. Bit-parallelism telah diterapkan pada kasus Longest Common Subsequences (LCS) dan Edit Distance yang menggunakan bobot similaritas biner, yaitu merepresentasikan cocok dan tidak. Sequence alignment pada kasus biologi memiliki karakteristik khusus. Kecocokan pasangan karakter direpresentasikan dalam nilai-nilai bobot integer. Bobot DNA terdiri dari satu bobot kecocokan, satu bobot integer ketidakcocokan dan satu bobot integer penyisipan gap. Protein membutuhkan lebih banyak representasi bobot kecocokan, karena ada 24 residu pembentuk sequence protein. Ada beberapa nilai integer diperlukan untuk merepresentasikan derajat kecocokan, demikian juga untuk derajat ketidakcocokan. Disertasi ini menyajikan desain komputasi skor bit-parallelism dengan bobot multi integer untuk menjawab kebutuhan biological sequence alignment, khususnya sequence protein. Desain komputasi disusun dari pengembangan komputasi skor General Integer scoring 2 dimana komputasi disusun dari operasi logik status kemunculan variabel-variabel integer pada algoritma komputasi skor. General integer scoring sudah bisa menjawab kebutuhan komputasi skor untuk DNA, tetapi belum untuk protein. Pengujian empiris komputasi skor pada sejumlah pasangan sequence dan dengan panjang masing-masing dan menunjukkan bahwa desain komputasi Bit-parallelism bobot multi integer terbukti telah menjawab kebutuhan komputasi pairwise sequence alignment pada protein yang menggunakan bobot dari tabel subtitusi protein, yaitu dengan memberikan skor alignment yang sama dengan DP klasik. Komputasi Bit-parallelism ini juga mampu mengefisienkan komputasi a DP, dari ????(????????) menjadi ????(????), hal ini didukung dari hasil pengujian empiris yang mengasumsikan terbesar saat ini adalah 64 bit, dapat memberikan efisiensi proses sampai dengan kisaran 30-70%. Komputasi membutuhkan ruang komputasi ????(????), dimana k adalah rentang nilai pada set bobot yang digunakan.