Sidang Tugas Akhir

Dian Nugraha
g54070045

Pengoptimuman Alignment Struktur Protein Menggunakan Permasalahan Maksimum Clique

Protein adalah bio-makromolekul yang terbentuk dari rangkaian asam-asam amino yang terikat satu sama lain dalam ikatan peptida. Saat protein melipat, asam-asam amino yang berada dalam rangkaian polipeptida akan saling berdekatan dan membentuk suatu hubungan kontak antara satu sama lain. Hubungan kontak yang terjadi dapat direpresentasikan secara simetri sebagai contact map. Contact map dalam protein dinyatakan sebagai suatu graf takberarah dengan vertek menyatakan asam amino dan edge antara dua verteks menyatakan keadaan dua asam amino yang mengalami kontak. Pada contact map yang ekuivalen dalam dua protein, terdapat suatu alignment yang menunjukkan ikatan antara kontak-kontak pada protein pertama dengan kontak-kontak pada protein kedua. Setiap pasangan kontak tersebut dinamakan overlap. Masalah Contact Map Overlap (CMO) merupakan permasalahan dalam pencarian overlap terbanyak yang dapat dibentuk dari asam-asam amino yang berikatan antara dua jenis protein. Masalah CMO dalam struktur protein dapat dijelaskan sebagai model Masalah Maksimum Clique dalam suatu kasus pendefinisian graf. Clique dalam graf adalah subgraf dengan sifat bahwa setiap pasang verteksnya terhubung oleh edge. Model Masalah Maksimum Clique menggunakan metode pengurutan verteks untuk mereduksi graf dan pewarnaan verteks berdasar verteks tetangganya. Solusi dari Masalah Maksimum Clique menjelaskan suatu Masalah CMO yang optimal dari ikatan antara dua jenis protein tersebut.