Smith Waterman

MABBI – Algoritme Smith–Waterman melakukan penyelarasan urutan lokal; yaitu, untuk menentukan daerah serupa antara dua rangkaian sekuens asam nukleat atau sekuens protein. Alih-alih melihat seluruh urutan, algoritma Smith-Waterman membandingkan segmen dari semua kemungkinan panjang dan mengoptimalkan ukuran kesamaan. Algoritma ini pertama kali diusulkan oleh Temple F. Smith dan Michael S. Waterman pada tahun 1981. Seperti algoritma Needleman–Wunsch, yang merupakan variasinya, Smith–Waterman adalah algoritma pemrograman dinamis. Dengan demikian, ia memiliki sifat yang diinginkan yaitu dijamin untuk menemukan keselarasan lokal yang optimal sehubungan dengan sistem penilaian yang digunakan (yang mencakup matriks substitusi dan skema penilaian kesenjangan). Perbedaan utama pada algoritme Needleman–Wunsch adalah bahwa sel matriks penilaian negatif diatur ke nol, yang menjadikan keberpihakan lokal (dengan demikian penilaian positif) terlihat. Prosedur traceback dimulai pada sel matriks dengan skor tertinggi dan dilanjutkan hingga ditemukan sel dengan skor nol, menghasilkan penyelarasan lokal dengan skor tertinggi. Karena kompleksitas kuadratnya dalam ruang dan waktu, sering kali tidak dapat diterapkan secara praktis untuk masalah berskala besar dan digantikan dengan alternatif yang kurang umum tetapi lebih efisien secara komputasi seperti (Gotoh, 1982), (Altschul dan Erickson, 1986), dan (Myers dan Miller, 1988). Pada tahun 1970, Saul B. Needleman dan Christian D. Wunsch mengusulkan algoritma homologi heuristik untuk penyelarasan urutan, juga disebut sebagai algoritma Needleman-Wunsch. Ini adalah algoritma penyelarasan global yang membutuhkan O(mn) langkah perhitungan (m dan n adalah panjang dari dua urutan yang disejajarkan). Ini menggunakan perhitungan berulang dari matriks untuk tujuan menunjukkan keselarasan global. Pada dekade berikutnya, Sankoff, Reichert, Beyer dan lainnya merumuskan algoritme heuristik alternatif untuk menganalisis urutan gen. Penjual memperkenalkan sistem untuk mengukur jarak urutan. Pada tahun 1976, Waterman et al. menambahkan konsep celah ke dalam sistem pengukuran asli. Pada tahun 1981, Smith dan Waterman menerbitkan algoritma Smith–Waterman mereka untuk menghitung penyelarasan lokal. Algoritme Smith–Waterman cukup menuntut waktu: Untuk menyelaraskan dua urutan panjang m dan N,(2) {displaystyle O(m2n)} waktu diperlukan. Gotoh dan Altschul mengoptimalkan algoritme untuk O(mn) langkah. Kompleksitas ruang dioptimalkan oleh Myers dan Miller dari O(mn) ke O(n) (linier), di mana n adalah panjang urutan yang lebih pendek, untuk kasus di mana hanya satu dari banyak kemungkinan keberpihakan optimal yang diinginkan. Chowdhury, Le, dan Ramachandran kemudian mengoptimalkan kinerja cache dari algoritma sambil menjaga penggunaan ruang tetap linier dalam total panjang urutan input.
Dalam beberapa tahun terakhir, proyek genom yang dilakukan pada berbagai organisme menghasilkan sejumlah besar data sekuens untuk gen dan protein, yang memerlukan pemrosesan ulang. Penyelarasan urutan menunjukkan hubungan antara gen atau antara protein, yang mengarah ke pemahaman yang lebih baik tentang homologi dan fungsionalitasnya. Penyelarasan urutan juga dapat mengungkapkan domain dan motif yang dilestarikan. Salah satu motivasi untuk penyelarasan lokal adalah sulitnya mendapatkan penyelarasan yang benar-benar di wilayah dengan kenyamanan yang rendah antara sekuens biologi yang berkerabat jauh, karena mutasi telah menambahkan terlalu banyak ‘kebisingan’ selama evolusi waktu untuk memungkinkan perbandingan yang berarti dari wilayah tersebut. Penyelarasan lokal menghindari wilayah semacam itu sama sekali dan berfokus pada wilayah dengan skor positif, yaitu wilayah dengan sinyal kenyamanan yang dilestarikan secara evolusioner. Prasyarat untuk penyelarasan lokal adalah skor ekspektasi negatif. Skor ekspektasi didefinisikan sebagai skor rata-rata yang akan dihasilkan oleh sistem penilaian (matriks substitusi dan gap penalti) untuk urutan acak. Motivasi lain untuk menggunakan keberpihakan lokal adalah adanya model statistik yang dapat diandalkan (dikembangkan oleh Karlin dan Altschul) untuk keberpihakan lokal yang optimal. Urutan penjajaran yang tidak terkait cenderung menghasilkan skor keselarasan lokal yang optimal yang mengikuti distribusi nilai ekstrim. Properti ini memungkinkan program untuk menghasilkan nilai harapan untuk penyelarasan lokal yang optimal dari dua sekuens, yang merupakan ukuran seberapa sering dua sekuens yang tidak terkait akan menghasilkan penyelarasan lokal yang optimal yang skornya lebih besar atau sama dengan skor yang diamati. Nilai ekspektasi yang sangat rendah menunjukkan bahwa dua sekuens yang dipermasalahkan mungkin homolog, artinya mereka mungkin memiliki nenek moyang yang sama. (Tri/MABBI)