Menemukan motif DNA sederhana merupakan dasar banyak aplikasi bioinformatika, mulai dari identifikasi start codon hingga pencarian target primer dan situs restriksi.
Hampir semua pertanyaan biologis di level molekuler bisa dirumuskan sebagai "di mana letaknya pola X dalam sekuen Y?". Contoh aplikasinya dapat ditemukan pada beberapa kasus berikut:
Start codon, Setiap protein dimulai dengan kodon ATG (metionin).
Mencari awal sebuah gen = mencari posisi ATG yang relevan.
Restriction site, Enzim restriksi seperti EcoRI memotong DNA persis di
GAATTC. Untuk merancang kloning, kita perlu tahu di mana saja motif itu muncul.
Binding site faktor transkripsi, Misalnya TATA box (TATAAA) di promoter.
Mencari binding site = memprediksi regulasi gen.
Mutasi penyebab penyakit, Mutasi BRCA1 yang terkait kanker payudara seringkali adalah perubahan motif spesifik yang harus kita cari di antara jutaan basa.
Pada pasien dengan demam dan ruam, pendekatan paling dasar adalah memeriksa satu per satu kemungkinan diagnosis: DBD, campak, rubella, atau tifoid. Dalam komputasi, pola ini mirip dengan brute force.
Pendekatan yang lebih efisien menggunakan gejala kunci sebagai filter. Jika ditemukan bercak Koplik, arah diagnosis berubah. Prinsip yang sama digunakan dalam algoritma yang memanfaatkan struktur data agar pencarian lebih efisien.
Modul ini dimulai dari brute force agar mahasiswa memahami dasar masalah sebelum beralih ke alignment dan BLAST.
Algoritma berikut digunakan untuk mencari motif secara langsung:
1. Mulai dari posisi 0 di sekuen.
2. Bandingkan motif dengan substring di posisi tersebut, karakter per karakter.
3. Jika semua karakter cocok → catat sebagai match, naikkan counter.
4. Geser satu posisi ke kanan.
5. Ulangi langkah 2-4 sampai tidak cukup karakter tersisa untuk dicocokkan.
Gunakan tombol "Langkah Berikutnya" untuk memindahkan window pencarian satu posisi. Perhatikan perubahan jumlah perbandingan dan jumlah match.
Perhatikan angka "Total Perbandingan". Untuk sekuen 21 karakter dan motif 3 karakter, kasus terburuk dapat mencapai sekitar 19 × 3 = 57 perbandingan.
Pada genome berukuran besar, jumlah operasi meningkat tajam. Ketika pertanyaan berubah dari pencarian motif eksak menjadi pencarian sekuen yang mirip dengan toleransi mutasi, dibutuhkan strategi yang lebih kuat, termasuk dynamic programming.
Dalam konteks algoritma, efisiensi merujuk pada jumlah langkah komputasi yang dibutuhkan. Jumlah langkah ini biasanya dinyatakan sebagai fungsi dari ukuran input n.
Brute force motif yang kita jalankan tadi, untuk motif pendek, jumlah langkahnya kira-kira sebanding dengan panjang sekuen. Kita sebut ini O(n), "linier", "skala dengan n".
Tapi banyak masalah bioinformatika yang lebih kompleks butuh O(n²) langkah , "kuadratik". Untuk sekuen 100 karakter, perbedaan O(n) vs O(n²) tidak terlalu terasa. Untuk sekuen 10.000 karakter, perbedaannya menjadi dramatis. Mari lihat sendiri.
Bayangkan sebuah klinik laboratorium yang menerima 1.000 sampel per hari. Kalau prosedur lab butuh waktu yang bertambah linier (semakin banyak sampel, antrian semakin panjang dengan kelipatan tetap), skalanya manageable. Tapi kalau waktu prosedur bertambah kuadratik (gandakan sampel, waktu jadi 4× lebih lama), klinik itu akan kolaps.
Hal yang sama berlaku untuk algoritma. Sekuen 1.000 basa dengan algoritma O(n²) butuh 1 juta langkah. Genome 3 miliar basa? 9 × 10¹⁸ langkah, secara fisik tidak mungkin diselesaikan. Itulah kenapa pemilihan algoritma yang tepat = perbedaan antara "selesai dalam 1 detik" dan "tidak akan pernah selesai".
Sampai di sini, kita hanya bertanya: apakah motif ATG ada persis di sekuen?
Jawabannya ya/tidak. Tapi pertanyaan biologis yang lebih realistis adalah:
seberapa mirip dua sekuen ini?
Untuk menjawabnya, kita perlu sistem skor. Tiga komponen dasar yang akan kita pakai sepanjang sisa semester:
Match, kedua karakter sama (A-A, G-G, dst). Skor positif (reward).
Mismatch, kedua karakter berbeda (A-G). Skor negatif (penalty ringan).
Gap, salah satu sekuen "kosong" di posisi itu (sisipan atau hapusan).
Skor sangat negatif (penalty berat).
Dalam biologi, indel (insertion/deletion) sering menyebabkan frameshift mutation , seluruh urutan asam amino setelah titik mutasi berubah, biasanya menghasilkan protein non-fungsional atau truncated. Sementara mismatch (SNP) hanya mengubah satu kodon, kadang tidak berdampak sama sekali (silent mutation).
Kita akan kupas tuntas alasan biologis ini di P3. Untuk sekarang, cukup terima bahwa: match menambah skor, mismatch sedikit mengurangi, gap mengurangi banyak.
Di pertemuan berikutnya, kita akan bertemu pertanyaan yang lebih sulit: diberikan dua sekuen, bagaimana cara mencari alignment dengan skor TERTINGGI?
Brute force akan mencoba semua kemungkinan alignment, yang seperti kita lihat di Bagian 3, jumlahnya astronomis. Solusi cerdasnya adalah Needleman-Wunsch dengan teknik dynamic programming. Tapi sebelum kita ke sana, scoring system yang Anda mainkan di atas harus sudah terasa familiar.
Setelah modul ini, Anda harus bisa:
✓ Menjelaskan algoritma brute force pattern matching dalam langkah-langkah eksplisit.
✓ Memberi contoh kasus nyata pencarian motif dalam bioinformatika (start codon, restriction site, dll).
✓ Membedakan O(n) dan O(n²) secara intuitif tanpa harus tahu matematikanya.
✓ Menjelaskan kenapa pilihan algoritma matters untuk genome berukuran besar.
✓ Mendefinisikan match, mismatch, dan gap dalam konteks alignment.
✓ Memahami kenapa gap penalty biasanya lebih besar dari mismatch penalty.
Di Pertemuan 3, Needleman-Wunsch, kita akan menggunakan scoring system yang Anda mainkan di Widget 3, tapi dalam konteks yang jauh lebih powerful: kita akan menemukan alignment optimal dari dua sekuen menggunakan dynamic programming, teknik yang berhubungan langsung dengan konsep "rekam medis elektronik" yang akan saya jelaskan nanti.